= -1; Z = X; // Height(Z) increases by 1 continue; } } // After a rotation adapt parent link: // N is the new root of the rotated subtree // Height does not change: Height(N) == old Height(X) parent(N) = 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 break; // There is no fall thru, only break; or continue; } // Unless loop is left via break, the height of the total tree increases by 1. In order to update the balance factors of all nodes, first observe that all nodes requiring correction lie from child to parent along the path of the inserted leaf. If the above procedure is applied to nodes along this path, starting from the leaf, then every node in the tree will again have a balance factor of −1, 0, or 1. The retracing can stop if the balance factor becomes 0 implying that the height of that subtree remains unchanged. If the balance factor becomes ±1 then the height of the subtree increases by one and the retracing needs to continue. If the balance factor temporarily becomes ±2, this has to be repaired by an appropriate rotation after which the subtree has the same height as before (and its root the balance factor 0). 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. Delete The preliminary steps for deleting a node are described in section Binary search tree#Deletion. There, the effective deletion of the subject node or the replacement node decreases the height of the corresponding child tree either from 1 to 0 or from 2 to 1, if that node had a child. Starting at this subtree, it is necessary to check each of the ancestors for consistency with the invariants of AVL trees. This is called "retracing". Since with a single deletion the height of an AVL subtree cannot decrease by more than one, the temporary balance factor of a node will be in the range from −2 to +2. If the balance factor remains in the range from −1 to +1 it can be adjusted in accord with the AVL rules. If it becomes ±2