Balancing binary trees provides efficient searching with overall O(log n) performance for retrieval and maintenance operations. The first data structure of this kind was proposed by Adelson-Velskii and Landis 50 years ago, and is now known as the AVL tree. Since then, balanced binary trees have been suggested based on growth-by-splitting, as in dynamic files for B-trees and extendible hashing. Popular red-black (RB) trees actually implement two-element B-trees, while binary labeling of the tree nodes is just for convenience.

Both types of trees, AVL and RB, show similar O(log n) behavior. According to this paper, the general performance for both is basically the same. Differences depend on the statistical variations in the distribution of keys and the mixture of operations. The distinction lies in programming complexity. For example, a lecture on the AVL details takes about an hour, while explaining the RB takes less than ten minutes.