rbtree

红黑树适用于需要频繁插入, 删除和查找, 且对性能有一定要求, 主要用来存储有序的数据
查找的时间复杂度是 $O(\log N)$.

1. 红黑树的性质

1. 每个结点要么是红色, 要么是黑色
2. 根结点是黑色的
3. 所有叶子都是黑色
   在红黑树中, 值为 NULL 的结点为叶子结点
4. 如果一个结点是红色的, 那么它的叶子结点必须是黑色的
   从每个叶子结点到根结点的所有路径上不能出现两个连续的红色结点
   黑色结点的子结点颜色没有限制
5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

2. 关键特性

- 最多三次旋转达到平衡
    最多三次旋转达到平衡: 插入最多2次旋转达到平衡, 删除最多3次旋转达到平衡
- 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长
    最短的可能路径都是黑色节点, 最长的可能路径有交替的红色和黑色节点. 因为根据性质5所有最长的路径都有相同数目的黑色节点, 这就表明了没有路径能多于任何其他路径的两倍长. 
    插入, 删除和查找都与树的高度成比例. 基于上述理论, 红黑树在最坏情况下也是高效的.

3. RB-Tree vs AVL-Tree

AVL-Tree 与 RB-Tree 的查找时间复杂度都是 $O(\log N)$
AVL-Tree 左右子树最大高度差不超过 1, 是严格平衡
RB-Tree 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长, 且插入/删除操作时最多三次旋转达到平衡
RB-Tree 相对于AVL树来说, 牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作, 保证了稳定的性能, 整体来说性能要优于AVL树

4. Resource

• 红黑树
• 30张图带你彻底理解红黑树
• https://www.jianshu.com/p/ab90c2ec07e4
• https://blog.csdn.net/Beyond_2016/article/details/81202511