平衡二叉树（Balanced Binary Tree）

平衡二叉树（Balanced Binary Tree）的简介

平衡二叉树（Balanced Binary Tree）是二叉树（Binary Tree）中最重要的一种树结构。在前面的二叉搜索树中，我们提到，二叉搜索树（Binary Search Tree, BST）的搜索效率取决于树的形状。

在最坏的情况下，所有的元素都以增加key的方式（通常一个节点的key对应了一个值，搜索树就是与节点的key比较）来插入节点，会使得二叉搜索树像一个线性表（这时候它就是一个单枝树），它的搜索时间就是O(n)。

之前的博客也提到过，二叉搜索树的搜索、插入和删除时间都与二叉搜索树的高度有关，而其高度范围是：\log_2(n) < h \leq n。为了使得二叉查找树的查询效率好，我们希望树的高度越小越好。因此，就有了平衡二叉树（Balanced Binary Tree）。

两种平衡二叉树

平衡二叉树的定义有两种，一种是权重平衡树（Weight-Balancedness Tree, WBT），一种是高度平衡树（Height-Balancedness Tree, HBT）：

• 对于一棵树的内部节点来说，如果它的左子树下所有节点数与右子树相比，其差值小于等于1，那么这棵树就是平衡的。这个定义的就是权重平衡树。

• 任意两个叶子节点的深度之差小于等于1，那么这就是高度平衡树。注意，在前面的二叉树（Binary Tree）介绍中，我们说明了树的深度是指当前节点到根节点的边数，树的高度是当前节点与叶子节点的边数。因此，有时候这里的定义是任意内部节点的左子树的高度和右子树的高度之差小于等于1。这二者是等价的。

权重平衡树（Weight-Balancedness Tree, WBT）

在计算机科学中，权重平衡二叉树（WBT）是一种自平衡二叉查找树，可用于实现动态集（dynamic sets），字典（映射，dictionaries/map）和序列（sequences）等。

与其他自平衡树一样，权重平衡树（WBT）保存了一些信息，并在受到插入或者删除操作的时候执行旋转操作以恢复平衡。其中每个节点保存了其子树的大小，同时左右子树之间的大小保持在某个因子内。与高度平衡树不同的是，WBT中保存的信息在应用中非常有用：一棵树的元素数量等于其根节点的大小，这在顺序统计树（order statistic tree）中非常需要。

权重统计树保存的信息：
key：键，任意一种有序类型即可
value：值，任意类型，只在实现map的时候需要
left, right, pointer to node：左右子节点信息
size：大小，这是整型

高度平衡树（Height-Balancedness Tree, WBT）

高度平衡树，也叫自适应二叉查找平衡树（self-balancing search tree）。这种结构提供了对可变顺序列表的高效实现，可以用来实现其他抽象的数据结构，如关联数组（associative arrays）、优先队列（priority queues）和集合（sets）等。

注意，一棵树是高度平衡树并不意味着它是权重平衡树，但是如果一棵树是权重平衡树，那么它一定是高度平衡树。也就是说，权重平衡树可以理解为一种高度平衡树。此外，高度平衡树还包括了以下其他的种类：

• 红黑树（Red-black tree）
• AVL树（Adelson-Velsky and Landis tree，是这两个人发明的）
• B-树（B-Tree，注意，这不是二叉树，区别于Binary Tree）
• …

参考：
http://user.it.uu.se/~justin/Teaching/PK2/Slides/AVLtrees.pdf