Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree

Russell A. Brown

This article compares the performance of the AVL tree to the performance of the bottom-up, top-down, and left-leaning red-black trees. The bottom-up red-black tree is faster than t…