Red Black Tree (Draft)
本文处于草稿中。。。
定义:红黑树利用特征标记决定高度的自平衡二叉搜索树,具有额外的数据决定其节点为黑或红节点。每一条从单一节点到叶子结点的路径都有相同数目的黑色节点。利用此特性,保持树高为$O(lg\ n)$。
pre:平衡树:空树或其左右两个子树高度差相对小的二叉搜索树。
正确性特性:
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色(叶子是NIL节点)。
- 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
- 为便于实现且解决边界问题,利用单一 $T.nil$ 节点作为空节点,并且将类似于原始二叉搜索树中的空指针指向$T.nil$。$T.nil$可以作为辅助节点,为后续插入删除做辅助。
- 每个节点包含:color, key, right, left, p指针。
解释:
性质2保证了根节点为黑色,但并不是必须的。(ex13.1-3)保证红色节点不可连续,而且单一路径黑节点数目相同,树就可以实现平衡。
NIL节点实现了,所有的有数据节点都为内部节点。
性质4决定了红色节点不可连续,但对于黑色节点没有限制。只要树的简单路径黑节点数目相同,就保证了4的正确性。
这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。(ex13.1-5)
说明:假设单一路径中全部节点为黑色,由性质4,另一单一路径的全部节点最多为红黑相间。因此不可以超过两倍。
树高的证明
根据性质4,5,定义辅助函数“树的黑高” $bh(x)$ 。利用说明任何以 $x$ 为跟的红黑树都有至少 $2^{bh(x)}-1$ 个内部节点。
证明:数学归纳法
设:根为x的树高为h。
$x=0$ 时, $2^{bh(x)}-1=0$ ;
假设x为根的树有2个子代,则:取决于当前子树的子代为黑或者红,黑高为bh(x) 或者 bh(x)-1;
// 这句有啥意义?
假设 $x’=x-1$ 黑高为 $2^{bh(x’)}-1$ 成立,则:
$\because x’=x$ 时: 减去根的黑节点,左右子树:$h’=2^{bh(x)-1}-1$,
$\therefore 2h’+1=2^{bh(x)}-1$ (1)