ON K-DIMENSIONAL BALANCED BINARY-TREES

An amortized analysis of the insertion and deletion algorithms of k-di mensional balanced binary trees (kBB-trees) is performed. It is shown that the total rebalancing time for a mixed sequence of m insertions a nd deletions in a kBB-tree of size n is O(k(m + n)). Based on ass-tree s, a self-organizing tree, called a self-organizing balanced binary tr ee, is defined. It is shown that the average access time for an item s tored in the tree is optimal to within a constant factor, while the wo rst-case access time is logarithmic. The amortized analysis of kBB-tre es leads to the result that the total update time for a mixed sequence of m accesses, insertions, and (restricted) deletions in a self-organ izing balanced binary tree initially storing n data items is O(m + n). (C) 1996 Academic Press, Inc.