第九讲

确定性构造平衡树算法

红黑树（期中不考察具体的插入与删除的操作）

性质：

（1）把添加空结点，直至除空结点外所有结点都具有两个儿子

（2）结点具有两种颜色：红与黑

（3）根结点与空结点是黑色的

（4）黑色条件：任何一条从根结点到叶子结点的路径包含的黑色结点个数相同

（5）红色条件：任何两个红色结点不能构成父子关系

为什么红黑树具有好的高度？

黑高度：从一个结点向下走直到某个叶子结点，路上经过最多黑色结点的数量为这一结点的黑高度。

叶子结点的黑高度均为0

断言：若红黑树的黑高度为\(h\)，则整棵树的结点个数\(\ge 2^h-1\)

考虑数学归纳法：\(h=0\)时显然

当\(h>0\)时，根结点\(x\)有两个孩子\(y,z\)，\(s(x)\ge 1+s(y)+s(z)\ge 2^h-1\)，归纳得证。

插入操作

（1）执行正常的二叉搜索树插入找到插入位置

（2）将带插入结点置为红色

（3）如果其父亲为黑色，直接插入即可

（4）否则，将其插入，将其祖父结点染成红色，父亲结点染成黑色，对其父亲结点进行旋转

删除操作

（1）可将删除问题归结为删除具有至少一个空孩子结点的结点\(z\)的问题

（2）若的颜色是红色，是简单的

（3）若的颜色是黑色且它的孩子结点颜色是红色，是简单的

（4）若的颜色是黑色且它的孩子结点颜色是黑色，

Splay 树