Weight-balanced tree
Type	Tree
Invented	1972
Invented by	de:Jürg Nievergelt andEdward Reingold
Complexities inbig O notation
Space complexity Space ${\displaystyle O(n)}$ Time complexity Function Amortized Worst case Search ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ Insert ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ Delete ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

Incomputer science,weight-balanced binary trees (WBTs) are a type ofself-balancing binary search trees that can be used to implementdynamic sets,dictionaries (maps) and sequences.^[1] These trees were introduced by Nievergelt and Reingold in the 1970s astrees of bounded balance, orBB[α] trees.^[2][3] Their more common name is due toKnuth.^[4]

A well known example is aHuffman coding of acorpus.

Like other self-balancing trees, WBTs store bookkeeping information pertaining to balance in their nodes and performrotations 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 inAVL trees (using information about the height of subtrees) andred–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 anorder statistic tree, viz., getting then'th largest element in a set or determining an element's index in sorted order.^[5]

Weight-balanced trees are popular in thefunctional programming community and are used to implement sets and maps inMIT Scheme,SLIB,SML-NJ, and implementations ofHaskell.^[6][4]

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 anil 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 beweight[n] = size[n] + 1.^[a] 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 samerebalancing operations used inAVL trees: rotations and double rotations. Formally, node balance is defined as follows:

A node isα-weight-balanced ifweight[n.left] ≥ α·weight[n] andweight[n.right] ≥ α·weight[n].^[7]

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

is a necessary condition for the balancing algorithm to work. Later work showed a lower bound of2⁄11 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 ofn elements will have height^[7]

${\displaystyle h\le {\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${\displaystyle 2{\log }_{2}n}$.

The number of balancing operations required in a sequence ofn insertions and deletions is linear inn, i.e., balancing takes a constant amount of overhead in anamortized sense.^[8]

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.^[9]

Several set operations have been defined on weight-balanced trees:union,intersection andset difference. Then fastbulk operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations,Split andJoin. With the new operations, the implementation of weight-balanced trees can be more efficient and highly-parallelizable.^[10][11]

Join

The functionJoin is on two weight-balanced treest₁ andt₂ and a keyk and will return a tree containing all elements int₁,t₂ as well ask. It requiresk to be greater than all keys int₁ and smaller than all keys int₂. If the two trees have the balanced weight,Join simply create a new node with left subtreet₁, rootk and right subtreet₂. Suppose thatt₁ has heavier weight thant₂ (the other case is symmetric).Join follows the right spine oft₁ until a nodec which is balanced witht₂. At this point a new node with left childc, root k and right childt₂ 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

Split

To split a weight-balanced tree into two smaller trees, those smaller than keyx, and those larger than keyx, first draw a path from the root by insertingx into the tree. After this insertion, all values less thanx will be found on the left of the path, and all values greater thanx will be found on the right. By applyingJoin, all the subtrees on the left side are merged bottom-up using keys on the path as intermediate nodes from bottom to top to form the left tree, and the right part is symmetric. For some applications,Split also returns a Boolean value denoting ifx appears in the tree. The cost ofSplit is${\displaystyle O(\log n)}$, order of the height of the tree. This algorithm actually has nothing to do with any special properties of a weight-balanced tree, and thus is generic to other balancing schemes such asAVL trees.

The join algorithm is as follows:

function joinRightWB(TL, k, TR)    (l, k', c) = expose(TL)if balance(|TL|, |TR|)return Node(TL, k, TR)else         T' = joinRightWB(c, k, TR)        (l', k', r') = expose(T')if (balance(|l|,|T'|))return Node(l, k', T')else if (balance(|l|,|l'|) and balance(|l|+|l'|,|r'|))return rotateLeft(Node(l, k', T'))elsereturn rotateLeft(Node(l, k', rotateRight(T'))function joinLeftWB(TL, k, TR)    /* symmetric to joinRightWB */function join(TL, k, TR)if (heavy(TL, TR))return joinRightWB(TL, k, TR)if (heavy(TR, TL))return joinLeftWB(TL, k, TR)    Node(TL, k, TR)

Here balance${\displaystyle (x,y)}$ means two weightsT andT are balanced. expose(v)=(l, k, r) means to extract a tree nodeT's left childT, the key of the nodeT and the right childT. Node(l, k, r) means to create a node of left childT, keyT and right childT.

The split algorithm is as follows:

function split(T, k)if (T = nil)return (nil, false, nil)    (L, (m, c), R) = expose(T)if (k = m)return (L, true, R)if (k < m)        (L', b, R') = split(L, k)return (L', b, join(R', m, R))if (k > m)        (L', b, R') = split(R, k)return (join(L, m, L'), b, R))

The union of two weight-balanced treest₁ andt₂ representing setsA andB, is a weight-balanced treet that representsA ∪B. The following recursive function computes this union:

function union(t1, t2):if t1 = nil:return t2if t2 = nil:return t1    t<, t> ← split t2 on t1.rootreturn join(union(left(t1), t<), t1.root, union(right(t1), t>))

Here,Split is presumed to return two trees: one holding the keys less than its input key, the other holding the greater keys. (The algorithm isnon-destructive, but an in-place destructive version exists as well.)

The algorithm for intersection or difference is similar, but requires theJoin2 helper routine that is the same asJoin but without the middle key. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the weight-balanced tree. SinceSplit andUnion callJoin but do not deal with the balancing criteria of weight-balanced trees directly, such an implementation is usually called thejoin-based algorithms.

The complexity of each of union, intersection and difference is${\displaystyle O\left(m\log \left(\frac{n}{m}+1\right)\right)}$ for two weight-balanced trees of sizesT and${\displaystyle n(\ge m)}$. This complexity is optimal in terms of the number of comparisons. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executedin parallel with aparallel depth${\displaystyle O(\log m\log n)}$.^[10] When${\displaystyle m=1}$, the join-based implementation has the same computationaldirected acyclic graph (DAG) as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree.

• Search trees

• Articles with short description
• Short description is different from Wikidata