加权平衡树:修订间差异

维基百科,自由的百科全书
删除的内容 添加的内容
Duzhong留言 | 贡献
建立内容为“{{Other uses|Optimal binary search tree}} In computer science, '''weight-balanced binary trees''' ('''WBTs''') are a type of self-balancing bi...”的新页面
(没有差异)

2015年12月8日 (二) 12:30的版本

In computer science, weight-balanced binary trees (WBTs) are a type of self-balancing binary search trees that can be used to implement dynamic sets, dictionaries (maps) and sequences.[1] These trees were introduced by Nievergelt and Reingold in the 1970s as trees of bounded balance, or BB[α] trees.[2][3] Their more common name is due to Knuth.[4]

Like other self-balancing trees, WBTs store bookkeeping information pertaining to balance in their nodes and perform rotations to restore balance when it is disturbed by insertion or deletion operations. Specifically, each node stores the size of the subtree rooted at the node, and the sizes of left and right subtrees are kept within some factor of each other. Unlike the balance information in AVL trees (which store the height of subtrees) and red-black trees (which store a fictional "color" bit), the bookkeeping information in a WBT is an actually useful property for applications: the number of elements in a tree is equal to the size of its root, and the size information is exactly the information needed to implement the operations of an order statistic tree, viz., getting the n'th largest element in a set or determining an element's index in sorted order.[5]

Weight-balanced trees are popular in the functional programming community and are used to implement sets and maps in MIT Scheme, SLIB and implementations of Haskell.[6][4]

Description

A weight-balanced tree is a binary search tree that stores the sizes of subtrees in the nodes. That is, a node has fields

  • key, of any ordered type
  • value (optional, only for mappings)
  • left, right, pointer to node
  • size, of type integer.

By definition, the size of a leaf (typically represented by a nil pointer) is zero. The size of an internal node is the sum of sizes of its two children, plus one (size[n] = size[n.left] + size[n.right] + 1). Based on the size, one defines the weight as either equal to the size, or as weight[n] = size[n] + 1.

Binary tree rotations.

Operations that modify the tree must make sure that the weight of the left and right subtrees of every node remain within some factor α of each other, using the same rebalancing operations used in AVL trees: rotations and double rotations. Formally, node balance is defined as follows:

A node is α-weight-balanced if weight[n.left] ≥ α·weight[n] and weight[n.right] ≥ α·weight[n].[7]

Here, α is a numerical parameter to be determined when implementing weight balanced trees. Lower values of α produce "more balanced" trees, but not all values of α are appropriate; Nievergelt and Reingold proved that

is a necessary condition for the balancing algorithm to work. Later work showed a lower bound of 211 for α, although it can be made arbitrarily small if a custom (and more complicated) rebalancing algorithm is used.[7]

Applying balancing correctly guarantees a tree of n elements will have height[7]

The number of balancing operations required in a sequence of n insertions and deletions is linear in n, i.e., balancing takes a constant amount of overhead in an amortized sense.[8]

References

  1. ^ Tsakalidis, A. K. Maintaining order in a generalized linked list. Acta Informatica. 1984, 21: 101. doi:10.1007/BF00289142. 
  2. ^ Nievergelt, J.; Reingold, E. M. Binary Search Trees of Bounded Balance. SIAM Journal on Computing. 1973, 2: 33. doi:10.1137/0202005. 
  3. ^  本条目引用的公有领域材料。材料来自NIST的文档:Black, Paul E. BB(α) tree. 演算法與資料結構辭典英语Dictionary of Algorithms and Data Structures. 
  4. ^ 4.0 4.1 Hirai, Y.; Yamamoto, K. Balancing weight-balanced trees. Journal of Functional Programming. 2011, 21 (3): 287. doi:10.1017/S0956796811000104. 
  5. ^ Roura, Salvador. A new method for balancing binary search trees. ICALP. Lecture Notes in Computer Science 2076: 469–480. 2001. ISBN 978-3-540-42287-7. doi:10.1007/3-540-48224-5_39. 
  6. ^ Adams, Stephen. Functional Pearls: Efficient sets—a balancing act. Journal of Functional Programming. 1993, 3 (4): 553–561. doi:10.1017/S0956796800000885. 
  7. ^ 7.0 7.1 7.2 Brass, Peter. Advanced Data Structures. Cambridge University Press. 2008: 61–71. 
  8. ^ 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. 

Template:Algorithm-stub

Template:CS-Trees