Optimized Deletion From an AVL Tree

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.