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${\displaystyle (L,k,R)}$ operation takes as input two binary balanced trees ${\displaystyle L}$ and ${\displaystyle R}$ of the same balancing scheme, and a key ${\displaystyle k}$, and outputs a new balanced binary tree ${\displaystyle t}$ whose in-order traversal is the in-order traversal of ${\displaystyle L}$, then ${\displaystyle k}$ then the in-order traversal of ${\displaystyle 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 ${\displaystyle L}$ are smaller than ${\displaystyle k}$ and all keys in ${\displaystyle R}$ are greater than ${\displaystyle k}$.

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 ${\displaystyle O(m\log(1+{\tfrac {n}{m}}))}$ for two trees of size ${\displaystyle m}$ and ${\displaystyle n(\geq 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.

The function join${\displaystyle (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 t₁, root k and right subtree t₂. Suppose that t₁ is heavier (this "heavier" depends on the balancing scheme) than t₂ (the other case is symmetric). Join follows the right spine of t₁ until a node c which is balanced with t₂. At this point a new node with left child c, root k and right child t₂ 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:

Where:

The join algorithm for red–black trees: