We propose an algorithm to insert into or delete from a weighted 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.
Key words : Optimal alphabetic trees, insertion and deletion, linear time alphabetic trees.
DIMACS Home Page