Glossary: Data Structures and Algorithms in C++

Self-balancing tree

Also written: self-balancing trees, AVL tree, AVL trees, red-black tree, red-black trees

A tree, such as an AVL or red-black tree, that rearranges nodes as you insert to keep its height near log₂ n, avoiding the chain that sorted input creates. std::map is usually a red-black tree.