Optimal alphabetic binary trees have a wide variety of applications in computer science and information systems. Fast algorithms for building such trees in O(n log n) do exist. However, no existing algorithm makes it possible to insert in (or delete from) the tree without losing its optimality. In this paper, we propose an algorithm to insert into or delete from an optimal binary alphabetic tree in linear time keeping the tree optimal after insertion or deletion. We show that both insertion and deletion of a node can be done in O(n) time provided its weight is not bigger than the higher weight of its two neighbouring nodes. This algorithm makes it possible to have a dynamic optimal alphabetic tree with reasonable complexity and allows us to expand the domain of weight sequences whose optimal alphabetic trees can be obtained in linear time.
Key words: Optimal alphabetic tree, insertion and deletion, linear-time alphabetic trees.
DIMACS Home Page