Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / b

Follow the unique branch in which the new key could belong. At an equal key, keep the existing node so that duplicate insertion does not change the represented set:

insert :: Ord a => a -> STree a -> STree a
insert y Empty = Node Empty y Empty
insert y (Node left x right) =
  case compare y x of
    LT -> Node (insert y left) x right
    EQ -> Node left x right
    GT -> Node left x (insert y right)

The Haskell Ord class supplies the three-way comparison. Each visited nonempty node costs one such comparison; rebuilding a node preserves all untouched subtrees. The inserted key satisfies every comparison along its search path, so it obeys both the local and ancestor binary search tree inequalities.

For height of a binary tree $h$, the worst search costs $\boxed{\Theta (h)\text{ comparisons}}$ when it reaches the bottom. With $n$ existing nodes, a chain can require $n$ comparisons, giving a worst case of $\Theta (n)$. Under the standard random-insertion model, distinct keys arrive in a uniformly random order and the expected path length is $\Theta (\log (n+1))$. Thus the usual average-case answer is $\boxed{\Theta (\log n)}$ for growing $n$, but this expectation needs the stated distribution: an arbitrary unbalanced binary search tree has no logarithmic guarantee.