Glossary: Data Structures and Algorithms in Java

balanced tree

Also written: balanced, self-balancing tree, self-balancing trees

A tree whose subtrees have similar heights, so its height is about log₂ n and lookups are O(log n). Self-balancing trees such as AVL and red-black trees rearrange nodes on insert to stay balanced.