Glossary: Data Structures and Algorithms in Rust

Balanced tree

Also written: balanced, unbalanced, self-balancing trees, AVL trees, red-black trees

A tree whose two subtrees at each node have about the same height, so its height is about log₂ n and lookups are O(log n). Inserting already-sorted IDs makes an unbalanced chain; self-balancing trees such as AVL and red-black trees rearrange nodes to avoid that.