A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
Rudolf Fleischer · International Journal of Foundations of Computer Science · 1996
In this paper we show how a slight modification of (a, 2b)-trees allows us to perform member and neighbor queries in O( log n) time and updates in O(1) worst-case time (once the position of the inserted or deleted key is known). Our data structure is quite natural and much simpler than previous worst-case optimal solutions. It is based on two techniques : 1) bucketing, i.e., storing an ordered list of 2 log n keys in each leaf of an (a, 2b) tree, and 2) preventive splitting, i.e., splitting nodes before they can grow bigger than allowed. If only insertions are allowed, it can also be used as a finger search tree with O( log * n) worst-case update time.