Efficient maintenance of binary search trees
Tony W. Lai · 1992
This thesis is concerned with the efficient maintenance of binary search trees. Two techniques are used to improve the performance of binary search trees: balance and adaptation. In the area of balance techniques, we introduce the class of k-stratum trees, which have the property that any two external nodes are no more than k levels apart. This implies that the height of a k-stratum tree of n internal nodes is at most $\lceil \log(n + 1)\rceil + k - 1.$ We prove that 2-stratum trees of height at most$$\left\lceil \log(n + 1) + {1\over\sqrt{\log(n + 1)}}\right\rceil$$can be updated in $O(\log n)$ amortized time. We also prove that trees with at most log* $n-3$ incomplete levels can be updated in $O(\log n)$ amortized time with amortized constant linkage cost (CLC); that is, with a constant amortized number of pointer changes per operation. In the area of adaptation techniques, we investigate constant linkage cost adaptive heuristics. We prove that no heuristic with an amortized linkage cost of $o(\log n)$ can be dynamically optimal. We also propose a new method for analyzing the expected time based on measuring what we call the expected amortized time, and we present four randomized heuristics. These include a worst-case-CLC heuristic that supports only accesses and has an expected search time within a constant factor of the search time of an optimal static tree if accesses are chosen by a user that cannot inspect the accessed tree; and an expected-CLC heuristic that supports both accesses and updates and has an expected operation time of $O(\log n).$ Our heuristics require only constant extra space and have logarithmic expected performance even if operations are performed by an adversary capable of inspecting the tree.