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.