本章节展示的红黑树都会省略NULL节点。
一、红黑树
1.1. 基本概念
红黑树(Red Black Tree)也是一种自平衡的二叉搜索树,以前也叫做平衡二叉B树(Symmetric Binary B-tree)。
红黑树必须满足以下 5 条性质:
- 根节点是BLACK;
- 节点是RED或者BLACK;
- 叶子节点(也叫做外部节点或空节点,注意和二叉树的叶子节点概念不太一样)都是BLACK;
- RED节点的子节点都是 BLACK;
- 推理1:RED节点的parent(父节点)都是BLACK
- 推理2:从根节点到叶子节点的所有路径上不能有2个连续的RED节点
- 从任一节点到叶子节点(空节点)的所有路径都包含相同数目的BLACK节点。
注意:红黑树会把度为0或者1的节点,“添加”空节点后变为度为2的节点(变成了真二叉树,即节点的度只有0或2),空节点是假想的,仅仅是为了便于理解红黑树的性质,实际代码中不会增加空节点。
请问下面这棵是红黑树么?
解答:不是,因为不满足红黑树性质5(从任一节点到叶子节点(空节点)的所有路径都包含相同数目的BLACK节点),例如55-38-null(右子树)
有2个BLACK节点,而其他路径都有3个BLACK节点。
红黑树是否计算空节点,取决于代码怎么写。如果空节点参与计算个数,就全部参与;如果不参与计数,则全部空节点都不计。
1.2. 红黑树的等价变换
- 红黑树和4阶B树(2-3-4树)具有等价性
- BLACK节点与它的RED子节点融合在一起,形成1个B树节点
- 红黑树的BLACK节点个数与4阶B树的节点总个数相等
注意:有些资料用2-3树与红黑树进行类比,这是极其不严谨的,2-3树并不能完美匹配红黑树的所有情况。
1.3. 红黑树 vs 2-3-4树
红黑树的黑节点和它的红色子节点合并成一个节点后就是一颗4阶B树。并且合并后的节点有以下几种情况:
1. 红黑红:
2. 黑红:
3. 红黑:
4. 黑:
思考:如果上面的四种示例最底层的BLACK节点是不存在的,在B树中是什么样的情形?
解答:整棵B树只有1个节点,而且是超级节点。
二、操作(代码)
为了方便操作红黑树节点,我们需要增加节点几个概念:
sibling
:兄弟节点- 例:17和33,25和46
parent
:父节点- 例:17和33的父节点是25,50的父节点是46
uncle
:叔父节点(parent
的兄弟节点)- 例:25是50的叔父节点,46是17的叔父节点
grand
:祖父节点(parent
的父节点)- 例:38是17、33、50的祖父节点
辅助函数:
1 | // 红黑树 |
注意:B树仅仅是为了辅助理解红黑树。
三、平衡及对比
3.1. 红黑树的平衡
为何那5条性质,就能保证红黑树是平衡的?那5条性质,可以恰好保证红黑树等价于4阶B树,而B树高度又比较矮,所以整体上红黑树是平衡的。
疑问:B树展开后的红黑树高度就会变高,还平衡么?二叉搜索树平衡的概念是组成二叉树的高度越小就越平衡。所以高度只要不是太高(甚至退化成一个链表),就可以认为达到了平衡。
相比AVL树,红黑树的平衡标准比较宽松:没有一条路径会大于其他路径的2倍(最短路径高度是B树的高度,而最长的路径是比最短的路径多红色,如果每个黑色都有一个红色子节点,最长路径肯定是最短路径的2倍,黑-黑 < 黑-红-黑-红
)。
红黑树是一种弱平衡(相对AVL树)、黑高度平衡(只计算黑节点的高度时,高度都是一样的)。
红黑树的最大高度是2 ∗ log2(n + 1)
,依然是O(logn)
级别。
3.2. 平均时间复杂度
搜索:O(logn)
添加:O(logn)
,O(1)
次的旋转操作
删除:O(logn)
,O(1)
次的旋转操作
3.3. AVL树 vs 红黑树
3.3.1. AVL树
平衡标准比较严格:每个左右子树的高度差不超过1。
最大高度是1.44 ∗ log2 n + 2 − 1.328
(100W个节点,AVL树最大树高28)。
搜索、添加、删除的复杂度都是O(logn)
,其中添加仅需O(1)
次旋转调整、删除最多需要O(logn)
次旋转调整。
3.3.2. 红黑树
平衡标准比较宽松:没有一条路径会大于其他路径的2倍。
最大高度是2 ∗ log2(n + 1)
(100W个节点,红黑树最大树高40)。
搜索、添加、删除的复杂度都是O(logn)
,其中添加、删除都仅需O(1)
次旋转调整。
3.3.3. 选择
搜索的次数远远大于插入和删除,选择AVL树。
搜索、插入、删除次数几乎差不多,选择红黑树。
相对于AVL树来说,红黑树牺牲了部分平衡性(牺牲高度)以换取插入/删除操作时少量的旋转操作,整体来说红黑树性能要优于AVL树。
红黑树的平均统计性能优于AVL树,实际应用中更多选择使用红黑树。
3.4. BST vs AVL Tree vs Red Black Tree
一棵树有以下节点:10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96。分别对比二叉搜索树、AVL树、红黑树。
二叉搜索树:
AVL树:
红黑树:
红黑树是在AVL树基础上优化后的版本。