Optimized Deletion From an AVL Tree

An AVL tree is a binary search tree that guarantees $ O\left( \log n \right ) $ 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 reduces rebalancing after deletion by 19 percent compared to previously reported deletion algorithms.