社区首页 >专栏 >C++红黑树的深入解析：从理论到实践

C++红黑树的深入解析：从理论到实践

用户11289931

发布于 2025-03-20 05:58:46

12000

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

红黑树作为一种自平衡的二叉搜索树，是计算机科学中的经典数据结构之一，广泛应用于各种需要高效查找、插入和删除操作的场景中，比如STL中的 map 和 set。虽然它的基本原理并不复杂，但在实现过程中，需要处理许多细节，比如颜色的调整、旋转操作等。本文将对红黑树的结构、插入、删除等操作进行详细的剖析，以帮助大家更好地理解和实现这一高效的数据结构。

一、红黑树的基本概念与规则

红黑树是一种满足特定性质的二叉搜索树。与普通的二叉搜索树不同，红黑树的每个结点都附加了一个颜色属性，且通过一些规则保证了树的平衡性。红黑树的四条基本规则如下：

每个节点的颜色要么是红色，要么是黑色。
根节点是黑色的。
如果一个节点是红色的，那么它的两个子节点必须是黑色的。 这就意味着红色节点不能有连续的红色节点。
从任意一个节点到其所有叶子节点的路径上，必须包含相同数量的黑色节点。 这条规则保证了树的平衡性，防止树的某些路径过长。

红黑树的这些规则通过“颜色约束”来间接实现自平衡，因此每次进行插入、删除操作时，都需要确保这些规则被满足。

以上均为红黑树示例。

二、红黑树的高度与效率

红黑树的高度是它的关键特性之一。红黑树的自平衡机制确保了它的高度不会太大，这对于树的查找、插入和删除操作的效率至关重要。理论上，红黑树的高度 h 与黑色高度 bh（从根到叶子节点的路径上黑色节点的数量）之间存在如下关系：

最短路径（只有黑色节点）长度为 bh。
最长路径（交替的红色和黑色节点）长度为 2 * bh。

因此，红黑树的最大高度为 2 * bh，而最小高度为 bh。因此，红黑树的高度 h 满足 h≤2×bhh \leq 2 \times bhh≤2×bh，并且由于红黑树的黑色高度是相同的，所以可以得出红黑树的高度是 O(log N)，其中 N 是树中结点的数量。

由于红黑树的高度被控制在对数级别，它能够保证查找、插入、删除操作在最坏情况下的时间复杂度均为 O(log N)。

三、红黑树的结构

红黑树的基本节点结构包括以下几个部分：

enum Colour {
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode {
    pair<K, V> _kv;         // 存储键值对
    RBTreeNode<K, V>* _left;  // 左子树
    RBTreeNode<K, V>* _right; // 右子树
    RBTreeNode<K, V>* _parent;  // 父节点
    Colour _col;  // 颜色属性

    RBTreeNode(const pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};

每个节点不仅包含键值对 (_kv)，还包含指向左子树、右子树和父节点的指针。此外，节点的颜色 (_col) 用于维护红黑树的平衡。

四、红黑树的插入操作

红黑树的插入操作需要遵循以下步骤：

按照二叉搜索树的规则插入新节点。这是插入操作的第一步，我们首先将新节点插入到树的适当位置。
将新节点的颜色设置为红色。新插入的节点默认是红色的，这有助于避免违反红黑树的黑色节点数平衡。
调整颜色和结构。插入新节点后，可能会破坏红黑树的平衡。具体的修复操作包括：
- 情况1：变色操作。如果父节点和叔叔节点都是红色，则将父节点和叔叔节点都变为黑色，祖父节点变为红色，并继续往上处理。
- 情况2：旋转和变色。如果父节点是红色，且叔叔节点是黑色或不存在，则需要进行旋转操作（单旋或双旋），并相应地调整颜色。

我们来看一段插入代码的实现：

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false; // 键值重复
        }
    }

    cur = new Node(kv);
    cur->_col = RED;
    if (parent->_kv.first < kv.first) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }
    cur->_parent = parent;

    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        if (parent == grandfather->_left) {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                if (cur == parent->_left) {
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        } else {
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED) {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                if (cur == parent->_right) {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }

    _root->_col = BLACK;
    return true;
}

这段代码展示了红黑树的插入操作，包括节点插入、颜色变更和旋转操作。关键的操作是通过循环和条件判断来确保红黑树的规则不被破坏。

五、红黑树的查找操作

红黑树的查找操作和普通的二叉搜索树是类似的，我们依然按照二叉搜索树的规则进行查找。由于红黑树的平衡性，查找操作的时间复杂度为 O(log N)。

Node* Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < key) {
            cur = cur->_right;
        } else if (cur->_kv.first > key) {
            cur = cur->_left;
        } else {
            return cur;
        }
    }
    return nullptr;
}

上述代码展示了查找操作的实现，我们根据节点的键值逐步向左或向右子树移动，直到找到目标节点或树为空。

六、红黑树的删除操作

删除操作在红黑树中比插入操作更为复杂。删除一个节点后，可能会破坏红黑树的平衡，特别是当删除的节点是黑色时，需要特别注意。因此，删除操作需要执行旋转和变色操作来恢复平衡。尽管删除操作复杂，但其时间复杂度同样是 O(log N)。

由于删除操作较为复杂，本文不深入讨论其实现。如果有兴趣，可以参考《算法导论》或《STL源码剖析》中的相关章节。

七、红黑树的验证

为了验证红黑树的正确性，我们可以检查它是否满足四条基本规则。可以通过前序遍历树的每一条路径，检查节点颜色和黑色节点数量是否符合要求。

bool Check(Node* root, int blackNum, const int refNum) {
    if (root == nullptr) {
        if (refNum != blackNum) {
            cout << "存在黑色结点数量不相等的路径" << endl;
            return false;
        }
        return true;
    }
    if (root->_col == RED && root->_parent->_col == RED) {
        cout << root->_kv.first << "存在连续的红色结点" << endl;
        return false;
    }
    if (root->_col == BLACK) {
        blackNum++;
    }
    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}