17.1 BST Performance

Tree Height

One unforunate feature of BSTs is that they range from a best-case "bushy" tree to a worst-case "spindly" tree.

In the best case, our tree will have height $\Theta(log N)$ , whereas in the worst case our tree has a height of $\Theta(N)$ , at which point it basically becomes a linked list. For example, contains on a "spindly" BST would take linear time.

Both trees below have a height H = 3, yet the left tree is able to hold many more items than the left.

Previous17. B-Trees Next17.2 Big O vs. Worst Case

Last updated 1 year ago

Tree Height

One unforunate feature of BSTs is that they range from a best-case "bushy" tree to a worst-case "spindly" tree.

In the best case, our tree will have height

\Theta(log N)

, whereas in the worst case our tree has a height of

\Theta(N)

, at which point it basically becomes a linked list. For example, contains on a "spindly" BST would take linear time.

Both trees below have a height H = 3, yet the left tree is able to hold many more items than the left.