Join-based tree algorithms

In computer science, join-based tree algorithms are a class of algorithms for self-balancing binary search trees. This framework aims at designing highly-parallelized algorithms for various balanced binary search trees. The algorithmic framework is based on a single operation ''join''. Under this framework, the ''join'' operation captures all balancing criteria of different balancing schemes, and all other functions ''join'' have generic implementation across different balancing schemes. The ''join-based algorithms'' can be applied to at least four balancing schemes: AVL trees, red–black trees, weight-balanced trees and treaps.

The ''join''$(L,k,R)$ operation takes as input two binary balanced trees $L$ and $R$ of the same balancing scheme, and a key $k$, and outputs a new balanced binary tree $t$ whose in-order traversal is the in-order traversal of $L$, then $k$ then the in-order traversal of $R$. In particular, if the trees are search trees, which means that the in-order of the trees maintain a total ordering on keys, it must satisfy the condition that all keys in $L$ are smaller than $k$ and all keys in $R$ are greater than $k$.

History

The ''join'' operation was first defined by Tarjan on red–black trees, which runs in worst-case logarithmic time. Later Sleator and Tarjan described a ''join'' algorithm for splay trees which runs in amortized logarithmic time. Later Adams . extended ''join'' to weight-balanced trees and used it for fast set–set functions including union, intersection and set difference. In 1998, Blelloch and Reid-Miller extended ''join'' on treaps, and proved the bound of the set functions to be $O(m\log (1+\tfrac))$ for two trees of size $m$ and $n(\ge m)$, which is optimal in the comparison model. They also brought up parallelism in Adams' algorithm by using a divide-and-conquer scheme. In 2016, Blelloch et al. formally proposed the join-based algorithms, and formalized the ''join'' algorithm for four different balancing schemes: AVL trees, red–black trees, weight-balanced trees and treaps. In the same work they proved that Adams' algorithms on union, intersection and difference are work-optimal on all the four balancing schemes.

Join algorithms

The function ''join''$(t_1,k,t_2)$ considers rebalancing the tree, and thus depends on the input balancing scheme. If the two trees are balanced, ''join'' simply creates a new node with left subtree , root and right subtree . Suppose that is heavier (this "heavier" depends on the balancing scheme) than (the other case is symmetric). ''Join'' follows the right spine of until a node which is balanced with . At this point a new node with left child , root and right child is created to replace c. The new node may invalidate the balancing invariant. This can be fixed with rotations.

The following is the ''join'' algorithms on different balancing schemes.

The ''join'' algorithm for AVL trees:
function joinRightAVL(T_L, k, T_R)
(l, k', c) := expose(T_L)
if h(c) ≤ h(T_R) + 1
T' := Node(c, k, T_R)
if h(T') ≤ h(l) + 1
return Node(l, k', T')
else
return rotateLeft(Node(l, k', rotateRight(T')))
else
T' := joinRightAVL(c, k, T_R)
T :''='' Node(l, k', T')
if h(T') ≤ h(l) + 1
return T
else
return rotateLeft(T)

function joinLeftAVL(T_L, k, T_R)
/* symmetric to joinRightAVL */

function join(T_L, k, T_R)
if h(T_L) > h(T_R) + 1
return joinRightAVL(T_L, k, T_R)
else if h(T_R) > h(T_L) + 1
return joinLeftAVL(T_L, k, T_R)
else
return Node(T_L, k, T_R)
Where:

* $h(v)$ is the height of node $v$.
* $\text(v)$ extracts the left child $l$, key $k$, and right child $r$ of node $v$ into a tuple $(l,k,r)$.
* $\text(l,k,r)$ creates a node with left child $l$, key $k$, and right child $r$.

The ''join'' algorithm for red–black trees:
function joinRightRB(T_L, k, T_R)
if T_L.color = black and ĥ(T_L) = ĥ(T_R)
return Node(T_L, ⟨k, red⟩, T_R)
else
(L', ⟨k', c'⟩, R') := expose(T_L)
T' := Node(L', ⟨k', c'⟩, joinRightRB(R', k, T_R))
if c' = black and T'.right.color = T'.right.right.color = red
T'.right.right.color := black
return rotateLeft(T')
else
return T'

function joinLeftRB(T_L, k, T_R)
/* symmetric to joinRightRB */

function join(T_L, k, T_R)
if ĥ(T_L) > ĥ(T_R)
T' := joinRightRB(T_L, k, T_R)
if (T'.color = red) and (T'.right.color = red)
T'.color := black
return T'
else if ĥ(T_R) > ĥ(T_L)
/* symmetric */
else if T_L.color = black and T_R = black
return Node(T_L, ⟨k, red⟩, T_R)
else
return Node(T_L, ⟨k, black⟩, T_R)
Where:

* is the black height of node $v$.
* $\text(v)$ extracts the left child $l$, key $k$, color $c$, and right child $r$ of node $v$ into a tuple $(l, \langle k, c \rangle, r)$.
* creates a node with left child $l$, key $k$, color $c$, and right child $r$.

The ''join'' algorithm for weight-balanced trees:
function joinRightWB(T_L, k, T_R)
(l, k', c) := expose(T_L)
if w(T_L) =_α w(T_R)
return Node(T_L, k, T_R)
else
T' := joinRightWB(c, k, T_R)
(l₁, k₁, r₁) := expose(T')
if w(l) =_α w(T')
return Node(l, k', T')
else if w(l) =_α w(l₁) and w(l)+w(l₁) =_α w(r₁)
return rotateLeft(Node(l, k', T'))
else
return rotateLeft(Node(l, k', rotateRight(T'))

function joinLeftWB(T_L, k, T_R)
/* symmetric to joinRightWB */

function join(T_L, k, T_R)
if w(T_L) >_α w(T_R)
return joinRightWB(T_L, k, T_R)
else if w(T_R) >_α w(T_L)
return joinLeftWB(T_L, k, T_R)
else
return Node(T_L, k, T_R)
Where:

* $w(v)$ is the weight of node ''$v$.''
* $w_1 =_\alpha w_2$ means weights $w_1$ and $w_2$ are α-weight-balanced.
* $w_1 >_\alpha w_2$ means weight $w_1$ is heavier than weight $w_2$ with respect to the α-weight-balance.
* $\text(v)$ extracts the left child $l$, key $k$, and right child $r$ of node $v$ into a tuple $(l,k,r)$.
* $\text(l,k,r)$ creates a node with left child $l$, key $k$ and right child $r$.

Join-based algorithms

In the following, $\text(v)$ extracts the left child $l$, key $k$, and right child $r$ of node $v$ into a tuple $(l,k,r)$. $\text(l,k,r)$ creates a node with left child $l$, key $k$ and right child $r$. "$s_1 , , s_2$" means that two statements $s_1$ and $s_2$ can run in parallel.

Split

To split a tree into two trees, those smaller than key ''x'', and those larger than key ''x'', we first draw a path from the root by inserting ''x'' into the tree. After this insertion, all values less than ''x'' will be found on the left of the path, and all values greater than ''x'' will be found on the right. By applying ''Join'', 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 asymmetric. For some applications, ''Split'' also returns a boolean value denoting if ''x'' appears in the tree. The cost of ''Split'' is $O(\log n)$, order of the height of the tree.

The split algorithm is as follows:

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

Join2

This function is defined similarly as ''join'' but without the middle key. It first splits out the last key $k$ of the left tree, and then join the rest part of the left tree with the right tree with $k$. The algorithm is as follows:

function splitLast(T)
(L, k, R) := expose(T)
if R = nil
return (L, k)
else
(T', k') := splitLast(R)
return (join(L, k, T'), k')

function join2(L, R)
if L = nil
return R
else
(L', k) := splitLast(L)
return join(L', k, R)

The cost is $O(\log n)$ for a tree of size $n$.

Insert and delete

The insertion and deletion algorithms, when making use of ''join'' can be independent of balancing schemes. For an insertion, the algorithm compares the key to be inserted with the key in the root, inserts it to the left/right subtree if the key is smaller/greater than the key in the root, and joins the two subtrees back with the root. A deletion compares the key to be deleted with the key in the root. If they are equal, return join2 on the two subtrees. Otherwise, delete the key from the corresponding subtree, and join the two subtrees back with the root. The algorithms are as follows:

function insert(T, k)
if T = nil
return Node(nil, k, nil)
else
(L, k', R) := expose(T)
if k < k'
return join(insert(L,k), k', R)
else if k > k'
return join(L, k', insert(R, k))
else
return T

function delete(T, k)
if T = nil
return nil
else
(L, k', R) := expose(T)
if k < k'
return join(delete(L, k), k', R)
else if k > k'
return join(L, k', delete(R, k))
else
return join2(L, R)

Both insertion and deletion requires $O(\log n)$ time if $, T, =n$.

Set–set functions

Several set operations have been defined on weight-balanced trees: union, intersection and set difference. The union of two weight-balanced trees and representing sets and , is a tree that represents . The following recursive function computes this union:

function union(t₁, t₂)
if t₁ = nil
return t₂
else if t₂ = nil
return t₁
else
(l₁, k₁, r₁) := expose(t₁)
(t_<, b, t_>) := split(t₂, k₁)
l' := union(l₁, t_<) , , r' := union(r₁, t_>)
return join(l', k₁, r')

Similarly, the algorithms of intersection and set-difference are as follows:

function intersection(t₁, t₂)
if t₁ = nil or t₂ = nil
return nil
else
(l₁, k₁, r₁) := expose(t₁)
(t_<, b, t_>) = split(t₂, k₁)
l' := intersection(l₁, t_<) , , r' := intersection(r₁, t_>)
if b
return join(l', k₁, r')
else
return join2(l', r')

function difference(t₁, t₂)
if t₁ = nil
return nil
else if t₂ = nil
return t₁
else
(l₁, k₁, r₁) := expose(t₁)
(t_<, b, t_>) := split(t₂, k₁)
l' = difference(l₁, t_<) , , r' = difference(r₁, t_>)
if b
return join2(l', r')
else
return join(l', k₁, r')

The complexity of each of union, intersection and difference is $O\left(m \log \left(\tfrac+1\right)\right)$ for two weight-balanced trees of sizes $m$ and $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 executed in parallel with a parallel depth $O(\log m\log n)$. When $m=1$, the join-based implementation applies the same computation as in a single-element insertion or deletion if the root of the larger tree is used to split the smaller tree.

Build

The algorithm for building a tree can make use of the union algorithm, and use the divide-and-conquer scheme:

function build(A[], n)
if n = 0
return nil
else if n = 1
return Node(nil, A[0], nil)
else
l' := build(A, n/2) , , r' := (A+n/2, n-n/2)
return union(L, R)

This algorithm costs $O(n\log n)$ work and has $O(\log^3 n)$ depth. A more-efficient algorithm makes use of a parallel sorting algorithm.

function buildSorted(A[], n)
if n = 0
return nil
else if n = 1
return Node(nil, A[0], nil)
else
l' := build(A, n/2) , , r' := (A+n/2+1, n-n/2-1)
return join(l', A /2 r')

function build(A[], n)
A' := sort(A, n)
return buildSorted(A, n)

This algorithm costs $O(n\log n)$ work and has $O(\log n)$ depth assuming the sorting algorithm has $O(n\log n)$ work and $O(\log n)$ depth.

Filter

This function selects all entries in a tree satisfying a predicate $p$, and return a tree containing all selected entries. It recursively filters the two subtrees, and join them with the root if the root satisfies $p$, otherwise ''join2'' the two subtrees.

function filter(T, p)
if T = nil
return nil
else
(l, k, r) := expose(T)
l' := filter(l, p) , , r' := filter(r, p)
if p(k)
return join(l', k, r')
else
return join2(l', R)

This algorithm costs work $O(n)$ and depth $O(\log^2 n)$ on a tree of size $n$, assuming $p$ has constant cost.

Used in libraries

The join-based algorithms are applied to support interface for sets, maps, and augmented maps in libraries such as Hackage, SML/NJ, and PAM.

Notes

References

External links

PAM
the parallel augmented map library

Hackage
Containers in Hackage

{{data structures

Binary trees