Weight-balanced tree

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.

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.

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.

[5] 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.

That is, a node has fields By definition, the size of a leaf (typically represented by a nil pointer) is zero.

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.

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 of 2⁄11 for α, although it can be made arbitrarily small if a custom (and more complicated) rebalancing algorithm is used.

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] 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.

Then fast bulk operations on insertions or deletions can be implemented based on these set functions.

With the new operations, the implementation of weight-balanced trees can be more efficient and highly-parallelizable.

expose(v)=(l, k, r) means to extract a tree node

(The algorithm is non-destructive, but an in-place destructive version exists as well.)

The algorithm for intersection or difference is similar, but requires the Join2 helper routine that is the same as Join but without the middle key.

Since Split and Union call Join but do not deal with the balancing criteria of weight-balanced trees directly, such an implementation is usually called the join-based algorithms.

This complexity is optimal in terms of the number of comparisons.

, the join-based implementation has the same computational directed acyclic graph (DAG) as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree.