13.1 红黑树的性质
红黑树是，在二叉搜索树基础上，加了一个叫“颜色”的存储位，可以是“RED”或“BLACK”。通过“对于每个结点，从该结点到后代叶子结点的简单路径上，均包含相同数目的黑色结点”这个规则，确保没有一条路径会比其它路径长出 2 倍，因而是近似于平衡的。
树中每个结点包含 5 个属性：color、key、left、right 和 p。如果一个结点没有子结点或父结点，则该结点相应的值为 NIL。我们可以把这些 NIL 视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。
一棵红黑树是满足下面的红黑性质的二叉搜索树：
- 每个结点是红色或黑色
- 根结点是黑色
- 每个叶结点（NIL）是黑色
- 如果一个结点是红色，则它的两个子结点都是黑色
- 对每个结点，从该结点到其所有后代叶子结点的简单路径上，无包含相同数目的黑色结点。
关于红黑树的高度：h <= 2lg(n+1)
搜索的复杂度：O(h)
为了全球处理红黑树代码中的，边界条件，使用一个哨兵来代表 NIL。对于一棵红黑树 T，哨兵 T.nil 是一个与树中普通结点有相同属性的对象。它的 color 属性为 Black，其它属性为任何值
使用哨兵后，就可以将结点 x 的 NIL 孩子裤一个普通结点。为树内每个 NIL 创建一个哨兵结点的话，有些浪费空间，所以用一个哨兵 T.nil 代替所有 NIL
我们通常把注意力放在红黑树的内部结点上，因为他们存储了关键字。
13.2 旋转
在对树进行“插入”或“删除”操作后，可能会违反了红黑树的性质，为了维护这些性质，必须要改变结点的颜色 或 指针结构。
指针结构的修改，是通过“旋转(rotation)”来完成的，这是一种能保持二叉搜索树性质的辟中操作。旋转分为：左旋和右旋。
左旋：把结点 x，放到结点 x的右结点 y的左孩子位置。而结点 x的右结点 y的左孩子，而放到结点 x的右结点位置。
右旋：把结点 y，放到结点 x的左结点 x的右孩子位置。而结点 y的左结点 x的右孩子，而放到结点 y的左结点位置。
第十四章 数据结构的扩张
当现在的标准的数据结构，不能满足我们的需要是地，很少的情况下才创造出一种全新类型的数据结构，一般都是在现有数据结构上进行扩张。相应的，原来数据结构的函数可能也需要修改。（这个时候，我们必须了解函数的过程）
14.1 动态顺序统计
在第 9 章介绍过“顺序统计量的”问题，它的时间复杂度是 O(n)。如果使用红黑树，可以在 O(lgn) 时间内确定任何顺序统计量。
“顺序统计树” T 是在红黑树基础上，再加上一个附加信息 size。它是用来保存“包含以 x 为根的子树(包含x)的(内)结点数”。哨兵的大小为0。
在一“顺序统计树”中，我们并不要求关键字各不相同（上面的图包含了两个21）。为此，我们定义一个元素的“秩”的位置，是指在中序遍历时的输出位置。（后序遍历时，可能先遍历到下面的 21，其它函数内部可能要进行修改，相对中序遍历的程序来说）
什么是秩？就是一个元素所在的位置。英语对应的是 rank，是和矩阵相关的术语。
上面程序要注意的是，如果是位置i大于当前结点的 size 时，在递归调用右子树时，位置i应该是i-当结点size。
这个程序中用 r 来表示当前元素的位置。注意，如果是 y=y.p.right 时，r 这个位置元素应该是“左子树的size + r + 1”。因为 y=y.p.right 的意思是，当前结点是它的父结点的右子树，那么下一个我们要迭代的结点应该是它的父结点，而父结点所在的 r ，左子树是比父结点小的元素的个数，所以应该加上左子树的 size。
对子树规模的维护
在插入和删除后，我们还需要对子树进行维护，让他保持红黑树的性质。维护需要两个阶段：
对由根到叶子的路径上遍历每一个结点 x，都增加 x.size 属性。新增结点的 size 为 1。由于一条遍历的路径上共有 O(lgn) 个结点，所以维护 size 属性的代价为 O(lgn)。
对红黑树结构上的改变仅仅是旋转，旋转次数至多为 2。而且，旋转还会使两个结点的 size 属性失效，所以还需要修改两个结点的 size 属性。因为操作是常数，代价为：O(1)
所以维护的代价为：O(lgn) + O(1) = O(lgn)，和一般红黑树是一样的。
14.2 如何扩张数据结构
下面的步骤是一个一般模式，不要盲目地按照上面给定的次序来执行这些步骤。例如：如果我们不能有效地维护附加信息，那么确定附加信息以及设计新的操作（步骤2和4）就没有任何意义。然后，这个 4 步法可以使读者在扩张数据结构时，目标确定且有条不紊。
选择一种基础数据结构。
确定基础数据结构中要维护的附加信息。
检验基础数据结构上的基础修改操作能否维护附加信息。
设计一些新的操作。
京公网安备 11010502036488号