本页使用了标题或全文手工转换

平衡树

维基百科,自由的百科全书
(重定向自自平衡二叉查找树
跳到导航 跳到搜索

平衡树计算机科学中的一类数据结构。

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

不平衡的树结构

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

平衡的树结构

基本操作[编辑]

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

旋转(Rotate) —— 不破坏左小右大特性的小手术

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

图中 x 与 y 为節點,A、B、C 为一整串的樹狀子目錄(subtrees)。试想:如果 x 原来是 y 的左子(left child);现在想将 x 变成父(parent),则树的其它部分应如何变化?y 必须变成右子(right child), 这样才能维持 BST 的特性 -- 左小右大。 至于 x 与 y 以下的其它部分,可以整串樹狀子目錄一起处理:x 原来的左子樹(left subtree(A),调整后还是 x 的 左子樹;y 原来的右子樹(right subtree(C)),调整后还是 y 的右子樹; x 原来的右子樹 (B),调整后很自然只有一个地方可以放:变成 y 的左子樹。 这些规则都不需要记,因为如果你希望调整后还维持二元搜尋樹左小右大的特性,这是唯一的答案。 把 x、y 两个值及 A、B、C三棵樹狀子目錄内的三串值画在数在线看更清楚:


x --------- y ---------

A B C 这个动作, 称为 right rotation 向右旋转,或称为顺时针旋转 (clockwise)。 原来的 parent (y) 叫做 pivot,原来的 child (x) 叫做 rotator。 把上图反过来看,如果原来的树长得像右图,想将它改成左图,则称为 left rotation 向左旋转,或称为逆时针旋转 (counter-clockwise)。 原来的 parent (x) 叫做 pivot,原来的 child (y) 叫做 rotator。

各种平衡树[编辑]

  • AVL树,经典平衡树, 所有操作的最坏复杂度都是的。
  • Treap,利用随机的期望深度来优化树的深度,达到较优的期望复杂度。
  • 伸展树,使得经常查找的结点深度较小,从而降低均摊复杂度。
  • 红黑树
  • 加权平衡树
  • 2-3树
  • AA树
  • 替罪羊樹
  • 节点大小平衡树

其他类型[编辑]

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

应用[编辑]

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

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