= Solution
\b[Yes, provided balancing guarantees logarithmic height.] In a suitably maintained <balanced binary tree> of height $O(\log(n+1))$, insertion searches one root-to-leaf path and deletion of the minimum follows the leftmost path. Reconnecting the tree and performing the required rebalancing also costs at most a constant amount per level for the standard logarithmic-time schemes. Thus both operations take $O(\log(n+1))$ time, conventionally written $O(\log n)$ for nontrivial sizes. Merely calling a tree approximately balanced would not prove that height bound; it is the balancing guarantee that matters. Without it, a <binary search tree> can have linear height.
Back to article page
