手撕红黑树 | zPytC

type

status

summary

date

slug

1.红黑树的性质

每个节点不是红色就是黑色

根节点是黑色的

如果一个节点是红色的那么他的两个孩子节点就都是黑色的（任何路径没有连续的红节点

对于每一个节点从他到他所有叶子节点的路径中所包含的黑色节点数目是一样的

每一个叶子节点都是黑色的（此处的叶子节点指的是空节点）

（1）请看这张图请问它有多少条路径？

其实他有12条路径（从根到空节点算一条路径）

（2）那为什么满足上述条件就能形成红黑树的特点呢（红黑树保证了没有一条路径能比其他一个路径长两倍，所以红黑树是接近平衡的。）？

就是他的性质中每条路径中的黑节点数量必须相同

（3）再次思考一下，他的最短路径？最长路径？

其实最短路径就是全黑（父节点只有一个儿子），最长其实就是红黑交替，但是又要保持他的每条路径中黑节点数目相同其实就是保证了在最短路径下其他路径最多只能比它多一个红节点，这样就实现了红黑树保证了没有一条路径能比其他一个路径长两倍

📎

这里我来解答一下为什么我觉得红黑树比AVL树更优秀的原因：

如果说向AVL树中插入了1000值

他的高度就是log_2 N，他是最大高度差不超过一

如果是向红黑树中插入了1000个值，并且他是最长路径不超过最短路径的2被，那就假设红黑树高度是AVL树的两倍

那么就是2log_2 N

插入一千个值其实对于AVL树来说就是搜索10次，红黑树就是搜索20次，

那如果是插入了十亿个值对于AVL树来说就是搜索三十次，而红黑树来说就是搜索60次对于现在的cpu来说其实搜索30次还是60次是基本上·没有什么差别的，并且AVL树在实现高度差的时候需要进行大量的旋转从而牺牲了一部分性能

2.红黑树的实现

那如果插入的红节点的parent也是红节点那该做什么调整才能使得，红黑树仍然满足红黑树的性质呢？

如果父亲是红节点，并且uncle也是红节点，那么父亲和uncle都变为黑色，grandfather变为红色，如果grandfather是根节点那么grandfather就变味黑，如果不是，那就继续看grandfather的父亲和uncle继续更新直到更新到grandfather

那如果不存在uncle，这个时候就需要进行旋转来调节

对于红黑树插入之后来说其实就是三种大情况

（1）uncle存在且为红

（2）uncle不存在

（3）uncle存在且为黑

所以红黑树插入处理需要观察uncle，如果uncle是红，那么就变黑，并且继续向上变化

如果uncle不存在或者存在且为黑，那么就是旋转加上变色

3.三种插入情况的解决方式

(1)cur为红，p为红，g为黑，u存在且为红

调整方式：p变为黑，u变为黑，g变为红，但是如果g本身就是root（parent为nullptr）那么需要将g调整为黑，

如果g是子树，那么g肯定就有双亲，将g作为cur继续向上调整

（2）p为红，g为黑，u不存在

这个时候就需要旋转+变色了

（3）最为麻烦的就是u存在且为黑

⚙

细讲旋转（rotate）：其实就是发现了某一边过高或者需要调整讲过高或者需要调整的那一边中的某一个节点作为旋转的支点，进行旋转调整，所以想要用好旋转就需要准确的找到旋转的支点和方向

4.实现红黑树

定义IsBalance函数

如何才能判断红黑树是否是平衡的呢

先来回顾一下红黑树的几条性质：

1.根节点必须是黑色

2.最长路径不超过最短路径的2倍

3.不存在连续的红色节点

4.每条路径上的黑色节点数量相同

第一个其实能很好的验证，第二个其实是不能通过很好的方式去实现验证的，因为很难确保或者找到哪一个才是最短路径，第三个其实只需要一直验证父亲和儿子是否都是红色节点就好了，第四个才是在能验证中最难验证的一个：

1.红黑树的性质

2.红黑树的实现

3.三种插入情况的解决方式

4.实现红黑树

PytC

交流频道

加入我们的社群讨论分享