Algorithm - RB-Tree

Created by : Mr Dk.

2019 / 11 / 13 21:56

Nanjing, Jiangsu, China

About

众所周知，二叉搜索树能够提升查找的性能：结点的左子树下所有结点都比该结点小，右子树下所有结点都比该结点大。理想情况下，每次砍掉了一半需要搜索的对象，时间复杂度为 O(log(n))。但树的失衡将导致时间复杂度的退化为 O(n)，所以应当采用一些手段维护二叉搜索树的平衡。

AVL

平衡二叉树。在定义上，要求所有子树的高度差不超过 1，是一种 严格定义 的平衡二叉树：

  • 一旦不满足条件，就要进行旋转
  • 旋转较为耗时
  • 维护代价高

因此 AVL 更适合插入和删除较少，而查询较多的情况，据说在 Windows NT 内核中广泛存在。

RB-Tree

红黑树 是一种比较常见的数据结构，使得对数据的搜索、插入、删除都能保持 O(log(n)) 的时间复杂度。C++ STL 的 map、JDK 中的 TreeMap 等，都是使用红黑树实现的。红黑树是 相对平衡 的，或者说是 弱平衡 的，平衡条件没有 AVL 那么苛刻，因此 RB-Tree 的高度可能比 AVL 略高些，但是显著减少了因维护平衡性而旋转的次数。所以在搜索、插入、删除操作都较多的情况下性能较好，得到了广泛的使用。

Definition

RB-Tree 也是一种二叉搜索树，但所有结点额外维护各自的颜色：要么是红，要么是黑。RB-Tree 的规则：

  1. root 结点为 黑色
  2. 任意从 root 到叶子结点的路径不包含 连续 的 红色结点 (即，红结点的子结点肯定是黑结点)
  3. 任意从 root 到叶子结点的路径上黑色结点总数相同 (以此保证平衡性)

根据以上定义，最不平衡的一种情况，最长路径也不会超过最短路径的两倍。😨

  • root(黑) -> 黑 -> 黑
  • root(黑) -> 红 -> 黑 -> 红 -> 黑 -> 红

关于查找，和普通的二叉搜索树的方法一致，复杂的点主要在于插入和删除。插入和删除会破坏红黑树的定义，导致需要进行旋转；而旋转时，又会造成结点颜色不符合定义，要对结点进行重新着色。在插入结点时，为了方便，一般默认将插入的结点设置为红色，因为插入黑色肯定会破坏定义导致旋转。

Modification

具体插入和删除的算法没有看。很久之前写过 AVL 的都给我整得够呛，主要就是递归的旋转 + 变色吧。网上有一个 alibaba 的老哥写得不错：

  • https://www.cnblogs.com/fanzhidongyzby/p/3187912.html
  • https://github.com/fanzhidongyzby/RBTree