Glossary: Data Structures and Algorithms

Balanced tree

Also written: balanced, unbalanced

A tree whose subtrees have about the same height at every node, so its height is about log₂ n and lookups are O(log n). An unbalanced tree, such as one built from sorted inserts, can become a long chain.