平衡树
动机
对一棵 search tree 进行查询/新增/删除 等动作, 所花的时间与树的高度 h 成比例, 并不与树的容量 n 成比例。 如果可以让树维持矮矮胖胖的好身材, 也就是让 h 维持在 O(lg n), 上述工作就很省时间。 能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做 balanced search tree 平衡树。
旋转 -- 不破坏左小右大特性的小手术
平衡树有很多种, 其中有几类树维持平衡的方法, 都是靠整形小手术:
y x
/ /
x C <==> A y
/ /
A B B C
图中 x 与 y 为 nodes; A, B, C 为一整串的 subtrees。 试想: 如果 x 原来是 y 的 left child; 现在想将 x 变成 parent, 则树的其它部分应如何变化? y 必须变成 right child, 这样才能维持 BST 的特性 -- 左小右大。 至于 x 与 y 以下的其它部分, 可以整串 subtree 一起处理: x 原来的 left subtree (A), 调整后还是 x 的 left subtree; y 原来的 right subtree (C), 调整后还是 y 的 right subtree; 而 x 原来的 right subtree (B), 调整后很自然只有一个地方可以放: 变成 y 的 left subtree。 这些规则都不需要记, 因为如果你希望调整后还维持 BST 左小右大的特性, 这是唯一的答案。 把 x,y 两个值及 A,B,C 三棵 subtrees 内的三串值画在数在线看更清楚:
--------- x --------- y ---------
A B C
这个动作, 称为 right rotation 向右旋转, 或称为顺时针旋转 (clockwise)。 原来的 parent (y) 叫做 pivot, 原来的 child (x) 叫做 rotator。
把上图反过来看, 如果原来的树长得像右图, 想将它改成左图, 则称为 left rotation 向左旋转, 或称为逆时针旋转 (counter-clockwise)。 原来的 parent (x) 叫做 pivot, 原来的 child (y) 叫做 rotator。
数一下旧的 parent 左 subtree 有多少 ndoes? 右 subtree 有多少 nodes? 旋转后新的 parent 左右 subtrees 又各有多少 nodes? 发现右旋的效果会让树的重心往右移; 而左旋的效果则是让树的重心往左移。 如果你的树经历过许多 insert/remove 等等岁月的沧桑, 越长越歪, 在适当的时候对它进行一下旋转手术, 不就可以将它变回矮矮胖胖四平八稳的美丽模样吗? 所以左旋与右旋是几种平衡树共同采用的基本手术; 只不过不同的平衡树, 选择不同的时机/条件来动手术而已。
左子节点与右子节点对称的树就是平衡树，否则就是非平衡树。
非平衡树会影响树中数据的查询，插入和删除的效率。比如当一个二叉树极不平衡时，即所有的节点都在根的同一侧，此时树没有分支，就变成了一个链表。数据的排列是一维的，而不是二维的。在这种情况下，查找的速度下降到O(N)，而不是平衡二叉树的O(logN)。
为了能以较快的时间O(logN)来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡的）。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。
几种主要的二叉平衡树：
红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。
红黑树有两个特征：
(1) 节点都有颜色
(2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。
红黑规则：
1. 每一个节点不是红色的就是黑色的
2. 根总是黑色的
3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）
4. 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。
（空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置）
AVL树，它或者是一颗空二叉树，或者是具有下列性质的二叉树：
(1) 其根的左右子树高度之差的绝对值不能超过1；
(2) 其根的左右子树都是二叉平衡树。
AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。
AVL树插入的C++代码：
template <class T>
ResultCode AVLTree<T>::Insert(AVLNode<T> * &p,T &x,bool &unBalanced)
...{
ResultCode result=Success;
if(p==null)...{//插入新节点
p=new AVLNode<T>(x);
unBalanced=true;
}else if(x<p->element)...{//新节点插入左子树
result=Insert(p->lChild,x,unBalanced);
if(unBanlanced)...{
switch(p->bF)...{
case -1:
p->bF=0;
unBalanced=false;
break;
case 0:
p->bF=1;
break;
case 1:
LRotation(p,unBalanced);
}
}
}else if(x==p->element)...{//有重复元素，插入失败
unBalanced=false;
x=p->element;
result=Duplicate;
}else...{//新节点插入右子树
result=Insert(p->rChild,x,unBalanced);
if(unBalanced)...{
switch(p->bF)...{
case 1:
p->bF=0;
unBalanced=false;
break;
case 0:
p->bF=-1;
break;
case -1:
RRotation(p,unBalanced);
}
}
}
return result;
}
template <class T>
void AVLTree<T>::LRotation(AVLNode<T> * &s,bool &unBalanced)
...{
AVLNode<T> *u,*r=s->lChild;
if(r->bF==1)...{//LL旋转
s->lChild=r->rChild;
r->rChild=s;
s->bF=0;
s=r; //s指示新子树的根
}else...{ //LR旋转
u=r->rChild;
r->rChild=u->lChild;
u->lChild=r;
s->lChild=u->rChild;
u->rChild=s;
switch(u->bF)...{
case 1:
s->bF=-1;
r->bF=0;
break;
case 0:
s->bF=r->bF=0;
break;
case -1:
s->bF=0;
r->bF=1;
}
s=u; //s指示新子树的根
}
s->bF=0; //s的平衡因子为0
unBalanced=false; //结束重新平衡操作
}
通常我们使用二叉树的原因是它可以用O（logn）的复杂度来查找一个数，删除一个数，对吧？？可是有时候会发现树会退化，这个就可能使O（logn）->O（n）的了，那么还不如用直接搜一次呢！！所以我们就要想办法使一棵树平衡。而我仅仅看了（AVL）的那个，所以也仅仅能说（AVL）的那个，至于（TREAP），我还不懂，如果你们知道算法的话，欢迎告诉我~！谢谢~
首先引入一个变量，叫做平衡因子（r），节点X的r就表示x的左子树的深度-右子树的深度。然后我们要保证一棵树平衡，就是要保证左右子树的深度差小于等于1.所以r的取值能且仅能取0，-1，1.
其次，我要介绍旋转，旋转有两种方式，就是左旋（顺时针旋转）和右旋（逆时针旋转）。
左旋（左儿子代替根）：即用左儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把L的右儿子取代X的左儿子，然后把更新后的X赋值为L的右儿子，就可以了。
右旋（右儿子代替根）：即用右儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把R的左儿子取代X的右儿子，然后把更新后的X赋值为L的左儿子，就可以了。