网站导航
> 技术文档 > C++-红黑树_C++红黑树平衡调整算法

C++-红黑树_C++红黑树平衡调整算法

网友: 技术文档 2025-09-02 19:10:45

1、红黑树的概念

        红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍，因而是接近平衡的。

红黑树图像，如图所示：

2、红黑树的性质

  1. 颜色属性：每个节点不是红色就是黑色

  2. 根节点属性：根节点必须是黑色的

  3. 红色节点属性：如果一个节点是红色的，则它的两个子节点必须是黑色的（即不能有两个连续的红色节点）

  4. 黑色高度属性：对于每个节点，从该节点到其所有后代叶节点的简单路径上，包含相同数目的黑色节点

  5. 叶子节点属性：每个叶子节点（NIL节点，空节点）都是黑色的

        这些性质保证了红黑树的关键特性：最长路径不超过最短路径的两倍，从而保证了树的平衡性。

3、红黑树的实现

1.节点结构定义

templatestruct RBTreeNode { RBTreeNode* _left; // 左子节点 RBTreeNode* _right; // 右子节点 RBTreeNode* _parent; // 父节点 T _kv;  // 键值对数据 Colour _col; // 节点颜色(RED或BLACK) RBTreeNode(const T& kv) :_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) {}};

        节点包含左右子节点指针、父节点指针、存储的数据以及颜色标记。新节点默认为红色。

2. 插入操作 (Insert)

        功能：向红黑树中插入一个新节点，并保持红黑树的性质。

步骤：

  1. 如果树为空，创建新节点作为根节点，并设为黑色

  2. 按照二叉搜索树的规则找到插入位置

  3. 创建新节点（红色）并插入到正确位置

  4. 检查并修复红黑树性质：

    • 如果父节点是黑色，无需处理

    • 如果父节点是红色，需要调整：

      • 情况1：叔叔节点是红色 - 变色处理

      • 情况2：叔叔节点是黑色或不存在 - 旋转处理

  5. 确保根节点始终为黑色

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

  • 情况一: cur为红，p为红，g为黑，u存在且为红

cur和p均为红，违反了性质三，此处能否将p直接改为黑？

        解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

  • 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的左孩子，则进行右单旋转；

相反， p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红

  • 情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；

相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

则转换成了情况2

针对每种情况进行相应的处理即可。

bool Insert(const T& 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 _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 _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;//u存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else //u不存在或存在且为黑{if (cur == parent->_left){//g//p//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//p//cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;//u存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g// p// cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

3. 左旋操作 (RotateL)

        功能：以parent节点为支点进行左旋。

操作：

  1. 将cur的左子节点作为parent的右子节点

  2. 将parent作为cur的左子节点

  3. 更新各个节点的父指针

  4. 处理根节点情况

//左单旋void RotateL(Node* parent){Node* cur = parent->_right;parent->_right = cur->_left;if (cur->_left){cur->_left->_parent = parent;}cur->_left = parent;Node* pparent = parent->_parent;parent->_parent = cur;if (pparent == nullptr){_root = cur;cur->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = cur;}else if (pparent->_right == parent){pparent->_right = cur;}cur->_parent = pparent;}}

4.右旋操作 (RotateR)

        功能：以parent节点为支点进行右旋。

操作：

  1. 将cur的右子节点作为parent的左子节点

  2. 将parent作为cur的右子节点

  3. 更新各个节点的父指针

  4. 处理根节点情况

//右单旋void RotateR(Node* parent){Node* cur = parent->_left;parent->_left = cur->_right;if (cur->_right){cur->_right->_parent = parent;}Node* pparent = parent->_parent;cur->_right = parent;parent->_parent = cur;if (pparent == nullptr){_root = cur;cur->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = cur;}else{pparent->_right = cur;}cur->_parent = pparent;}}

5. 红黑树验证 (IsBalance)

功能：验证红黑树是否满足以下性质：

  1. 每个节点要么是红色，要么是黑色

  2. 根节点是黑色

  3. 每个叶子节点（NIL节点）是黑色

  4. 不能有两个连续的红色节点

  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

实现：

  1. IsBalance()是公开接口，调用IsBalance(_root)

  2. IsBalance(Node* root)验证根节点是否为黑色

  3. CheckColour()递归检查：

    • 计算每条路径的黑色节点数是否一致

    • 检查是否有连续的红色节点

bool CheckColour(Node* root, int blacknum, int benchmark){//递归停止条件if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout <_kv.first << \"出现连续的红色节点\" <_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}//基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}

4、红黑树与AVL树的比较

特性 红黑树 AVL树 平衡标准 近似平衡（最长路径≤2倍最短） 严格平衡（高度差≤1） 查询效率 O(log n) O(log n) 插入/删除效率 相对较高（旋转次数少） 相对较低（旋转次数多） 实现复杂度 中等 较高 适用场景 频繁插入删除的场景 查询为主、很少修改的场景

5、 红黑树的应用

  1. C++ STL：map、set、multimap、multiset

  2. Java集合框架：TreeMap、TreeSet

  3. Linux内核：进程调度、内存管理等

  4. 其他：数据库索引、文件系统等

6、 总结

        红黑树是一种高效的平衡二叉搜索树，它通过颜色标记和旋转操作维持树的近似平衡。相比于AVL树，红黑树在插入和删除操作上更为高效，适合需要频繁修改的场景。理解红黑树的原理和实现，对于深入掌握STL容器和许多系统级的数据结构都有重要意义。

         红黑树的设计体现了计算机科学中典型的时空权衡思想：通过放宽平衡条件来减少维护平衡的开销，同时仍能保证较好的性能。这种思想在许多算法和数据结构中都有体现，值得深入理解和掌握。

网络标签：

相关问题