MIT算法导论十 平衡搜索树一

平衡搜索树（BST），所有操作的Θ(lgn)
（平衡树有可能不是二叉树，这一节只讨论二叉树的情况）

有多重平衡树结构
- AVL trees
- 2-3 trees
- 2-3-4 trees
- B trees
- Red-black trees
- Skip lists
- Treaps

---

红黑树 Red-black trees

BST的一种
- 每个结点有一个色域，要么为黑结点，要么为红结点
- 根节点和叶子结点都为黑结点
- 每个红结点的父亲都为黑结点，即不可能出现两个红色结点相连的情况
- 从根节点到任意叶节点的路径中的黑色结点数目相等，这个数目也称为黑高度

由以上性质，可以保证红黑树的高度为O(lgn)

Example.

证明

将红黑树的所有红结点，都与其父节点（黑）合并，可以得到一颗2-3-4 tree（即每个结点的子节点数目为2~4个）
并且所有节点的高度都是黑节点的高度，也就是所有叶子节点有相同的深度，意味着树是平衡的

假设整棵树高度为h，那么叶子结点数应为h²~h⁴
原红黑树的叶子结点个数为带键值结点个数n+1（平衡树叶子节点的数量总是内部节点的数量加1）
leaf = n+1 | n是key的数量
=> h'² <= n+1 <= h'⁴
=> h' <= lg n+1
树最高情况是红黑相间的时候，因此其高度最高只有h <= 2h' <= 2lg n+1
树的高度为O(lgn)

树操作

红黑树的查询操作和普通BST一样，删除和插入操作则相对复杂
我们要保证红黑树的性质，因为这些性质是红黑树为平衡树的保证，能够保证红黑树的高度为Olgn，这样红黑树的基本操作都可以保证在O(lgn)的时间复杂度内完成

为了保持红黑性需要三种操作
- BST操作
- 改变节点颜色
- 利用旋转改变节点关系

旋转
保持二叉搜索树的性质，并且只需要常数时间

α<X<β<Y<γ

LEFT_ROTATE(T,x)
   y = right[x]           //获取右孩子
   rihgt[x] = left[y]     //设置x的右孩子为y的左孩子
   if left[y] != NIL
       then parent[left[x]] = x
    parent[y] = parent[x]  //设置y的父节点为x的父节点
    if parent[x] == NIL
       then root[T] = y
       else if x==left[parent[x]
              then left[parent[x]] = y
              else  right[[parent[x]] = y
    left[y] = x            //设置y的左孩子为x
    parent[x] =y

插入
插入一个新结点的过程是在二叉查找树插入过程的基础上改进的，先按照二叉排序的插入过程插入到红黑树中，然后将新插入的结点标记为红色（插入黑色会影响树的深度，很容易破坏红黑性质，标记红色只可能影响性质3）。然后调整结点并重新着色，使得满足红黑树的性质。

Insert

如果每次插入新的结点z导致红黑树性质被破坏，最多只有一个性质被破坏，并且不是性质2就是性质4。违反性质2是因为z是根且为红色，只需要改变跟节点的颜色，违反性质4是因为z和其父节点parent[z]都是红色的。

以下分析的大前提是z的父结点是红色，建立在z的父结点是左孩子基础上（相反情况类似，不做分析）

插入后有多种情况
情况1：z的叔叔结点y是红色的
此时父节点parent[z] A和叔叔节点y D都是红色的，解决办法是将z的父节点parent[z] A和叔叔结点y D都变为黑色，将z的祖父结点parent[parent[z]] C变为红色，然后从祖父结点parent[parent[z]] C继续向上判断是否破坏红黑树的性质

Case1

情况2：z的叔叔y是黑色的，而且z是右孩子
情况3：z的叔叔y是黑色的，而且z是左孩子

情况2和情况3中叔叔节点y D都是黑色的，通过z是左孩子还是右孩子进行区分的。可以将情况2通过旋转为情况3。情况2中z是右孩子，旋转后成为情况3，使得z变为左孩子，可以在parent[z]结点出使用一次左旋转来完成。
无论是间接还是直接的通过情况2进入到情况3，z的叔叔y总是黑色的。在情况3中，将父节点parent[z] B着为黑色，祖父节点parent[parent[z]] C着为红色，然后从祖父节点parent[parent[z]] C处进行一次右旋转。

Case2和Case3

RB_INSERT(T,z)
  y = NIL
  x =root(T)
  while x != NIL
       do y=x
           if key[z]<key[x]
             then x=left[x]
             else  x=right[x]
  parent[z] = y
  if y =NIL
     then root =z
     else if key[z] < key[y]
            then left[y] =z
            else  right[y] =z
   left[z] = NIL
   right[z] =NIL
   color[z] = RED          //新插入结点标记为红色
   RB_INSERT_FIXUP(T,z)    //进行调整，使得满足红黑树性质

RB_INSERT_FIXUP(T,z)
  while color[parent[z]] = RED
      do if parent[z] == left[parent[parent[z]]]
            then y = right[parent[parent[z]]]
                if color[y] == RED    //情况1，z的叔叔为红色
                   then color[parent[z]] = BLACK
                        color[y] = BLACK
                        color[parent[parent[z]]=RED 
                        z= parent[parent[z]]
                else if z == right[parent[z]]    //情况2，z的叔叔为黑色，z为右孩子
                        then z = parent[z]
                             LEFT_ROTATE(T,z)
                color[parent[z]]=BLACK    //情况3，z的叔叔为黑色，z为左孩子
                color[parent[parent[z]] = RED
                RIGHT_ROTATE(T, parent[parent[z]])
      else (same as then clause with “right” and “left” exchanged)
color(root(T)) = BLACK; //将根结点设置为黑色