手写红黑树（C++实现）

原创

大盘鸡拌面

发布于 2023-12-04 10:24:31

3100

发布于 2023-12-04 10:24:31

文章被收录于专栏：软件研发

手写红黑树（C++实现）

在计算机科学中，红黑树（Red-Black tree）是一种自平衡的二叉搜索树，它是在B树的基础上添加了颜色标记，用以保证其在插入和删除等操作后能够保持平衡。红黑树的特点是：

每个节点都被标记为红色或黑色。
根节点和叶子节点（NIL节点）被标记为黑色。
如果一个节点是红色的，则它的子节点必须是黑色的。
从任何一个节点到其每个叶子节点的路径上都包含相同数目的黑色节点。本文将带你一步步实现红黑树的基本功能，包括插入、删除和搜索等操作。我们使用C++语言来实现红黑树的数据结构和算法。

数据结构定义

首先，我们定义一个Node结构体来表示红黑树的节点：

cppCopy codestruct Node {
    int data;
    bool isBlack;
    Node* left;
    Node* right;
    Node* parent;
};

其中，data字段表示节点存储的数据，isBlack字段表示节点的颜色（黑色为true，红色为false），left和right字段分别指向节点的左子节点和右子节点，parent字段指向节点的父节点。接下来，我们定义一个RedBlackTree类来实现红黑树的操作：

cppCopy codeclass RedBlackTree {
public:
    RedBlackTree();
    ~RedBlackTree();
    bool search(int key);
    void insert(int key);
    void remove(int key);
    void printTree();
private:
    void insertFixup(Node* node);
    void deleteFixup(Node* node, Node* parent);
    void rotateLeft(Node* node);
    void rotateRight(Node* node);
    void transplant(Node* u, Node* v);
    void destroyTree(Node* node);
    void printTreeHelper(Node* node, int indent);
    Node* root;
};

插入操作

接下来，我们来实现红黑树的插入操作。插入操作分为两个步骤：首先按照二叉搜索树的规则找到插入位置，然后根据红黑树的规则进行调整。在RedBlackTree类中，我们添加一个insert方法用于插入新节点：

cppCopy codevoid RedBlackTree::insert(int key) {
    Node* newNode = new Node();
    newNode->data = key;
    newNode->isBlack = false;
    newNode->left = NULL;
    newNode->right = NULL;
    Node* current = root;
    Node* parent = NULL;
    // 找到插入位置
    while (current != NULL) {
        parent = current;
        if (key < current->data) {
            current = current->left;
        } 
        else if (key > current->data) {
            current = current->right;
        } 
        else {
            // 若节点已存在，则直接返回
            delete newNode;
            return;
        }
    }
    newNode->parent = parent;
    // 插入新节点
    if (parent == NULL) {
        // 空树，直接将新节点设为根节点
        root = newNode;
    } 
    else if (key < parent->data) {
        parent->left = newNode;
    } 
    else {
        parent->right = newNode;
    }
    // 调整红黑树
    insertFixup(newNode);
}

插入调整

在插入节点后，我们可能需要进行一系列的旋转和颜色调整来满足红黑树的规则。具体的插入调整逻辑包括以下几种情况：

新节点是根节点。
新节点的父节点是黑色。
新节点的父节点是红色，并且叔节点也是红色。
新节点的父节点是红色，并且叔节点是黑色（或者为空）。具体实现如下：

cppCopy codevoid RedBlackTree::insertFixup(Node* node) {
    Node* parent = NULL;
    Node* grandparent = NULL;
    while (node != root && node->isBlack == false && node->parent->isBlack == false) {
        parent = node->parent;
        grandparent = parent->parent;
        if (parent == grandparent->left) {
            Node* uncle = grandparent->right;
            if (uncle != NULL && uncle->isBlack == false) {
                parent->isBlack = true;
                uncle->isBlack = true;
                grandparent->isBlack = false;
                node = grandparent;
            } 
            else {
                if (node == parent->right) {
                    rotateLeft(parent);
                    node = parent;
                    parent = node->parent;
                }
                rotateRight(grandparent);
                std::swap(parent->isBlack, grandparent->isBlack);
                node = parent;
            }
        } 
        else {
            Node* uncle = grandparent->left;
            if (uncle != NULL && uncle->isBlack == false) {
                parent->isBlack = true;
                uncle->isBlack = true;
                grandparent->isBlack = false;
                node = grandparent;
            } 
            else {
                if (node == parent->left) {
                    rotateRight(parent);
                    node = parent;
                    parent = node->parent;
                }
                rotateLeft(grandparent);
                std::swap(parent->isBlack, grandparent->isBlack);
                node = parent;
            }
        }
    }
    root->isBlack = true;
}

其他操作和打印红黑树

除了插入操作，我们还可以实现红黑树的搜索、删除和打印等操作。这里为了篇幅，省略了这些方法的实现。感兴趣的读者可以尝试自己实现或者参考其他资料。为了方便调试和验证，我们还提供了一个打印红黑树的方法：

cppCopy codevoid RedBlackTree::printTree() {
    if (root == NULL) {
        std::cout << "Empty tree" << std::endl;
        return;
    }
    printTreeHelper(root, 0);
}
void RedBlackTree::printTreeHelper(Node* node, int indent) {
    if (node == NULL) {
        return;
    }
    printTreeHelper(node->right, indent + 4);
    if (indent > 0) {
        std::cout << std::setw(indent) << " ";
    }
    std::cout << node->data << (node->isBlack ? "B" : "R") << std::endl;
    printTreeHelper(node->left, indent + 4);
}

红黑树是一种自平衡的二叉查找树，在面试中常被问及。了解红黑树的实现细节，可以帮助你更好地理解其原理和特性。下面我将介绍红黑树的一般实现流程，帮助你对其有更全面的了解。红黑树的实现细节包括以下几个方面：

结构定义：首先，我们需要定义一个红黑树的结构，包括树节点的属性和方法。一个典型的节点结构定义如下：

pythonCopy codeclass Node:
    def __init__(self, data, color):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None
        self.color = color

插入操作：红黑树的插入操作分为几个步骤。首先，我们按照二叉查找树的规则将节点插入到适当的位置。然后，根据红黑树的性质对节点进行颜色调整和旋转操作，以保持红黑树的平衡。在插入操作中，我们需要处理以下情况：
- 当插入节点的父节点是红色节点时，需要进行颜色调整和旋转操作，使树保持平衡。
- 如果插入节点的父节点是黑色节点，无需进行调整。插入操作的伪代码如下：

pythonCopy codedef insert(self, data):
    node = Node(data, "RED")
    # 将节点插入合适的位置
    # ...
    # 插入后对树进行修复
    self._insert_fixup(node)

插入修复操作的伪代码如下：

pythonCopy codedef _insert_fixup(self, node):
    while node.parent and node.parent.color == "RED":
        if node.parent == node.parent.parent.left:
            uncle = node.parent.parent.right
            if uncle and 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
                    self._left_rotate(node)
                node.parent.color = "BLACK"
                node.parent.parent.color = "RED"
                self._right_rotate(node.parent.parent)
        else:
            # 类似处理右边对称的情况
            # ...
    self.root.color = "BLACK"

删除操作：红黑树的删除操作相对复杂，涉及到了多种情况的处理。删除操作主要分为以下几个步骤：
- 首先，按照二叉查找树的规则找到待删除的节点，并进行删除。
- 然后，根据红黑树的性质对树进行修复，以保持红黑树的平衡。在删除操作中，我们需要处理以下情况：
- 当删除节点是红色节点时，直接删除，不会影响红黑树的平衡。
- 当删除节点是黑色节点时，需要进行额外的处理才能保持红黑树的平衡。删除操作的伪代码如下：

pythonCopy codedef delete(self, data):
    node = self._search(data)  # 先找到待删除的节点
    if not node:
        return
    self._remove(node)  # 删除节点
    self._remove_fixup(node.parent)  # 修复红黑树

删除修复操作的伪代码如下：

pythonCopy codedef _remove_fixup(self, node):
    while node != self.root and node.color == "BLACK":
        if node == node.parent.left:
            sibling = node.parent.right
            if sibling.color == "RED":
                sibling.color = "BLACK"
                node.parent.color = "RED"
                self._left_rotate(node.parent)
                sibling = node.parent.right
            if (not sibling.left or sibling.left.color == "BLACK") and \
                    (not sibling.right or sibling.right.color == "BLACK"):
                sibling.color = "RED"
                node = node.parent
            else:
                if not sibling.right or sibling.right.color == "BLACK":
                    sibling.left.color = "BLACK"
                    sibling.color = "RED"
                    self._right_rotate(sibling)
                    sibling = node.parent.right
                sibling.color = node.parent.color
                node.parent.color = "BLACK"
                sibling.right.color = "BLACK"
                self._left_rotate(node.parent)
                node = self.root
        else:
            # 类似处理右边对称的情况
            # ...
    node.color = "BLACK"

这是红黑树的一个基本实现，但实际上还有许多细节需要考虑，例如树的查找、旋转等操作，以及对应的辅助函数的实现。红黑树的实现还有很多变种和优化，涉及更多的特殊情况处理和平衡性维护。但是通过了解这个基本的实现流程，你应该可以更好地理解红黑树的原理和特性，并能够自己实现一个简单的红黑树。

总结

至此，我们完成了红黑树的基本操作和打印方法的实现。红黑树是一种重要的自平衡二叉搜索树，在很多场景下都有广泛的应用。通过手写实现红黑树，我们不仅能够更深入地理解红黑树的原理和操作，还能够提升自己的编程能力。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c++

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c++

登录后参与评论

0 条评论

热度

手写红黑树（C++实现）

手写红黑树（C++实现）

手写红黑树（C++实现）

数据结构定义

插入操作

插入调整

其他操作和打印红黑树

总结

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐