= Solution
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.
Back to article page
