红黑树

红黑树(Red-Black Tree)简称 R-B Tree,它是一种不严格的平衡二叉查找树,它的定义是不严格符合平衡二叉查找树的定义的,也就是任何节点的左右子树高度相差可能超过 1

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色


性质:

1.节点是红色或黑色

2.根是黑色

3.所有叶子都是黑色(叶子是NIL节点,即不存储数据)

4.每个红色节点必须有两个黑色的子节点。(即不能有两个连续的红色节点)

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


AVL树在失去平衡后需要重新保持平衡,而红黑树是在失去上述性质后,需要通过 变更颜色 + 旋转 来重新保持上述性质,只要能保持上述性质,这棵树就能保持相对平衡,查询效率会很高

实现可以参考:

wiki-red-black-tree


红黑树与AVL树对比:

1.红黑树任何不平衡都能在都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多

2.插入节点导致树失衡的情况,AVL和RB-Tree都是最多两次树旋转来实现重新平衡

3.删除节点导致失衡,AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡,旋转的量级为O(logN),而RB-tree 最多3次,时间复杂度为O(1)

红黑树可能存在的,最不平衡的情形(即最不平衡),即一边尽可能少的红色,另一边尽可能多的红色节点。

不算上nil节点,当黑色节点数为n,最长可能路径上的节点数为2n,所以可以得出红黑树从根节点到叶节点最长路径跟最短路径相差不大于2倍


上述最坏情况通过新增一些限制条件可以得到优化

总结:优先选择红黑树,除非删除插入非常少,大多是查询等特殊情况可考虑使用 AVL


上一篇: AVL树
下一篇: B树和B+树
作者邮箱: 203328517@qq.com