平衡二叉树

平衡二叉树(Balanced Binary Tree) 是二叉搜索树（又名二叉查找树排序二叉树）的一种。在二叉搜索树中，搜索、插入、删除的复杂度都和树的高度相关，因此树高是制约二叉搜索树时间效率的最大瓶颈。 理论上，任意高度为h二叉树最多能容纳2^h − 1个元素，即h=O(lg n)。实际上，由于普通二叉树的形态常常受操作顺序的影响，各子树左右儿子节点数目相差比较大，极端情况下，二叉树蜕化成一条链，此时h=O(n)

平衡二叉树通过一组平衡化旋转规则，使得各个子树的形态发生变化，从而使树高趋近于lg n。

---

常见的平衡化旋转规则有两种：左旋转和右旋转

左旋转

Left-Rotate (t)
1     k ← right[t]
2     right[t] ← left[k]
3     left[k] ← t
4     s[k] ← s[t]
5     s[t] ← s[left[t]] + s[right[t]] + 1
6     t ← k

右旋转

Right-Rotate(t)
1     k ← left[t]
2     left[t] ← right[k]
3     right[k] ← t
4     s[k] ← s[t]
5     s[t] ← s[left[t]] + s[right[t]] + 1
6     t ← k

--- 常见的平衡二叉树有如下的几种

1. AVL树 其主要思想是维护树高，使之平衡
2. 红黑树 其主要思想是对节点染色，对不同颜色的节点采用不同的判断，编程复杂度较高
3. AA树 是红黑树的一种特例
4. 伸展树 有四种旋转规则
5. Treap 其主要思想是对每个节点附加随机权值，并根据权值维护为堆，因此被命名为Tree+Heap=Treap，其编程复杂度较低，性价比较高。
6. Size Balanced Tree 其主要思想为直接维护各子树的节点个数，使之严格平衡。其论文由中国OIer广东纪念中学的陈启峰于2006年底完成，并在Winter Camp 2007中发表。