How it works
Inserting sorted keys into an unbalanced BST produces a chain, and search degrades from logarithmic to linear. Self-balancing trees exist to prevent exactly this.
State the shape assumption whenever quoting logarithmic search.
Common error
Quoting log n for a BST unconditionally. That holds only while the tree stays balanced.
Worked example
Example
Insertion order in an unbalanced BST: 1, 2, 3, 4
Shape: each key becomes the right child of its predecessor
Search for 4: visits every nodeA sorted insertion order can make an unbalanced BST behave like a linked list. Search time depends on height: balanced height supports logarithmic paths, while a chain can have linear height.
Exercises
6.4.1 · Explain
How many nodes may a search for the last key visit in a chain of n nodes?
Show solution
It may visit all n nodes, giving linear worst-case search time.
6.4.2 · Explain
Why does balance improve worst-case search without changing the BST ordering rule?
Show solution
Balance limits height while preserving the smaller-left, larger-right ordering. A search therefore makes fewer sequential decisions.