红黑树

平衡二叉树: AVL树 红黑树 伸展树(SplayTree) 树堆(Treap)

学习数据结构和算法,要学习的是 它的由来/特性/使用场景/解决的问题.

这已经足够了.

平衡二叉树

平衡二叉树:任意一个节点左右子树高度相差不能大于1

平衡二叉树的初衷:解决普通二叉查找树树结构”不平衡”时,出现时间复杂度退化的情况

“近似平衡”: 树看起来”比较对称”,”比较平衡”,不出现左右子树一边高一边矮的情况.

从而避免性能退化得太严重

AVL树

最先被发明的平衡二叉树 AVL树,是严格符合定义,高度平衡的二叉查找树.

AVL树 增加和删除操作都可能进行一次或多次 “AVL旋转”,实现树的重新平衡

AVL树 节点的左右子树高度差称为 平衡因子,1/0/-1被认为是平衡的.

Adelson-Velsky and Landis Tree 人名命名的

AVL树高度平衡,查找效率非常高,但是为了维持这种平衡付出了更多代价

每次 插入 删除都要做调整,复杂耗时.频繁进行插入删除的操作集合并不适用.

但很多平衡二叉树并没有严格符合 平衡二叉树的定义.例如,开篇中的后三种树.

无需完全符合二叉树定义,尽量平衡,保证高度仍是对数量级,

就仍可以说是合格平衡二叉树.

红黑树

BlackRedTree,一种不严格的平衡二叉树.

要求:

1. 根节点黑色

2. 叶子节点黑色空节点,不储存数据(简化代码)

3. 红色节点不能相邻

4. 任意节点 到达其可到达的 任意叶子节点 经过的黑色节点数目 相同

以上要求,使红黑树达到了下面的效果.

1. 去掉红节点后的纯黑树高度低于 log2n(毕竟去掉了一些节点)

2. 加上红节点,由于红节点不能连续,所以最长路径不超过 2log2n(一红一黑)

也就是说,红黑树高度近似不超过 2log2n.

红黑树高度 比高度平衡的 AVL树 仅仅大了一倍,所以性能上不差很多.

这样推导的结果不够精确,实际上红黑树性能更好

红黑树的插入 删除 查找 各项操作都相对 性能稳定,工业级应用更倾向.

红黑树的演变,红黑的含义