平衡树

红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。

红黑树有两个特征:

(1) 节点都有颜色

(2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。

红黑规则:

1. 每一个节点不是红色的就是黑色的

2. 根总是黑色的

3. 如果节点是红色的，则它的子节点必须是黑色的(反之不一定成立)

4. 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。

(空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置)

AVL树 ，它或者是一颗空二叉树，或者是具有下列性质的二叉树:

(1) 其根的左右子树高度之差的绝对值不能超过1;

(2) 其根的左右子树都是二叉平衡树。

AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。

AVL树插入的C++代码:

通常我们使用二叉树的原因是它可以用O(logn)的复杂度来查找一个数，删除一个数，对吧??可是有时候会发现树会退化，这个就可能使O(logn)->O(n)的了，那么还不如用直接搜一次呢!!所以我们就要想办法使一棵树平衡。

首先引入一个变量，叫做平衡因子(r)，节点X的r就表示x的左子树的深度-右子树的深度。然后我们要保证一棵树平衡，就是要保证左右子树的深度差小于等于1.所以r的取值能且仅能取0，-1，1.

其次，我要介绍旋转，旋转有两种方式，就是左旋(顺时针旋转)和右旋(逆时针旋转)。

左旋(左儿子代替根):即用左儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把L的右儿子取代X的左儿子，然后把更新后的X赋值为L的右儿子，就可以了。

右旋(右儿子代替根):即用右儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把R的左儿子取代X的右儿子，然后把更新后的X赋值为R的左儿子，就可以了。

Size Balanced Tree (SBT平衡树)是2007年Winter Camp上由我国著名OI选手陈启峰发布的他自己创造的数据结构。相比于一般的平衡树，此平衡树具有的特点是:快速(远超Treap，超过AVL)、代码简洁、空间小(是线段树的1/4左右)、便于调试和修改等优势。

与一般平衡搜索树相比，该数据结构只靠维护一个Size来保持树的平衡，通过核心操作Maintain(修复)使得树的修改平摊时间为O(1)。因而大大简化代码实现复杂度、提高运算速度。

参见百度百科SBT。

Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap并不一定是。

平衡树的一种，每次将待操作节点提到根，每次操作时间复杂度为O(logn)。见伸展树。

对一棵查找树(search tree)进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree(平衡树)。

旋转Rotate -- 不破坏左小右大特性的小手术

平衡树有很多种, 其中有几类树维持平衡的方法, 都是靠整形小手术:

图中 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。

一棵二叉平衡树的子树，根是Root，左子树是x，右子树的根为RootR，右子树的两个孩子树分别为RLeftChild和RRightChild。则左旋后，该子树的根为RootR，右子树为RRightChild，左子树的根为Root，Root的两个孩子树分别为x(左)和RLeftChild(右)。

一棵二叉平衡树的子树，根是Root，右子树是x，左子树的根为RootL，左子树的两个孩子树分别为LLeftChild和LRightChild。则右旋后，该子树的根为RootL，左子树为LLeftChild，右子树的根为Root，Root的两个孩子树分别为LRightChild(左)和x(右)。

数一下旧的 parent 左 subtree 有多少 nodes? 右 subtree 有多少 nodes? 旋转后新的 parent 左右 subtrees 又各有多少 nodes? 发现右旋的效果会让树的重心往右移; 而左旋的效果则是让树的重心往左移。 如果你的树经历过许多 insert/remove 等等岁月的沧桑, 越长越歪, 在适当的时候对它进行一下旋转手术, 不就可以将它变回矮矮胖胖四平八稳的美丽模样吗? 所以左旋与右旋是几种平衡树共同采用的基本手术; 只不过不同的平衡树, 选择不同的时机/条件来动手术而已。

左子节点与右子节点对称的树就是平衡树，否则就是非平衡树。

非平衡树会影响树中数据的查询，插入和删除的效率。比如当一个二叉树极不平衡时，即所有的节点都在根的同一侧，此时树没有分支，就变成了一个链表。数据的排列是一维的，而不是二维的。在这种情况下，查找的速度下降到O(N)，而不是平衡二叉树的O(logN)。

为了能以较快的时间O(logN)来搜索一棵树，需要保证树总是平衡的(或者至少大部分是平衡的)。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。

Size Balanced Tree(SBT)是一种通过大小(Size)域来保持平衡的二叉搜索树，它也因此得名。它总是满足:

对于SBT的每一个结点 t:

性质(a) s[right[t] ]≥s[left[left[t]]], s[right[left[t]]]

性质(b) s[left[t] ]≥s[right[right[t]]], s[left[right[t]]]

即每棵子树的大小不小于其兄弟的子树大小。

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。

AVL是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap并不一定是。

伸展树(Splay Tree)是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

Size Balanced Tree(简称SBT)是一自平衡二叉查找树，是在计算机科学中用到的一种数据结构。它是由中国广东中山纪念中学的陈启峰发明的。陈启峰于2006年底完成论文《Size Balanced Tree》，并在2007年的全国青少年信息学奥林匹克竞赛冬令营中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的信息学竞赛选手和ACM/ICPC选手们戏称为"傻B树"、"Super BT"等。相比红黑树、AVL树等自平衡二叉查找树，SBT更易于实现。据陈启峰在论文中称，SBT是"目前为止速度最快的高级二叉搜索树"。SBT能在O(log n)的时间内完成所有二叉搜索树(BST)的相关操作，而与普通二叉搜索树相比，SBT仅仅加入了简洁的核心操作Maintain。由于SBT赖以保持平衡的是size域而不是其他"无用"的域，它可以很方便地实现动态顺序统计中的select和rank操作。

我们知道，对于一般的二叉搜索树(Binary Search Tree)，其期望高度(即为一棵平衡树时)为log2n，其各操作的时间复杂度(O(log2n))同时也由此而决定。但是，在某些极端的情况下(如在插入的序列是有序的时)，二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。

平衡二叉搜索树(Balanced Binary Tree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log(n))，大大降低了操作的时间复杂度。