您的位置：首页 > 财经 > 产业 > C++红黑树

C++红黑树

2024/11/16 10:43:08 来源：https://blog.csdn.net/2301_77525727/article/details/140664407  浏览:  次   关键词：C++红黑树

目录

  • 前言
  • 红黑树的概念
  • 红黑树的性质
  • 红黑树节点的定义
  • 红黑树结构
  • 红黑树的定义
  • 红黑树的插入操作
    • （1）按照二叉搜索的树规则插入新节点
    • （2）检测新节点插入后，红黑树的性质是否造到破坏
      • 【情况一】cur为红，p为红，g为黑，==u存在且为红==
      • 【情况二】cur为红，p为红，g为黑，==u不存在/u存在且为黑==
      • 【情况三】cur 为红，p 为红，g 为黑，u不存在/u存在且为黑
  • 红黑树的验证
  • 红黑树的删除
  • 红黑树与AVL树的比较
  • 红黑树的应用

前言

AVL树：严格平衡（左右子树高度差不超过 1），所以 AVL 树的查找、插入、删除效率高：O(logN)，但在插入和删除节点后，要维持树的平衡状态，做的旋转处理还是很多的。
红黑树：近似平衡（控制最长路径不超过最短路径的2倍），变了一种方式来控制树的平衡，相较于 AVL 树而言，没有那么严格。

红黑树更多是一种折中的选择，它舍弃平衡二叉树的严格平衡，换取节点插入时尽可能少的调整。

因为红黑树的旋转情况少于 AVL 树，使得红黑树整体性能略优于 AVL 树，不然 map 和 set 底层怎么会使用红黑树呢，包括很多语言的库里面都用了红黑树。

红黑树的概念

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

在这里插入图片描述

红黑树的性质

  1. 每个结点不是红色就是黑色。
  2. 根节点是黑色的 。
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的。（红黑树里面没有 连续的 红色节点）
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上， 均包含相同数目的黑色结点 。（即每条路径都有相同数量的黑色节点，注意：路径是走到 NIL 空节点）
  5. 每个 NIL 叶子结点都是黑色的。（此处的叶子结点指的是空结点）

上图这颗红黑树一共有 11 条路径，每条路径都有两个黑节点（不包括 NIL）。

思考：为什么满足上面的性质，红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的 2 倍呢？（不包括NIL）

当某条路径最短时，这条路径必然都是由黑色节点构成。
当某条路径长度最长时，这条路径必然是由红色和黑色节点交替构成的
（上面第 3 点限定了不能出现两个连续的红色节点）。而第 4 点又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点，那么说明最长路径上黑节点的数目和最短路径上 黑节点的数目是相等 的。

  • 最短路径：全是黑节点。
  • 最长路径：一黑一红，交替出现，所以最长路径刚好是最短路径的 2 倍。
    在这里插入图片描述

红黑树节点的定义


// 定义节点的颜色
enum Color // 枚举类型，枚举值默认从0开始，往后逐个加1（递增）
{RED,BLACK
};// 红黑树节点的定义（KV模型）
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;   // 三叉链结构RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;            // 键值对Colour _col;               // 用来标记节点颜色// 构造函数RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}
};

在节点的定义中，为什么要将节点的默认颜色给成红色的？

如果插入黑色节点，一定会破坏第 4 点性质（每条路径的黑色节点数量相等）。
如果插入红色节点，可能会破坏第 3 点性质（树中不能出现两个连续的红色节点）。
所以默认给红色。（破坏第 3 点性质的可行性高一些）

红黑树结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 parent 域指向红黑树的根节点，_left 域指向红黑树中最小的节点，_right 域指向红黑树中最大的节点，如下：

在这里插入图片描述

红黑树的定义


// 红黑树的定义（KV模型）
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree() :_root(nullptr) {}        // 构造函数bool Insert(const pair<K, V>& kv); // 插入节点void InOrder();                    // 中序遍历bool IsBalance();                  // 检测红黑树是否平衡           // ......private:void _InOrder(Node* root);         // 中序遍历子函数void RotateL(Node* parent)         // 左单旋void RotateR(Node* parent)         // 右单旋// ......
private:Node* _root;
};

红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

（1）按照二叉搜索的树规则插入新节点


template<class ValueType>
class RBTree
{//……bool Insert(const ValueType& data){PNode& root = GetRoot();if (nullptr == root){root = new Node(data, BLACK);// 根的双亲为头节点root->_parent = _pHead;_pHead->_parent = root;}else{// 1. 按照二叉搜索的树方式插入新节点// 2. 检测新节点插入后，红黑树的性质是否造到破坏，//   若满足直接退出，否则对红黑树进行旋转着色处理}// 根节点的颜色可能被修改，将其改回黑色root->_color = BLACK;_pHead->_left = LeftMost();_pHead->_right = RightMost();return true;}
private:PNode& GetRoot(){ return _pHead->_parent;}// 获取红黑树中最小节点，即最左侧节点Node* LeftMost();// 获取红黑树中最大节点，即最右侧节点Node* RightMost();
private:Node* _pHead;
};

（2）检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：
如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；
如果其双亲节点的颜色为红色，就违反了第 3 点性质（不能有连在一起的红色节点），此时需要对红黑树分情况来讨论：
约定：cur 为当前节点，p（parent）为父节点，g（grandfather）为祖父节点，u（uncle）为叔叔节点。
调整的关键：主要是看 cur 的叔叔节点 u 是否存在，以及叔叔节点 u 的颜色。

【情况一】cur为红，p为红，g为黑，u存在且为红

注意：此处所看到的树，可能是一颗完整的树，也可能是一颗子树。所以可能会一直调整到根节点才停止。
在这里插入图片描述
(cur可以插入在最左边，也可以插入在最右边，如上图所示）

对情况一进行平衡化操作： 先调整颜色，再往上调整。
无论父亲 p 是祖父 g 的左孩子还是右孩子，无论 cur 是父亲 p 的左孩子还是右孩子，处理方式都是一样的：

  • 调整颜色：将 cur 的父亲 p 和叔叔 u 变黑，祖父 g 变红。
  • 把祖父 g 当成新的 cur，往上调整（即往上检测新的子树破坏了性质），分为以下情况：

1.如果 cur 父亲 p 不存在，说明 cur 就是根节点，调整到头了，此时将根节点改为黑色。在这里插入图片描述

2.如果 cur 父亲 p 存在且为黑色，则无需调整（没有违反任何性质)。

3.如果 cur 父亲 p 存在且为红色，继续调整，判断是否产生了情况 2/3：
在这里插入图片描述

注意：情况 1 在向上调整的过程中，可能会产生情况 2/3。
处理方式：旋转（先要判断是哪种旋转） + 变色处理。

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

在这里插入图片描述
如下图所示，情况一向上调整过程中，产生了情况二，情况一的图是情况二的一个分支 ：

在这里插入图片描述

对情况二进行 平衡化操作 ：先单旋，再调整颜色（不管是哪种单旋，颜色调整都一样：p 变黑，g 变红）
注意：对局部的一颗子树平衡化操作，整个过程中，我们要保持当前子树的每条路径中黑色节点数量不变。

将情况一向上调整产生的情况二四种情况进行平衡化处理：
① 如果父亲 p 是祖父 g 的左孩子， cur 是父亲 p 的左孩子：
先对祖父 g 进行右单旋；然后将父亲 p 变黑，祖父 g 变红：

  1. u不存在
    在这里插入图片描述
  1. u存在且为黑
    在这里插入图片描述

② 如果父亲 p 是祖父 g 的右孩子， cur 是父亲 p 的右孩子:
先对祖父 g 进行进行左单旋；然后将父亲 p 变黑，祖父 g 变红：

  1. u不存在
    在这里插入图片描述
  1. u存在且为黑
    在这里插入图片描述

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

情况三的cur插入在p的右边（双旋），情况二的cur插入的p的左边（单旋）
在这里插入图片描述
如下图所示，情况一向上调整过程中，产生了情况三，情况一的图是情况二的一个分支 ：
在这里插入图片描述

对情况三进行 平衡化操作：先双旋，再调整颜色（不管是哪种双旋，颜色调整都一样：cur 变黑，g 变红）
注意：对局部的一颗子树平衡化操作，整个过程中，我们要保持当前子树的每条路径中黑色节点数量不变。

将情况一向上调整产生的情况二四种情况进行平衡化处理：
① 如果父亲 p 是祖父 g 的左孩子， cur 是父亲 p 的右孩子：
先对父亲 p 进行左单旋，再对祖父 g 进行右单旋；然后将 cur 变黑，祖父 g 变红：

  1. u不存在
    在这里插入图片描述
  1. u存在且为黑
    在这里插入图片描述

② 如果父亲 p 是祖父 g 的右孩子，cur 是父亲 p 的左孩子:
先对父亲 p 进行右单旋，再对祖父 g 进行左单旋；然后将 cur 变黑，祖父 g 变红：

  1. u不存在
    在这里插入图片描述
  1. u存在且为黑
    在这里插入图片描述

【总结】
当插入红色新节点 cur 后，如果父亲 p 存在且为红，说明破坏红黑树性质了，需要平衡化操作。


// 插入节点
bool Insert(const pair<K, V>& kv)
{// 1、查找到适合插入的空位置// 判断树是否为空if (_root == nullptr){_root = new Node(kv); // 插入新节点_root->_col = BLACK;  // 根节点为黑色return true;}// 记录当前节点和它的父节点Node* parent = nullptr;Node* cur = _root;while (cur) // cur为空时，说明找到插入位置了{if (kv.first > cur->_kv.first) // 键值大于当前节点{parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first) // 键值小于当前节点{parent = cur;cur = cur->_left;}else // 键值等于当前节点{return false;  // 不允许数据冗余，返回false}}// 插入新节点，颜色为红色（可能会破坏性质3，产生两个连续红色节点）cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first) // 判断新节点是其父亲的左孩子还是右孩子{parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent; // 更新cur的双亲指针// 2、检测红黑树性质有没有被破坏，并控制树的平衡// 如果cur的父亲p存在且为红，则树不平衡，就需要一直往上调整while (parent && parent->_col == RED){Node* grandfater = parent->_parent; // 记录cur的祖父grandfatherassert(grandfater);assert(grandfater->_col == BLACK);// 关键看叔叔// 1、如果parent是grandfather的左孩子if (parent == grandfater->_left){Node* uncle = grandfather->_right; // uncle是grandfather的右孩子// 情况(1)：uncle存在且为红，变色+继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK; // parent和uncle变黑grandfather->_col = RED; // grandfather变红// 继续往上处理cur = grandfater;parent = cur->_parent;}// 情况(2)+(3)：uncle不存在+存在且为黑else{// 情况(2)：右单旋+变色//     g //   p   u// cif (cur == parent->_left) // 如果cur是parent的左孩子，说明是情况2{// 单旋 + 调整颜色RotateR(grandfater);    // 右单旋parent->_col = BLACK;   // parent变黑grandfater->_col = RED; // grandfather变红}else{// 情况3：左右单旋+变色//     g //   p   u//     c// 双旋 + 调整颜色RotateL(parent);        // 左单旋RotateR(grandfater);    // 右单旋cur->_col = BLACK;      // cur变黑grandfater->_col = RED; // grandfather变红}break; // 情况2或3处理完成后，当前子树的根节点为黑，没有连续红节点了，则停止调整}}// 2、如果parent是grandfather的右孩子else // (parent == grandfater->_right){Node* uncle = grandfater->_left; // uncle是grandfather的左孩子// (1) uncle存在且为红，说明是情况1if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK; // parent和uncle变黑grandfater->_col = RED; // grandfather变红// 继续往上处理cur = grandfater;parent = cur->_parent;}// (2) uncle不存在/存在且为黑，说明是情况2或3else{// 情况2：左单旋+变色//     g //   u   p//         c// 如果cur是parent的右孩子，说明是情况2if (cur == parent->_right){// 单旋 + 调整颜色RotateL(grandfater);    // 左单旋parent->_col = BLACK;   // parent变黑grandfater->_col = RED; // grandfather变红}// 如果cur是parent的左孩子，说明是情况3else{// 情况3：右左单旋+变色//     g //   u   p//     c// 双旋 + 调整颜色RotateR(parent);        // 右单旋RotateL(grandfater);    // 左单旋cur->_col = BLACK;      // cur变黑grandfater->_col = RED; // grandfather变红}break; // 情况2或3处理完成后，当前子树的根节点为黑，没有连续红节点了，则停止调整}}}_root->_col = BLACK; // 根节点变黑return true;
}// 左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right; // 记录parent的右孩子Node* subRL = subR->_left;   // 记录parent右孩子的左孩子parent->_right = subRL;if (subRL){subRL->_parent = parent;}	Node* ppNode = parent->_parent; // 先记录下parent的父节点subR->_left = parent;parent->_parent = subR;// root为空，说明parent原先是根节点if (_root == parent){_root = subR;            // subR为新的根节点subR->_parent = nullptr; // subR的双亲指针指向空}// root不为空，说明parent原先是一个普通子树else{// 判断parent原先是父亲ppNode的左孩子还是右孩子if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode; // subR的双亲指针指向ppNode}
}// 右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left; // 记录parent的左孩子Node* subLR = subL->_right; // 记录parent左孩子的右孩子parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent; // 先记录下parent的父节点subL->_right = parent;parent->_parent = subL;// root为空，说明parent原先是根节点if (_root == parent){_root = subL;            // subL为新的根节点subL->_parent = nullptr; // subL的双亲指向指向空}// root不为空，说明parent原先是一个普通子树else{// 判断parent原先是ppNode的左孩子还是右孩子if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode; // subL的双亲指针指向ppNode}
}

动态效果演示：

  • 以升序插入构建红黑树。
    在这里插入图片描述
  • 以降序插入构建红黑树。
    在这里插入图片描述
  • 随机插入构建红黑树
    在这里插入图片描述

红黑树的验证

红黑树的检测分为两步：

  1. 检测其是否满足二叉搜索树（中序遍历是否为有序序列）。
  2. 检测其是否满足红黑树的性质。
  • 根节点是否为黑色。
  • 是否存在连续红节点。
  • 统计每条路径上的黑节点数是否相等。

（1）检测是否存在连续红节点


// 检测红黑树是否有连续红节点
bool CheckRedRed(Node* root)
{if (root == nullptr)return true;// 思路1：如果当前节点为红色，检测它的孩子是否为红色，但孩子可能为空，每次还得判断孩子是否为空，太麻烦了// 思路2：如果当前节点为红色，我们去检测它的父亲是否为红色。因为根节点没有父亲，且根节点为黑色，是不会被判断的if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}// 继续判断当前节点的左右孩子return CheckRedRed(root->_left)&& CheckRedRed(root->_right);
}

（2）检测每条路径上的黑节点数是否相等

首先计算出红黑树其中一条路径的黑节点数，作为一个 baseValue 基准值(参考值)，然后再求出红黑树每条路径的黑节点数，与基准值比较，如果不相等，说明违反性质了。

  • blackNum：表示从根节点到当前节点的黑节点数。
  • benchmark：基准值（最左侧路径的黑节点数）。

// 计算红黑树最左侧这条路径的黑色节点数量基准值(参考值)
int CountBaseValue()
{int benchmark = 0;Node* cur = _root;while (cur) // 遇到NIL时，统计结束{if (cur->_col == BLACK)benchmark++;cur = cur->_left;}return benchmark;
}bool PrevCheck(Node* root, int blackNum, int& benchmark)
{// 当前节点为空，说明遇到了NIL，判断该路径的黑节点数是否等于基准值if (root == nullptr){if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark){cout << "某条黑色节点的数量不相等" << endl;return false;}else{return true;}}// 当前节点为黑色，则从根节点到当前节点的黑节点数加1if (root->_col == BLACK){blackNum++;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);
}

【注意】

这里计算每条路径的黑节点数 blackNum 时，使用的是传值，因为这样就可以在递归的过程中计算到每条路径的黑节点数，因为每个函数栈帧中的 blackNum 变量都是独立存在的。
下一层的 blackNum 是上一层的拷贝，下一层中++，不会影响上一层。
比如在黑节点 1 中对 blackNum++，变成 2，但红节点 8 中的 blackNum 值还是1，所以就不会影响到计算右孩子即黑节点 11 所在路径的黑节点数。

在这里插入图片描述
补：求一棵树的叶子节点数和总的节点数，就可以用引用。


// 检测红黑树是否平衡
bool IsBalance()
{if (_root == nullptr)return true;// 1、检测红黑树的根节点是否为红色if (_root->_col == RED){cout << "根节点不是黑色" << endl;return false;}// 2、CheckRedRed：检测红黑树是否有连续红节点// 3、CheckBlackNums：检测红黑树每条路径黑节点数是否相等return CheckRedRed(_root) && PrevCheck(_root, 0, CountBaseValue());
}

红黑树的删除

红黑树的删除这里不做讲解，感兴趣可以参考：《算法导论》或者《STL源码剖析》。

红黑树与AVL树的比较

红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用

  1. C++ STL库 —— map/set、mutil_map/mutil_set。
  2. Java 库。
  3. linux内核。
  4. 其他一些库。

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

解决 rosdep 无法初始化问题 统信 UOS 操作系统介绍 CF2031D 题解 全球及中国金融担保市场营销策略与渠道动态建设报告2022版 DNS批量解析管理软件有什么用 AI智能检测视频分析网关安全帽检测识别监控解决方案

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989