Balanced Tree

noun

say it: “BAL-unst TREE” /ˈbælənst triː/

A tree whose branches are all about the same length, so it stays short and every path down is quick.

What is a balanced tree?

A balanced tree keeps its sides about equally tall, so its height stays close to log n. That's what keeps a binary search tree fast: fed sorted data, an unbalanced one becomes a line, and search becomes O(n).

In a sentence

  • “Searching a balanced tree of a million contacts takes about 20 checks.”

Level: Journeyman · More Data Structures terms at this level

Updated