Weight-balanced tree: Difference between revisions
m →References: unlikely that these two authors will get a collective article |
replace by a stub about what is more commonly called a WBT; the previous article duplicated the topic of optimal binary search tree |
||
| Line 1: | Line 1: | ||
{{Other uses|Optimal binary search tree}} |
|||
A '''weight-balanced binary tree''' is a [[binary tree]] which is balanced based on knowledge of the probabilities of searching for each individual node. Within each [[subtree]], the node with the highest weight appears at the root. This can result in more efficient searching performance compared to searching a binary tree where node probability is not considered. |
|||
In [[computer science]], '''weight-balanced binary trees''' ('''WBTs''') are a type of [[self-balancing binary search tree]]s that can be used to implement [[Set (abstract data type)|dynamic set]]s, [[Associative array|dictionaries]] (maps) and sequences.<ref>{{cite doi|10.1007/BF00289142}}</ref> These trees were introduced by Nievergelt and Reingold in the 1970s as '''trees of bounded balance''', or '''BB[α] trees''';<ref>{{cite doi|10.1137/0202005}}</ref> their more common name is due to [[Donald Knuth|Knuth]].<ref name="Hirai">{{cite doi|10.1017/S0956796811000104}}</ref> |
|||
Like other self-balancing trees, WBTs store bookkeeping information pertaining to balance in their nodes and perform [[tree rotation|rotations]] to restore balance when it is disturbed by insertion or deletion operations. Specifically, each node has a ''weight'' that is either the size of the subtree rooted at the node, or (in the original presentation) the size plus one. Unlike the balance information in [[AVL tree]]s (which store the height of subtrees) and [[red-black tree]]s (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 produce an [[order statistic tree]]. |
|||
Construction of such a tree is similar to that of a [[Treap]], but node weights are chosen randomly in the latter. |
|||
Weight-balanced trees are popular in the [[functional programming]] community and are used to implement sets and maps in [[MIT Scheme]], the Slib [[Scheme (programming language)|Scheme]] library, and implementations of [[Haskell (programming language)|Haskell]].<ref>{{cite doi|10.1017/S0956796800000885}}</ref><ref name="Hirai"/> |
|||
[[Image:Weight_balanced_tree2.jpg|frame|Example of weight balanced tree]] |
|||
==The diagram== |
|||
In the diagram to the right, the letters represent node ''values'' and the numbers represent node ''weights''. Values are used to order the tree, as in a general [[binary search tree]]. The weight may be thought of as a probability or activity count associated with the node. In the diagram, the root is G because its weight is the greatest in the tree. The left subtree begins with A because, out of all nodes with values that come before G, A has the highest weight. Similarly, N is the highest-weighted node that comes after G. |
|||
The rebalancing operations needed to implement a WBT are the same as those for an AVL tree, rotations and double rotations. Applying them correctly guarantees a tree of {{mvar|n}} elements will have height {{math|''O''(log ''n'')}}; the number of balancing operations required in a sequence of {{mvar|n}} insertions and deletions is linear in {{mvar|n}}, i.e., constant in an [[amortized analysis|amortized]] sense.<ref>{{cite doi|10.1016/0304-3975(80)90018-3}}</ref> |
|||
==Timing analysis== |
|||
A weight balanced tree gives close to optimal values for the '''e'''xpected '''l'''ength '''o'''f '''s'''uccessful '''s'''earch calculations (ELOSS). From the above example we get: |
|||
| ⚫ | |||
ELOSS = depth(node A)*probability(node A) + depth(node C)*probability(node C) + ... |
|||
{{reflist}} |
|||
{{Algorithm-stub}} |
|||
ELOSS = 2*0.17 + 5*0.03 + 4*0.09 + 3*0.12 + 1*0.20 + 3*0.11 + 3*0.10 + 2*0.18 |
|||
{{CS-Trees}} |
|||
ELOSS = 2.5 |
|||
| ⚫ | |||
This is the expected number of nodes that will be examined before finding the desired node. |
|||
== See also == |
|||
* [[Binary tree]] |
|||
* [[AVL tree]] |
|||
* [[B-tree]] |
|||
* [[Binary space partitioning]] |
|||
* [[Red-black tree]] |
|||
* [[Treap]] |
|||
| ⚫ | |||
* Jean-Paul Tremblay and Grant A. Cheston. ''Data Structures and Software Development in an object-oriented domain'', Eiffel Edition. Prentice Hall, 2001. ISBN 0-13-787946-6. |
|||
| ⚫ | |||
Revision as of 09:02, 26 March 2015
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] their more common name is due to Knuth.[3]
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 has a weight that is either the size of the subtree rooted at the node, or (in the original presentation) the size plus one. 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 produce an order statistic tree.
Weight-balanced trees are popular in the functional programming community and are used to implement sets and maps in MIT Scheme, the Slib Scheme library, and implementations of Haskell.[4][3]
The rebalancing operations needed to implement a WBT are the same as those for an AVL tree, rotations and double rotations. Applying them correctly guarantees a tree of n elements will have height O(log n); the number of balancing operations required in a sequence of n insertions and deletions is linear in n, i.e., constant in an amortized sense.[5]
References
- ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/BF00289142, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1007/BF00289142instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1137/0202005, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1137/0202005instead. - ^ a b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1017/S0956796811000104, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1017/S0956796811000104instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1017/S0956796800000885, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1017/S0956796800000885instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0304-3975(80)90018-3, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1016/0304-3975(80)90018-3instead.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |