加权平衡树

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

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

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

描述

加权平衡树是一种储存子树大小的二叉搜索树。那就是说，一个结点包含以下字段：

• 键（key），任何可排序的类型
• 值（value，可选，只作映射作用）
• 左子树（left），右子树（right），结点的指针
• 大小（size），整数类型

从定义上来说，树上叶子（没有子结点的元素）的大小（典型地用一个空指针表示）是0。一个内部结点的大小是它的两棵子树的大小，再加一 （size[n] = size[n.left] + size[n.right] + 1）。一个结点的权重取决于它的大小或者等于它的大小，或weight[n] = size[n] + 1。

树旋转

修改树的操作必须使用与AVL树中相同的操作来保证左子树和右子树的大小相互存在某种内在因子α，也就是旋转和两次选择。形式上来说，结点平衡操作如下定义：

如果一个结点满足weight[n.left] ≥ α·weight[n]以及weight[n.right] ≥ α·weight[n]，那么就说这个结点是α加权平衡的。^[7]

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

${\displaystyle \alpha <1-{\frac {1}{\sqrt {2}}}}$

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

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

${\displaystyle h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n)}$

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