红黑树 学习笔记1 - 基本性质

本系列为算法导论 第13章 红黑树 学习笔记

RB_Tree是一颗BST，满足：
1. 结点颜色为红或黑。
2. 根结点为黑色。
3. 每个叶结 (NIL) 点是黑色。
4. 不存在2个连续的红色结点
5. 对于任一结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

先做一些人为的约定：
$\quad$树根的高度为1；
$\quad$叶结点指的是 $NIL$，内部结点指的是红黑树中出现的结点；
$\quad$黑高 $bh(x)$不包含 $x$点，但是包含 $NIL$；

为方便起见，我们把所有 $NIL$都用一个哨兵结点来代替，如图：

定义：
$\quad$黑高： 从某个结点 $x$出发(不含该结点)，到达一个叶结点的任一一条简单路径上的黑色结点个数称为该结点的黑高，记为 $bh(x)$。
$\quad$红黑树的黑高：其根结点的黑高。

引理 13.1
$\quad$一颗有n个内部结点的红黑树的高度至多为$2log(n+1)$。
proof：
$\quad$先证明一个结论：以任一结点x为根的子树中至少包含 $2^{bh(x)}-1$个内部结点。
归纳法易证。
$\quad$另一方面，设 $h$为树的高度，则根的黑高 $bh(root) \ge [{\frac{h-1}{2}}]+1 \ge \frac{h}{2}$，得证。

课后习题：时间比较紧，最后2题没怎么做，到时候再说
13. 1-1
$\quad$黑高为2：2，4层为红。
$\quad$黑高为3：某层为红。
$\quad$黑高为4：无红结点。
$\quad$
13. 1-2
$\quad$均不是红黑树
$\quad$
13. 1-3
$\quad$是
$\quad$
13. 1-4
$\quad$
$\quad$
13. 1-5
$\quad$易知 $1+[\frac{l_{max}-1}{2}]\le bh(x)\le l_{min}$
$\quad$
13. 1-6
$\quad$在一颗高为 $h$的红黑树中，
$\quad$$\quad$内部结点最多有多少个？$2^k-1$
$\quad$$\quad$最少可能有多少个？
$\quad$$\quad$$\quad$我写了个递推 $x_{n+1}=x_n+x_{\lceil \frac{n+1}{2}\rceil}+1$
$\quad$$\quad$$\quad$不保证正确，答案也懒得找了，目测这个解起来颇有难度。
$\quad$
13. 1-7 —过两天再看
$\quad$
$\quad$
$\quad$