Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where

The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information".

[2] It is the first self-balancing binary search tree data structure to be invented.

For holding the AVL balance information, two bits per node are sufficient.

Read-only operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree, but modifications have to observe and restore the height balance of the sub-trees.

[12] So it is necessary to check each of the node's ancestors for consistency with the invariants of AVL trees: this is called "retracing".

However, if the temporary balance factor is ±2, the subtree rooted at this node is AVL unbalanced, and a rotation is needed.

[9]: 52  With insertion as the code below shows, the adequate rotation immediately perfectly rebalances the tree.

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.

Starting at this subtree, it is necessary to check each of the ancestors for consistency with the invariants of AVL trees.

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.

(Unlike insertion where a rotation always balances the tree, after delete, there may be BF(Z) ≠ 0 (see figures 2 and 3), so that after the appropriate single or double rotation the height of the rebalanced subtree decreases by one meaning that the tree has to be rebalanced again on the next higher level.)

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.

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.

Then fast bulk operations on insertions or deletions can be implemented based on these set functions.

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 algorithm for intersection or difference is similar, but requires the Join2 helper routine that is the same as Join but without the middle key.

If during a modifying operation the height difference between two child subtrees changes, this may, as long as it is < 2, be reflected by an adaption of the balance information at the parent.

During insert and delete operations a (temporary) height difference of 2 may arise, which means that the parent subtree has to be "rebalanced".

The given repair tools are the so-called tree rotations, because they move the keys only "vertically", so that the ("horizontal") in-order sequence of the keys is fully preserved (which is essential for a binary-search tree).

There are four possible variants of the violation: And the rebalancing is performed differently: Thereby, the situations are denoted as C B, where C (= child direction) and B (= balance) come from the set { Left, Right } with Right := −Left.

In its upper half, node X has two child trees with a balance factor of +2.

Otherwise the leaf layer reaches level h+1, so that the height of the rotated tree decreases.

The result of the final left rotation is shown in the lower third of the figure.

For maintaining the AVL (or RB) tree's invariants, rotations play an important role.

AVL deletions requiring O(log n) rotations in the worst case are also O(1) on average.

For insertions and deletions, Ben Pfaff shows in 79 measurements a relation of AVL/RB between 0.677 and 1.077 with median ≈0.947 and geometric mean ≈0.910.