算法导论笔记：13-04红黑树以及其他平衡树_加权平衡树

一：红黑树的其他特点

       1：对于一颗用RB-INSERT插入n个结点形成的红黑树，如果n>1，则该树至少有一个红结点。

 

       2： 如果用RB-INSERT将节点x插入一颗红黑树，然后接着用RB-DELETE删除，则结果红黑树是否和原始红黑树一样？

       不一样，因为RB-INSERT可能会进行旋转而改变树的结构，比如;

 

 

二：AVL树

       AVL树是比红黑树还要平衡的二叉搜索树，他满足的性质是：任意结点的左子树和右子树的高度差的绝对值不超过1。

 

       定义结点的平衡因子BF为：该节点左子树的高度减去右子树的高度。在AVL树上，任何结点的BF值只可能是-1, 0, 1。如果有一个结点的平衡因子的绝对值大于1，则就不是AVL树。如下图分别描述了AVL树和非AVL树：

 

       证明：一颗有n个结点的AVL树，它的高度为O(lg n)

       证明：如果高度为h的AVL树，至少包含个结点。所以， = 1， ，因为是AVL树，所以 = + + 1。这个和斐波那契类似，根据斐波那契堆的性质，所以有：一颗有n个结点的AVL树，它的高度为O(lg n)。

 

       AVL树的插入和删除操作有可能会破坏AVL树的性质，也就是使得某个结点的BF值由1 -> 2，或者是 -1 -> -2。总共有4种可能使得这样的情况发生，在左子树插入可以使得BF值由1 -> 2，在右子树插入可以使得BF值由-1 -> -2。其中两种情况是左右对称的，所以只看在左子树插入的情况，如下图：

图1

       如果当前BH(A) = 1，添加新的结点后，使得BH(A) = 2，则该新节点一定加在了左子树，也就是bl或者br中。

       我们只查看改变AVL性质的最小情况，所以BH(B) = 0,如果BH(B) != 0，则将新节点插入B子树中高度较小的子树，只会使BH(B) = 0，而不会改变A的BH值。如果将新节点插入B子树中高度较大的子树，则会使BH(B) = 2/-2，所以，不考虑BH(B) != 0的情况。

 

 

1：LL

       参见图1，如果新节点插入bl，则是LL型。 根据之前的讨论，在加入新节点之前，有BH(A) = 1， BH(B) = 0。所以可以得到下面的性质：

       h(bl) = h(br) =h(C)

       整个分支的高度为h(br)+2

 

       插入后h(bl)的值加1。此时，只需要对A结点进行右旋即可，得到下图：

图2

       因原来有h(bl) = h(br) = h(C)，而且h(br)和h(C)没有发生变化，h(bl)的值加1，所以：BH(A) = 0，BH(B) = 0。整个分支的高度为h(br) + 2。所以，整个分支的高度没变。因而不需要调整之上的分支。

 

2：LR型

       首先对图1进行扩展，得到图3：

 

图3

       如果新节点插入br，则是LR型，根据之前的讨论，在加入新节点之前，有BH(A) = 1， BH(B) = 0， BH(br) = 0。所以，可得下面的性质：

       h(brl) = h(brr)

       h(bl) = h(C) = h(br) = h(brl)+1 = h(brr)+1

       整个分支的高度为h(bl)+2

 

       这种情况下，不管新节点插入brl还是brr，都是进行相同的操作：首先是对B进行左旋，得到下图：

图4

然后对A进行右旋，得到下图：

图5

       原来的性质是：

       h(brl) = h(brr)

       h(bl) = h(C) = h(br) = h(brl)+1 =h(brr)+1

       整个分支的高度为h(bl)+2

       如果新节点插在了brl，所以h(brl) = h(brl) +1。

现在，因h(brr)+1 = h(C)，所以，BH(A)= -1;

因h(bl) = h(brl)，所以，BH(B) = 0;

因h(bl) + 2 = h(C) + 2，所以，BH(br)= 0；

符合AVL的性质，同时，整个分支的高度为h(bl) + 2，所以，整个分支的高度不变。

 

       如果新节点插在了brr，所以h(brr)= h(brr) + 1。

现在，因h(bl) = h(brl) + 1，所以，BH(B)= 1;

因h(C) = h(brr)，所以BH(A)=0;

因h(bl) + 2 = h(C) + 2，所以，BH(br)= 0；

符合AVL的性质，同时，整个分支的高度为h(bl) + 2，所以，整个分支的高度不变。

 

       如果BH值由-1变为了-2，则跟上面的情况对称，分别为RR和RL，进行的操作也对称，不再赘述。

 

 

三：Treap

1：概念：

       如果一个二叉搜索树节点插入的顺序是随机的，这样我们得到的二叉搜索树大多数情况下是平衡的，即使存在一些极端情况，但是这种情况发生的概率很小，所以我们可以这样建立一棵二叉搜索树，而不必要像AVL那样旋转，可以证明随机顺序建立的二叉搜索树在期望高度是O(log n)，但是某些时候我们并不能得知所有的待插入节点，打乱以后再插入。所以我们需要一种规则来实现这种想法，并且不必要所有节点。也就是说节点是顺序输入的，我们实现这一点可以用Treap。

 

       Treap=Tree+Heap。Treap本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap记录一个额外的数据，就是优先级。

       Treap在以key构成二叉搜索树的同时，还按优先级来满足最小堆的性质(在这里我们假设节点的优先级小于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。

 

       Treap有一个特性，就是每个子树的形态在优先级和key唯一确定的情况下都是唯一的，不受其他因素影响。这是因为：根节点一定是优先级最小的元素，这是唯一确定的，左子树是key比根小的元素集合，右子树是key比根大的元素集合，所以，左右子树的集合中的元素是确定的。而这些集合中，再找出优先级最小的元素，就分别是左右子树的根了。然后依次推理下去，所以，对于一组元素，如果key和优先级都唯一确定的话，那么Treap也是唯一确定的。

      

       根据上面的性质，可以看出，Treap相当于先把所有节点按照优先级排序，然后依次插入，又因为优先级在插入的时候，是随机给出的，所以实质上就相当于以随机顺序建立的二叉搜索树，所以Treap的期望高度为O(logn)。

 

2：插入

       给节点随机分配一个优先级，和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比父节点小就旋转，如果当前节点是父节点的左儿子就右旋，如果当前节点是父节点的右儿子就左旋。

 

       由于旋转是O(1)的，最多进行h次(h是树的高度)，插入的复杂度是O(h)的，在期望情况下h=O(log n)，所以它的期望复杂度是O(log n)。

 

3：删除

       有了旋转的操作之后，Treap的删除比二叉搜索树还要简单。因为Treap满足堆性质，所以我们只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最小的儿子，向与其相反的方向旋转，直到那个要删除的节点被旋转到了叶节点，然后直接删除即可。删除最多进行O(h)次旋转，期望复杂度是O(log n)。

 

关于Treap的其他内容参见论文《平衡树Treap的方法与应用》。