平衡树

维基百科,自由的百科全书
跳转至: 导航搜索

平衡树计算机科学中的一类数据结构。 平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当结点的深度普遍较大时,查询的均摊复杂度会上升,为了更高效的查询,平衡树应运而生了。

不平衡的树结构

在这里,平衡指所有叶子的深度趋于平衡,更广义的是指在树上所有可能查找的均摊复杂度偏低。

平衡的树结构

基本操作[编辑]

几乎所有平衡树的操作都基于树旋转操作,通过旋转操作可以使得树趋于平衡。 对一棵查找树(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。

各种平衡树[编辑]

其他类型[编辑]

  • 跳表,一种支持平衡树大多数操作的数据结构

应用[编辑]

用于表示有序的线性数据结构,如优先队列关联数组、键-值的映射等。自平衡的二叉查找树的实现与其竞争对手hash表的实现,各具有优缺点。自平衡二叉查找树在按序遍历所有键值时是量级最优的,hash表不能。自平衡二叉查找树在查找一个键值时,最坏情况下时间复杂度优于hash表, O(log n)对比O(n);但平均时间复杂度逊于hash表,O(log n)对比O(1)。

自平衡二叉查找树的排序方法,虽然在平均时间复杂度上也是O(n log n),但由于cache性能、树的调整操作等,性能上不如快速排序、堆排序、合并排序。