Mixing
加权平衡树
參數所指定的目標頁面不存在，建議更正成存在頁面或直接建立下列一個頁面（建立前請先搜尋是否有合適的存在頁面可以取代）：
- 最优二叉搜索树
關於与「加权平衡树」名称相近或相同的条目，請見「最优二叉搜索树」。在计算机科学里面，加权平衡树（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曾经证明过满足
- α<1−12{displaystyle alpha <1-{frac {1}{sqrt {2}}}}
是一个平衡算法成功工作的重要状态。他们往后的工作展示了α的一个下界是2⁄11，几时它可以无限小如果使用一个自定义（更加复杂的）的再平衡算法。[7]
若平衡被正确实现，一棵含有n个元素的加权平衡树的高度h满足[7]
- h≤log11−αn=log2nlog2(11−α)=O(logn){displaystyle hleq log _{frac {1}{1-alpha }}n={frac {log _{2}n}{log _{2}left({frac {1}{1-alpha }}right)}}=O(log n)}
加权平衡树n次插入和删除操作中，平衡的次数是线性的，为n。也就是说，加权平衡树的平衡操作均摊开销是恒定的。[8]
引用
^ Tsakalidis, A. K. Maintaining order in a generalized linked list. Acta Informatica. 1984, 21: 101. doi:10.1007/BF00289142.
^ Nievergelt, J.; Reingold, E. M. Binary Search Trees of Bounded Balance. SIAM Journal on Computing. 1973, 2: 33. doi:10.1137/0202005.
^
本条目引用的公有领域材料。材料来自NIST的文档：Black, Paul E. BB(α)tree. 演算法與資料結構辭典.
^ 4.04.1 Hirai, Y.; Yamamoto, K. Balancing weight-balanced trees. Journal of Functional Programming. 2011, 21 (3): 287. doi:10.1017/S0956796811000104.
^ Roura, Salvador. A new method for balancing binary search trees. ICALP. Lecture Notes in Computer Science: 469–480. 2001. ISBN 978-3-540-42287-7. doi:10.1007/3-540-48224-5_39.
^ Adams, Stephen. Functional Pearls: Efficient sets—a balancing act. Journal of Functional Programming. 1993, 3 (4): 553–561. doi:10.1017/S956796800000885.
^ 7.07.17.2 Brass, Peter. Advanced Data Structures. Cambridge University Press. 2008: 61–71.
^ Blum, Norbert; Mehlhorn, Kurt. On the average number of rebalancing operations in weight-balanced trees (PDF). Theoretical Computer Science. 1980, 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3.
本条目引用的公有领域材料。材料来自NIST的文档：Black, Paul E. BB(α)tree.
| ||||||||||||||||||||||||||||||||||||||
Comments
Post a Comment