Narrow Results

In this paper we present a strategy to maintain a dynamic optimal binary search tree. The algorithms for insertion and deletion use swapping as the basic operation. Since in average situations the tree reorganization is limited to local changes, it can be favourably compared with the local balancing algorithms. The present algorithms dynamically maintain the optimal tree with an amortized time of O(log₂ n), where n is the total number of nodes in the tree. In the worst case situations, the algorithms take only O(n) time. This is significant when they are compared to the algorithms producing static optimal binary search trees.

The scheduling problem for dynamic tree-structured task graphs is studied and is shown to be inherently more difficult than the static case. It is shown that any online scheduling algorithm, deterministic or randomized, has competitive ratio Ω((1/g)/log_d(1/g)) for trees with granularity g and degree at most d. On the other hand, it is known that static trees with arbitrary granularity can be scheduled to within twice the optimal schedule. It is also shown that the lower bound is tight: there is a deterministic online tree scheduling algorithm that has competitive ratio O((1/g)/log_d(1/g)). Thus, randomization does not help.