Join-based tree algorithms

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, join-based tree algorithms are a class of algorithms for <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing binary search trees</a>. 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: <a href="/facts/AVL_tree/DfexIbS6">AVL trees</a>, <a href="/facts/Red%25E2%2580%2593black_tree/ckgWTV7G">red–black trees</a>, <a href="/facts/Weight-balanced_tree/Per0DBtr">weight-balanced trees</a> and <a href="/facts/Treap/sNDcxCpE">treaps</a>.
The join
 
 
 
 (
 L
 ,
 k
 ,
 R
 )
 
 
 {\displaystyle (L,k,R)}
 
 operation takes as input two binary balanced trees 
 
 
 
 L
 
 
 {\displaystyle L}
 
 and 
 
 
 
 R
 
 
 {\displaystyle R}
 
 of the same balancing scheme, and a key 
 
 
 
 k
 
 
 {\displaystyle k}
 
, and outputs a new balanced binary tree 
 
 
 
 t
 
 
 {\displaystyle t}
 
 whose <a href="/facts/Tree_traversal/Dkch34pz">in-order traversal</a> is the in-order traversal of 
 
 
 
 L
 
 
 {\displaystyle L}
 
, then 
 
 
 
 k
 
 
 {\displaystyle k}
 
 then the in-order traversal of 
 
 
 
 R
 
 
 {\displaystyle R}
 
. In particular, if the trees are <a href="/facts/Search_tree/zJIIMEH8">search trees</a>, which means that the in-order of the trees maintain a <a href="/facts/Total_ordering/xnTtmuYJ">total ordering</a> on keys, it must satisfy the condition that all keys in 
 
 
 
 L
 
 
 {\displaystyle L}
 
 are smaller than 
 
 
 
 k
 
 
 {\displaystyle k}
 
 and all keys in 
 
 
 
 R
 
 
 {\displaystyle R}
 
 are greater than 
 
 
 
 k
 
 
 {\displaystyle k}
 
.

Join-based tree algorithms open-in-new

Join-based tree algorithms