Editing AVL tree (section)

===Set operations and bulk operations===
In addition to the single-element insert, delete and lookup operations, several set operations have been defined on AVL trees: [[Union (set theory)|union]], [[Intersection (set theory)|intersection]] and [[set difference]]. Then fast ''bulk'' operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, ''Split'' and ''Join''. With the new operations, the implementation of AVL trees can be more efficient and highly-parallelizable.<ref name="join-based">{{Citation |last1=Blelloch |first1=Guy E. |title=Symposium on Parallel Algorithms and Architectures |pages=253–264 |year=2016 |chapter=Just join for parallel ordered sets |publisher=ACM |arxiv=1602.02120 |doi=10.1145/2935764.2935768 |isbn=978-1-4503-4210-0 |s2cid=2897793 |last2=Ferizovic |first2=Daniel |last3=Sun |first3=Yihan}}.</ref>

The function ''Join'' on two AVL trees {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} and a key {{mvar|k}} will return a tree containing all elements in {{math|''t''<sub>1</sub>}}, {{math|''t''<sub>2</sub>}} as well as {{mvar|k}}. It requires {{mvar|k}} to be greater than all keys in {{math|''t''<sub>1</sub>}} and smaller than all keys in {{math|''t''<sub>2</sub>}}. If the two trees differ by height at most one, ''Join'' simply create a new node with left subtree {{math|''t''<sub>1</sub>}}, root {{mvar|k}} and right subtree {{math|''t''<sub>2</sub>}}. Otherwise, suppose that {{math|''t''<sub>1</sub>}} is higher than {{math|''t''<sub>2</sub>}} for more than one (the other case is symmetric). ''Join'' follows the right spine of {{math|''t''<sub>1</sub>}} until a node {{mvar|c}} which is balanced with {{math|''t''<sub>2</sub>}}. At this point a new node with left child {{mvar|c}}, root {{mvar|k}} and right child {{math|''t''<sub>2</sub>}} is created to replace c. The new node satisfies the AVL invariant, and its height is one greater than {{mvar|c}}. The increase in height can increase the height of its ancestors, possibly invalidating the AVL invariant of those nodes. This can be fixed either with a double rotation if invalid at the parent or a single left rotation if invalid higher in the tree, in both cases restoring the height for any further ancestor nodes. ''Join'' will therefore require at most two rotations. The cost of this function is the difference of the heights between the two input trees.
{{Collapse top|Pseudocode implementation for the Join algorithm}}
 '''function''' JoinRightAVL(T<sub>L</sub>, k, T<sub>R</sub>)
     (l, k', c) = expose(T<sub>L</sub>)
     '''if''' (Height(c) <= Height(T<sub>R</sub>)+1)
        T' = Node(c, k, T<sub>R</sub>)
        if (Height(T') <= Height(l)+1) then '''return''' Node(l, k', T')
        else '''return''' rotateLeft(Node(l, k', rotateRight(T')))
     '''else''' 
         T' = JoinRightAVL(c, k, T<sub>R</sub>)
         T<nowiki>''</nowiki> = Node(l, k', T')
         '''if''' (Height(T') <= Height(l)+1) '''return''' T<nowiki>''</nowiki>
         '''else''' '''return''' rotateLeft(T<nowiki>''</nowiki>)

 '''function''' JoinLeftAVL(T<sub>L</sub>, k, T<sub>R</sub>)
   /* symmetric to JoinRightAVL */

 '''function''' Join(T<sub>L</sub>, k, T<sub>R</sub>)
     '''if''' (Height(T<sub>L</sub>)>Height(T<sub>R</sub>)+1) '''return''' JoinRightAVL(T<sub>L</sub>, k, T<sub>R</sub>)
     '''if''' (Height(T<sub>R</sub>)>Height(T<sub>L</sub>)+1) '''return''' JoinLeftAVL(T<sub>L</sub>, k, T<sub>R</sub>)
     '''return''' Node(T<sub>L</sub>, k, T<sub>R</sub>)
Here Height(v) is the height of a subtree (node) {{mvar|v}}. (l,k,r) = expose(v) extracts {{mvar|v}}'s left child {{mvar|l}}, the key {{mvar|k}} of {{mvar|v}}'s root, and the right child {{mvar|r}}. Node(l,k,r) means to create a node of left child {{mvar|l}}, key {{mvar|k}}, and right child {{mvar|r}}.
{{Collapse bottom}}

To split an AVL tree into two smaller trees, those smaller than key {{mvar|k}}, and those greater than key {{mvar|k}}, first draw a path from the root by inserting {{mvar|k}} into the AVL. After this insertion, all values less than {{mvar|k}} will be found on the left of the path, and all values greater than {{mvar|k}} 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. The cost of ''Split'' is {{math|O(log ''n'')}}, order of the height of the tree.
{{Collapse top|Pseudocode implementation for the Split algorithm}}
 '''function''' Split(T, k)
     '''if''' (T = nil) return (nil, false, nil)
     (L,m,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'))
{{Collapse bottom}}

The union of two AVL trees {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} representing sets {{mvar|A}} and {{mvar|B}}, is an AVL {{mvar|''t''}} that represents {{math|''A'' ∪ ''B''}}.

{{Collapse top|Pseudocode implementation for the Union algorithm}}
 '''function''' Union(t<sub>1</sub>, t<sub>2</sub>):
     '''if''' t<sub>1</sub> = nil:
         '''return''' t<sub>2</sub>
     '''if''' t<sub>2</sub> = nil:
         '''return''' t<sub>1</sub>
     (t<sub><</sub>, b, t<sub>></sub>) = Split(t<sub>2</sub>, t<sub>1</sub>.root)
     '''return''' Join(Union(left(t<sub>1</sub>), t<sub><</sub>), t<sub>1</sub>.root, Union(right(t<sub>1</sub>), t<sub>></sub>))

Here, ''Split'' is presumed to return two trees: one holding the keys less its input key, one holding the greater keys. (The algorithm is [[persistent data structure|non-destructive]], but an in-place destructive version exists as well.)
{{Collapse bottom}}

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. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the AVL tree. Since ''Split'' calls ''Join'' but does not deal with the balancing criteria of AVL trees directly, such an implementation is usually called the [[Join-based tree algorithms|"join-based" implementation]].

The complexity of each of union, intersection and difference is <math>\text{O}\left(m \log \left({n\over m}+1\right)\right)</math> for AVL trees of sizes <math>m</math> and <math>n \; (\ge m)</math>. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executed [[parallel programming|in parallel]] with a [[Analysis of parallel algorithms|parallel depth]] <math>\text{O}(\log m\log n)</math>.<ref name="join-based" /> When <math>m=1</math>, the join-based implementation has the same computational DAG as single-element insertion and deletion.