一、红黑树的概念
红黑树是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,这句话换个意思就是:红黑树中最长路径不超过最短路径的 2 倍。因而是接近平衡的,而 AVL 树是严格平衡的,这就导致,红黑树的高度会比 AVL 树高一些,但是效率并不会比 AVL 树差。
二、红黑树的性质
-
每个结点不是红色就是黑色。
-
根节点是黑色。
-
如果一个结点是红色,则它的两个孩子结点必须是黑色的。
-
对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。
-
每个
NIL
叶子结点都是黑色的(此处的叶子结点指的是空节点)。
小Tips:第三点决定了一颗红黑树的任何路径没有连续的红色结点。在红黑树中计算路径一定是计算到 NIL
结点。一颗红黑树中的最短路径是全为黑结点的路径,最长路径是一黑一红相间的路径。任意一条路径上黑色结点的占比一定是大于等于
1
/
2
1/2
1/2 的。这就决定了,红黑树中其最长路径中结点个数不会超过最短路径结点个数的两倍。
三、红黑树结点的定义
//红黑树的结点
template<class K, class V>
struct RBTreeNode
{
RBTreeNode(const& pair<K, V> kv = pair<K, V>(), Color color = RED)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(color)
{}
pair<K, V> _kv;//结点中存的值
RBTreeNode<K, V>* _left;//结点的左孩子
RBTreeNode<K, V>* _right;//结点的右孩子
RBTreeNode<K, V>* _parent;//结点的父亲
Color _col;//结点的颜色
};
小Tips:新节点默认颜色是 RED
。这是因为,如果新插入结点的颜色是 BLACK
,那意味着当前路径上新增了一个黑色结点,为了保证二叉树的第四条性质,我们要对这颗红黑树其他的所有路径进行检查,可见新插入结点如果默认是 BLACK
,会存在着牵一发而动全身的影响。而让新插入结点默认是 RED
则不会出现这样的结果。假如新插入结点的 parent
恰好是 BLACK
,那这次插入就没有什么问题。如果新插入结点是 parent
是 RED
,此时需要对这颗红黑树稍作调整。
四、红黑树的插入操作
红黑树是在二叉搜索树的基础上加上平衡限制条件,因此红黑树的插入可以分为两步:
-
按照二叉搜索树的规则插入结点。
-
检测新节点插入后,红黑树的性质是否遭到破坏。
因为新结点的默认颜色是 RED
,因此:如果其双亲结点的颜色是 BLACK
,没有违反红黑树任何性质,则不需要调整;但是当新插入节点的双亲结点颜色为 RED
时,就违反了性质三不能有连在一起的红色结点,此时需要对红黑树分情况来讨论:
约定:cur
为当前结点,parent
为父结点,grandp
为祖父结点,uncle
为叔叔结点。如果 parent
为红那 grandp
一定为黑。所以当前唯一不确定的就是 uncle
,主要分以下三种情况
4.1 情况一:uncle 存在且为红
小Tips:此处看到的树,可能是一颗完整的树,也可能是一颗子树。
解决方式:将 parent
和 uncle
改为黑,grandp
改成红。然后把 grandp
当成 cur
,继续向上调整。
-
如果
grandp
是根结点,将grandp
再改成黑色,本次插入就算结束。 -
如果
grandp
是子树,则其一定也有双亲,且grandp
的双亲如果是红色,需要继续向上调整。
4.2 情况二:uncle 不存在
如果 uncle
结点不存在,则 cur
一定是新插入结点,因为如果 cur
不是新插入结点,则 cur
和 parent
一定有一个结点的颜色是黑色,就不满足性质四:每条路径黑色结点个数相同。
解决方法:直接进行旋转即可。
4.3 情况三:uncle 存在且为黑
叔叔存在且为黑,那么 cur
一定不是新插入的结点,并且 cur
结点原来的颜色一定是黑色,现在看到是红色的原因是因为 cur
的子树在调整的过程中将 cur
结点的颜色由黑色改成了红色。
4.4 插入完整源码
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;//插入成功
}
//找插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first)//小于往左走
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)//大于往右走
{
parent = cur;
cur = cur->_right;
}
else//相等插入不了
{
return false;
}
}
//找到待插入位置了,进行插入
cur = new Node(kv);
cur->_col = RED;
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//检测新结点插入后,红黑树的性质是否遭到破坏
while (parent && parent->_col == RED)
{
Node* grandp = parent->_parent;
if (parent == grandp->_left)
{
Node* uncle = grandp->_right;
if (uncle && uncle->_col == RED)//叔叔存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandp->_col = RED;
//继续向上处理
cur = grandp;
parent = cur->_parent;
}
else //uncle不存在或者存在为黑
{
if (cur == parent->_left)
{
RotateR(grandp);
parent->_col = BLACK;//parent当了根
grandp->_col = RED;
}
else if (cur == parent->_right)
{
RotateLR(grandp);
cur->_col = BLACK;//cur当了根节点
grandp->_col = RED;
}
break;
}
}
else if (parent == grandp->_right)
{
Node* uncle = grandp->_left;
if (uncle && uncle->_col == RED)//叔叔存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandp->_col = RED;
//继续向上处理
cur = grandp;
parent = cur->_parent;
}
else //uncle不存在或者存在为黑
{
if (cur == parent->_right)
{
RotateL(grandp);
parent->_col = BLACK;//parent当了根
grandp->_col = RED;
}
else if (cur == parent->_left)
{
RotateRL(grandp);
cur->_col = BLACK;//cur当了根节点
grandp->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;//根结点始终变黑
return true;
}
private:
//左单旋
void RotateL(Node* parent)
{
++_rotatecount;
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
cur->_left = parent;
if (curleft)
{
curleft->_parent = 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;
}
}
//右单旋
void RotateR(Node* parent)
{
++_rotatecount;
Node* cur = parent->_left;
Node* curright = cur->_right;//此时的情况是curright比cur大,比parent小
parent->_left = curright;
cur->_right = parent;
if (curright)
{
curright->_parent = parent;
}
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (ppnode)
{
cur->_parent = ppnode;
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
}
else
{
_root = cur;
cur->_parent = nullptr;
}
}
//右左双旋
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
RotateR(parent->_right);
RotateL(parent);
}
//左右双旋
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
RotateL(cur);
RotateR(parent);
}
五、红黑树的验证
红黑树的检测分为两步:
-
检测其是否满足二叉搜索树(中序遍历是否为有序序列)。
-
检测其是否满足红黑树的性质(主要是性质三和性质四)。
public:
bool Isblance()
{
if (_root == nullptr)
return true;
//根节点如果不是黑色说明就不是红黑树
if (_root->_col != BLACK)
{
return false;
}
//计算红黑树中任意一条路径上黑色结点的个数作为一个基准值
Node* cur = _root;
int count = 0;
while (cur)
{
if (cur->_col == BLACK)
{
++count;
}
cur = cur->_left;
}
return CheckColour(_root, 0, count);
}
private:
//检查颜色
bool CheckColour(Node* root, int blacknum, int stand)
{
if (root == nullptr)
{
//到这里说明一条路径结束,那么这条路径上的黑色结点数也一定统计出来了
if (blacknum != stand)
{
cout << "当前路径上黑色结点的个数有问题" << endl;
return false;
}
return true;
}
//检查是否出现连续的红色结点
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << root->_kv.first << ":为红色节点,并且孩子结点也是红色" << endl;
}
//统计一条路径上黑色结点个数
if (root->_col == BLACK)
{
++blacknum;
}
return CheckColour(root->_left, blacknum, stand) && CheckColour(root->_right, blacknum, stand);
}
六、红黑树与 AVL 树的比较
红黑树和 AVL 树都是高效的平衡二叉树,增删查改的时间复杂度都是 O ( l o g 2 N ) O(log2^N) O(log2N),红黑树不追求绝对平衡,其只需要保证最长路径不超过最短路径的 2 倍,相对而言,降低了插入过程中旋转的次数,所以在经常进行增删查改的结构中性能比 AVL 树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。红黑树主要会应用在以下几个地方:
-
C++ STL 库----map、set、mutilmap、mutilset。
-
Java 库。
-
Linux 内核。
-
其它一些库。
七、结语
今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,春人的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是春人前进的动力!文章来源:https://www.toymoban.com/news/detail-713413.html
文章来源地址https://www.toymoban.com/news/detail-713413.html
到了这里,关于【C++杂货铺】一文带你走进RBTree的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!