加权平衡树

在计算机科学里面，加权平衡树（，縮寫：WBTs）是一种可以用来实现集合、字典（映射）和序列的平衡树。这些树结构在20世纪70年代被Nievergelt和Reingold作为有界限的自平衡树或BB[α]树提出。让这些结构普及的是高德纳。

就像其他自平衡树一样，加权平衡树储存的账簿信息可以在树结构被插入和删除操作打乱时，通过平衡结点和操作树旋转来使树结构重新达到平衡。特别的地方是，加权平衡树的每个结点储存这个结点下子树的大小，并且这个结点左右子树的大小保持着某种内在联系。不同于AVL树（储存子树的高度）和红黑树（储存虚构的“颜色”位），加权平衡树储存记账信息的方式是对应用真正有用的属性：一棵树下元素的数量等于它的根的大小，然而这个根的大小是一个用来实现顺序统计树操作的有用数据，也就是说，可以得到一个大小为的集合下的最大元素或者决定一个顺序结构下一个元素的索引。

加权平衡树在函数程式语言社区下面非常受欢迎以及被用来实现MIT Scheme的集合和映射结构还有Haskell语言的实现。

在这里，是一个在实现加权平衡树是用来做决定的数值参数。的值越大，意味着这棵树“更加平衡”，但不是所有的值都是合适的；Nievergelt和Reingold曾经证明过满足

:\alpha

是一个平衡算法成功工作的重要状态。他们往后的工作展示了的一个下界是，但如果使用一个自定义（更加复杂的）的再平衡算法，下界还可以更小。

若平衡被正确实现，一棵含有个元素的加权平衡树的高度满足

:h \le \log_{\frac{1}{1-\alpha}} n = \frac{\log_2 n}{\log_2 \left( \frac{1}{1-\alpha} \right)} = O(\log n)

加权平衡树次插入和删除操作中，平衡的次数是线性的，为。也就是说，加权平衡树的平衡操作均摊开销是恒定的。

引用