The AVL and red-black trees are binary search trees that guarantee O ( log n ) insertion, deletion, and search. This guarantee requires rebalancing the trees, potentially for each insertion or deletion. Benchmarks demonstrate that the AVL tree is often faster than three red-black tree variants for insertion and deletion, and as fast or faster for search. An improved AVL tree deletion algorithm reduces the rebalancing operations associated with deletion by 20 percent.

An AVL tree is a binary search tree that guarantees O ( log n ) search. The guarantee is obtained at the cost of rebalancing the AVL tree, potentially after every insertion or deletion. This article proposes a deletion algorithm that decreases the rebalancing required after deletion compared to the rebalancing required after deletion by a previously reported algorithm.