G; if (G != null) { if (X == left_child(G)) left_child(G) = N; else right_child(G) = N; } else tree->root = N; // N is the new root of the total tree if (b == 0) break; // Height does not change: Leave the loop // Height(N) decreases by 1 (== old Height(X)-1) } // If (b != 0) the height of the total tree decreases by 1. The retracing can stop if the balance factor becomes ±1 (it must have been 0) meaning that the height of that subtree remains unchanged. If the balance factor becomes 0 (it must have been ±1) then the height of the subtree decreases by one and the retracing needs to continue. If the balance factor temporarily becomes ±2, this has to be repaired by an appropriate rotation. It depends on the balance factor of the sibling Z (the higher child tree in figure 2) whether the height of the subtree decreases by one –and the retracing needs to continue– or does not change (if Z has the balance factor 0) and the whole tree is in AVL-shape. The time required is for lookup, plus a maximum of retracing levels ( on average) on the way back to the root, so the operation can be completed in time. 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, 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. The function Join on two AVL trees and and a key will return a tree containing all elements in , as well as . It requires to be greater than all keys in and smaller than all keys in . If the two trees differ by height at most one, Join simply create a new node with left subtree , root and right subtree . Otherwise, suppose that is higher than for more than one (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