C++ 实现红黑树

编程入门行业动态更新时间:2024-10-11 09:25:54

C++ 实现<a href=https://www.elefans.com/category/jswz/34/1764775.html style= 红黑树"/>

C++ 实现红黑树

红黑树的概念

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

红黑树的性质

每个结点不是红色就是黑色。
根节点是黑色的。
如果一个节点是红色的，则它的两个孩子结点一定是黑色的。
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

红黑树第四条性质的理解：

如上图所示，该红黑树一共存在11条路径，每条路径上黑色节点的数量均为2
路径 1: 13 ----> 8 ----> 1 ----> NULL 黑色节点数量：2
路径 2: 13 ----> 8 ----> 1 ----> 6 ----> NULL (6这个节点的左孩子) 黑色节点数量：2
路径 3: 13 ----> 8 ----> 1 ----> 6 ----> NULL (6这个节点的右孩子) 黑色节点数量：2
··········

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

最短路径的理解：红黑树的节点要么是红色要么是黑色，并且要求**从根节点到空节点路径(以下简称路径)**上的黑色节点的数量一样多，因此我们可以得出结论：当一颗红黑树路径上的黑色节点数量确定时，路径上的节点全部为黑色节点即为路径长度的最小值。

最长路径的理解：因为红黑树要求路径上不能出现连续的红色节点，并且根节点必须为黑色，因此，最长路径的节点颜色变化一定是：黑 --> 红 --> 黑 --> 红 --> 黑 --> 红 --> ·······

综上所述：当一颗红黑树路径上的黑色节点数量确定时，最短路径 * 2 <= 最长路径。
例如(如下图所示)：一颗红黑树路径上的黑色节点数量为 2 ，最短路径：黑 --> 黑最长路径：黑 --> 红 --> 黑 -->红。

红黑树节点定义

红黑树节点存储的数据类型我们依然选择 key-value 的结构，原因是 STL 库中的 map 和 set 底层的数据结构就是红黑树，到时候我们模拟实现 map 和 set 的时候，就要用我们自己实现的红黑树作为他们的底层数据结构。

我们先来思考一个问题：

红黑树应当插入什么颜色的节点？

红黑树的性质4：从根节点出发，到达每一个空节点的简单路径上黑色节点的数量是一样的。

性质4要求路径上的黑色节点数量相同，一条路径上黑色节点数量改变，那么我们必须调整其他路径的黑色节点数量，显然代价十分巨大。

因此，红黑树的应始终插入红色节点，这样就会有两种情况：

新插入节点的父亲是黑色，新节点插入完成。
新插入节点的父亲是红色，只需调整当前路径上节点的颜色使其满足红黑树的性质即可。(如下图所示)

有了上面的知识，我们就可以定义出红黑树的节点，以及怎么书写节点的构造函数了。

#pragma onceenum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _parnet; //父节点指针RBTreeNode<K, V>* _left; //左孩子RBTreeNode<K, V>* _right; //右孩子Color _col; //节点的颜色//构造函数RBTreeNode(const pair<K, V>& kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr)_col(RED) //新插入的节点默认是红色的{}
};template<class K, class V>
class AVLTree
{typedef RBTreeNode<K, V> Node;
public:AVLTree():_root(nullptr) //初始时候根节点为为 nulptr{}private:Node* _root;
};

红黑树的插入

插入一个新的节点，最重要的是插入之后经过变化，使得新插入一个节点之后，整棵树依然满足红黑树的性质。

1：父节点为黑色

这种情况在一开始就探讨过了，新插入的节点父亲为黑色，直接插入就完事儿了！新插入节点的位置在哪里？还是根据二叉搜索树的那里的插入一样。

2：父节点为红色，叔叔存在且为红

这个叔叔节点是什么呢？叔叔节点就是父节点的亲兄弟，你懂我那个意思吧！

这种情况应该怎么做呢？

将父节点，叔叔节点的颜色改为黑色，将祖父节点的颜色改为红色。

插入新的节点之前，该树是一颗红黑树，满足红黑树的性质，其中性质三：如果一个节点是红色的，则它的两个孩子结点一定是黑色的。

这句话说明一条路径上不可能存在连续的两个红色节点。因此，如果父节点的颜色为红色，那么父节点的父节点的颜色一定为黑色。将父节点颜色改为红色，父节点颜色改为黑色，叔叔节点改为黑色，所有路径黑色节点的数量依旧相同。

我们发现经过这样一次变化之后一条路径上出现了连续的红节点(17 和 25)，任然不满足红黑树的性质

我们将红黑树的插入情况进行了分类，每种插入情况都会对应一种调整方式(或者直接完成插入，情况1)，调整后并不一定能完成插入，而是进入了红黑树插入分类的另一种情况(或者与上一次的情况一样，这个例子中就是与上一次的情况相同)。因此，我们需要更新父节点，叔叔节点，祖父以及新插入的节点(cur)，判断更新后处于插入的哪种情况，直到完成插入。

更新方式：令新插入的节点(cur)指向祖父节点，然后找到新的父节点，叔叔节点，祖父节点即可。

我们发现，我们的这个例子就是与上一次变换的方式相同，直接继续进行相同的变换即可。

我们可以看到在向上更新，变换颜色的过程中可能将根节点的颜色搞成红色。根据红黑树的性质二：**根节点是黑色的。**如果出现这种情况就需要将根节点的颜色改成黑色。这样修改之后每条路径上的黑色节点数量都会加一，该树依然满足红黑树的性质。

3：父节点为红色，叔叔存在且为黑

我们先来证明新插入一个节点之后的第一次调整颜色是不可能出现这种情况的！一定是另一种情况经过调整，更新 cur，parent，uncle，grandparent 之后出现的这种情况！

证明：如果新插入的节点的叔叔节点是黑色，因为父亲节点和叔叔节点到根节点的路径是相同的，如果叔叔节点是黑色的，那么，父亲节点必然也是黑色的(根据红黑树的性质思：不同路径上的黑色节点数量相同)，因为是新插入一个节点嘛，父节点之下是不可能有黑色节点的，只能是父节点本身是黑色的。如果父节点是黑色的，在父节点下插入新节点时，我们的插入就直接成功了，不需要调整。

综上所述，在插入新节点的第一次调整节点颜色的时候是不可能出现这种情况的！只能是某种情况进行调整节点颜色之后，出现的这种情况！

我们来看下面的例子：

我们向下面的一颗红黑树中插入一个新节点 28，发现调整颜色的策略和 2 相同，我们就进行相应的颜色调整。

第一次调整之后的结果就是这个样子啦：是不是就满足我们的第三种情况啦！

那么这种情况应该怎么调整节点的颜色呢！！仔细观察你会发现无论怎么调整节点的颜色都比较麻烦，于是我们就要使用旋转啦！那进行什么类型的旋转呢？这就得根据 cur，parent，grandparent 的相对位置来看啦：

旋转想必你在 AVL 树的学习过程中已经了然于胸了！

我们上面的那个例子就是一个左单旋哈：以 grandparent 为旋转点进行左单旋。

第三种情况旋转之后都需要将 grandparent 改为红色，parent 改为黑色哈！

4：父节点为红色，叔叔不存在

在下面的例子中，我们向这颗红黑树中插入了 28 这个节点，满足情况四：父节点为红色，叔叔不存在，和情况三一样，同样需要根据 cur，parent，grandparent 的相对位置确定旋转方式。如下图所示：显然是一个左单旋哈！

左单旋之后的结果：

很明显仅仅是左单旋之后还不满足红黑树的性质，我们需要调整颜色，调整颜色的策略和情况三是一样的：将 grandparent 的颜色改为红色，将 parent 的颜色改为黑色即可。

聪明的你肯定已经发现了情况三和情况四其实是可以合并的啦！合并之后代码看起来就简单多了!

检查一棵树是不是红黑树

原理就是根据红黑树的性质来嘛！我们可以先求出一条路径中黑色节点的数量。然后根据这个基准值来对比其他路径黑色节点的数量！在求其他路径黑色节点的数量时，记得检查是否出现连续的红色节点哦！

代码

#pragma onceenum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Color _col; //节点的颜色RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED) //节点默认的颜色是红色{}
};template<class K, class V>
struct RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){//插入的时候如果根节点为 nullptr, 申请一个节点，将该节点的颜色改为黑色之后作为根节点就行啦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;//调整节点的颜色，使之满足红黑树的性质，只有 parent 的颜色为红才会调整节点的颜色，parent 为黑就直接完成插入了嘛while (parent && parent->_col == RED){//祖父节点Node* grandfather = parent->_parent;//这里根据父节点在祖父节点的位置进行分类，因为我们要确定 uncle 的位置嘛，这样分类代码比较简洁//parent 位于 grandparent 的左侧if (parent == grandfather->_left){Node* uncle = grandfather->_right;// uncle 存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // uncle 不存在 或 uncle 存在且为黑{if (cur == parent->_left){//     g//   p// c//右单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p//		c//左右双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break; //一旦经过旋转调整颜色之后就一定满足红黑树的性质了，直接结束循环}}else // parent == grandfather->_right{//找到叔叔节点Node* uncle = grandfather->_left;// uncle 存在且为红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//       c//左单旋RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// c//右左双旭那RotateR(parent);RotateL(grandfather);//调整颜色cur->_col = BLACK;grandfather->_col = RED;}break; //一旦经过旋转调整颜色之后就一定满足红黑树的性质了，直接结束循环}}}_root->_col = BLACK; // 无论根节点的颜色是否在调整的过程中变成了红色，最后我们都将根节点的颜色变为黑色，方便写代码return true;}//左单旋。逻辑和 AVL 树完全一样就不写注释void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}//右单旋。逻辑和 AVL 树完全一样就不写注释void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}//下面就是检查一颗树是不是红黑树的代码//benchmark 就是那个基准值。blacknum 就是用来统计路径中的黑色节点数量的，请体会传值的妙处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 << root->_kv.first << "出现连续红色节点" << endl;return false;}//递归左右子树return CheckColour(root->_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);}private:Node* _root = nullptr;
};

红黑树的删除

红黑树的删除比插入还要复杂一些，但是难度并没有上升多少！具体过程包含了普通的二叉搜索树的删除，懂的都懂！同样面试的过程中顶多考红黑树的插入呢！有兴趣可以了解了解！

红黑树与AVL树的比较

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