• 日期: 2024-07-13
  • 标签: 常规

红黑树是一种自平衡二叉查找树，它保证了在最坏情况下的查找、插入和删除操作的时间复杂度都是 O(log n)。它的实现涉及到一些复杂的旋转和颜色变换操作，但是可以通过递归和迭代两种方式实现。

以下是递归实现的红黑树代码：

#include <iostream>
#include <cstdlib>

using namespace std;

enum Color {
    RED,
    BLACK
};

struct Node {
    int key;
    Color color;
    Node *left, *right, *parent;
};

class RBTree {
private:
    Node *root;

protected:
    void rotateLeft(Node *);
    void rotateRight(Node *);
    void fixInsert(Node *);
    void fixDelete(Node *);
    Node *minimum(Node *);
    Node *maximum(Node *);
    Node *successor(Node *);
    Node *predecessor(Node *);
    void transplant(Node *, Node *);
    void destroy(Node *);

public:
    RBTree();
    ~RBTree();
    Node *getRoot();
    Node *search(int);
    void insert(int);
    void remove(int);
    void print();
};

RBTree::RBTree() {
    root = NULL;
}

RBTree::~RBTree() {
    destroy(root);
}

Node *RBTree::getRoot() {
    return root;
}

Node *RBTree::search(int key) {
    Node *current = root;

    while (current != NULL && current->key != key) {
        if (key < current->key) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    return current;
}

void RBTree::insert(int key) {
    Node *node = new Node;
    node->key = key;
    node->color = RED;
    node->left = NULL;
    node->right = NULL;

    Node *parent = NULL;
    Node *current = root;

    while (current != NULL) {
        parent = current;

        if (key < current->key) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    node->parent = parent;

    if (parent == NULL) {
        root = node;
    } else if (key < parent->key) {
        parent->left = node;
    } else {
        parent->right = node;
    }

    fixInsert(node);
}

void RBTree::remove(int key) {
    Node *node = search(key);

    if (node == NULL) {
        return;
    }

    Node *x = NULL;
    Node *y = node;
    Color yOriginalColor = y->color;

    if (node->left == NULL) {
        x = node->right;
        transplant(node, node->right);
    } else if (node->right == NULL) {
        x = node->left;
        transplant(node, node->left);
    } else {
        y = minimum(node->right);
        yOriginalColor = y->color;
        x = y->right;

        if (y->parent == node) {
            x->parent = y;
        } else {
            transplant(y, y->right);
            y->right = node->right;
            y->right->parent = y;
        }

        transplant(node, y);
        y->left = node->left;
        y->left->parent = y;
        y->color = node->color;
    }

    if (yOriginalColor == BLACK) {
        fixDelete(x);
    }

    delete node;
}

void RBTree::print() {
    cout << "Red Black Tree:" << endl;

    if (root != NULL) {
        cout << root->key << endl;
    } else {
        cout << "Empty tree." << endl;
    }
}

void RBTree::rotateLeft(Node *node) {
    Node *right = node->right;
    node->right = right->left;

    if (right->left != NULL) {
        right->left->parent = node;
    }

    right->parent = node->parent;

    if (node->parent == NULL) {
        root = right;
    } else if (node == node->parent->left) {
        node->parent->left = right;
    } else {
        node->parent->right = right;
    }

    right->left = node;
    node->parent = right;
}

void RBTree::rotateRight(Node *node) {
    Node *left = node->left;
    node->left = left->right;

    if (left->right != NULL) {
        left->right->parent = node;
    }

    left->parent = node->parent;

    if (node->parent == NULL) {
        root = left;
    } else if (node == node->parent->left) {
        node->parent->left = left;
    } else {
        node->parent->right = left;
    }

    left->right = node;
    node->parent = left;
}

void RBTree::fixInsert(Node *node) {
    while (node != root && node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            Node *uncle = node->parent->parent->right;

            if (uncle != NULL && uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    rotateLeft(node);
                }

                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rotateRight(node->parent->parent);
            }
        } else {
            Node *uncle = node->parent->parent->left;

            if (uncle != NULL && uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rotateRight(node);
                }

                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rotateLeft(node->parent->parent);
            }
        }
    }

    root->color = BLACK;
}

void RBTree::fixDelete(Node *node) {
    while (node != root && node->color == BLACK) {
        if (node == node->parent->left) {
            Node *sibling = node->parent->right;

            if (sibling->color == RED) {
                sibling->color = BLACK;
                node->parent->color = RED;
                rotateLeft(node->parent);
                sibling = node->parent->right;
            }

            if (sibling->left->color == BLACK && sibling->right->color == BLACK) {
                sibling->color = RED;
                node = node->parent;
            } else {
                if (sibling->right->color == BLACK) {
                    sibling->left->color = BLACK;
                    sibling->color = RED;
                    rotateRight(sibling);
                    sibling = node->parent->right;
                }

                sibling->color = node->parent->color;
                node->parent->color = BLACK;
                sibling->right->color = BLACK;
                rotateLeft(node->parent);
                node = root;
            }
        } else {
            Node *sibling = node->parent->left;

            if (sibling->color == RED) {
                sibling->color = BLACK;
                node->parent->color = RED;
                rotateRight(node->parent);
                sibling = node->parent->left;
            }

            if (sibling->right->color == BLACK && sibling->left->color == BLACK) {
                sibling->color = RED;
                node = node->parent;
            } else {
                if (sibling->left->color == BLACK) {
                    sibling->right->color = BLACK;
                    sibling->color = RED;
                    rotateLeft(sibling);
                    sibling = node->parent->left;
                }

                sibling->color = node->parent->color;
                node->parent->color = BLACK;
                sibling->left->color = BLACK;
                rotateRight(node->parent);
                node = root;
            }
        }
    }

    node->color = BLACK;
}

Node *RBTree::minimum(Node *node) {
    while (node->left != NULL) {
        node = node->left;
    }

    return node;
}

Node *RBTree::maximum(Node *node) {
    while (node->right != NULL) {
        node = node->right;
    }

    return node;
}

Node *RBTree::successor(Node *node) {
    if (node->right != NULL) {
        return minimum(node->right);
    }

    Node *parent = node->parent;

    while (parent != NULL && node == parent->right) {
        node = parent;
        parent = parent->parent;
    }

    return parent;
}

Node *RBTree::predecessor(Node *node) {
    if (node->left != NULL) {
        return maximum(node->left);
    }

    Node *parent = node->parent;

    while (parent != NULL && node == parent->left) {
        node = parent;
        parent = parent->parent;
    }

    return parent;
}

void RBTree::transplant(Node *u, Node *v) {
    if (u->parent == NULL) {
        root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }

    if (v != NULL) {
        v->parent = u->parent;
    }
}

void RBTree::destroy(Node *node) {
    if (node != NULL) {
        destroy(node->left);
        destroy(node->right);
        delete node;
    }
}

int main() {
    RBTree tree;

    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(1);
    tree.insert(9);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);
    tree.insert(2);

    tree.print();

    tree.remove(5);
    tree.remove(3);

    tree.print();

    return 0;
}

以上代码中包含了红黑树的基本操作，包括插入、删除、查找、旋转、颜色变换等等。可以通过这些操作实现红黑树的自平衡。

c++--红黑树的实现

原文地址: https://www.cveoy.top/t/topic/rea 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录