平衡树是计算机科学中的一类数据结构,为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离(即深度),因此当结点的深度普遍较大时,查询的均摊复杂度会上升。为了实现更高效的查询,产生了平衡树。
在这里,平衡指所有叶子的深度趋于平衡,更广义的是指在树上所有可能查找的均摊复杂度偏低。
旋转(Rotate):几乎所有平衡树的操作都基于树旋转操作(也有部分基于重构,如替罪羊树),通过旋转操作可以使得树趋于平衡。对一棵查找树(search tree)进行查询、新增、删除等动作,所花的时间与树的高度h成比例,并不与树的容量 n 成比例。如果可以让树维持平衡,也就是让h维持在,且最大的数。
查询后继(successor):后继定义为大于,且最小的数。
在维护节点大小(size)后,可以支持以下操作:
查询排名(rank):排名定义为比x小的数的个数加一。
查询第k大:即排名为的数。
以下数据结构支持平衡树大多数操作,但实现有根本不同:
用于表示有序的线性数据结构,如优先队列、关联数组、键(key)-值(value)的映射等。自平衡的二叉查找树与哈希表的相比,各有优缺。平衡树在按序遍历所有键值时是量级最优的,哈希表不能。自平衡二叉查找树在查找一个键值时,最坏情况下时间复杂度优于哈希表, 对比;但平均时间复杂度逊于hash表,对比。
平衡树的排序方法,虽然在平均时间复杂度上也是,但由于cache性能、树的调整操作等,性能上不如快速排序、堆排序、归并排序等同为复杂度的排序。