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. These trees were introduced by Nievergelt and Reingold in the 1970s as trees of bounded balance, or BB[α] trees. Their more common name is due to Knuth. 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 (using information about 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. Weight-balanced trees are popular in the functional programming community and are used to implement sets and maps in MIT Scheme, SLIB, SML-NJ, and implementations of Haskell.
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 to be weight[n] = size[n] + 1. Weight has the advantage that the weight of a node is simply the sum of the weights of its left and right children.
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]. Here, α is a numerical parameter to be determined when implementing weight balanced trees. Larger values of α produce "more balanced" trees, but not all values of α are appropriate; Nievergelt and Reingold proved that
α < 1 − 2 2 ≈ 0.29289 {\displaystyle \alpha <1-{\frac {\sqrt {2}}{2}}\approx 0.29289}
is a necessary condition for the balancing algorithm to work. Later work showed a lower bound of 2⁄11 for α, although it can be made arbitrarily small if a custom (and more complicated) rebalancing algorithm is used. Applying balancing correctly guarantees a tree of n elements will have height
h ≤ log 1 1 − α n = log 2 n log 2 ( 1 1 − α ) = O ( log n ) {\displaystyle h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n)}
If α is given its maximum allowed value, the worst-case height of a weight-balanced tree is the same as that of a red–black tree at 2 log 2 n {\displaystyle 2\log _{2}n} . 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. While maintaining a tree with the minimum search cost requires four kinds of double rotations (LL, LR, RL, RR as in an AVL tree) in insert/delete operations, if we desire only logarithmic performance, LR and RL are the only rotations required in a single top-down pass.
Set operations and bulk operations Several set operations have been defined on weight-balanced trees: union, intersection and set difference. Then fast bulk operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, Split and Join. With the new operations, the implementation of weight-balanced trees can be more efficient and highly-parallelizable.
Join The function Join is on two weight-balanced trees t1 and t2 and a key k and will return a tree containing all elements in t1, t2 as well as k. It requires k to be greater than all keys in t1 and smaller than all keys in t2. If the two trees have the balanced weight, Join simply create a new node with left subtree t1, root k and right subtree t2. Suppose that t1 has heavier weight than t2 (the other case is symmetric). Join follows the right spine of t1 until a node c which is balanced with t2. At this point a new node with left child c, root k and right child t2 is created to replace c. The new node may invalidate the weight-balanced invariant. This can be fixed with a single or a double rotation assuming α < 1 − 1 2 {\displaystyle \alpha <1-{\frac {1}{\sqrt {2}}}}
… excerpt ends here. Continue reading the full article.
