Self-adjusting binary trees

ABSTRACT

We use the idea of self-adjusting trees to create new, simple data structures for priority queues (which we call heaps) and search trees. Unlike other efficient implementations of these data structures, self-adjusting trees have no balance condition. Instead, whenever the tree is accessed, certain adjustments take place. (In the case of heaps, the adjustment is a sequence of exchanges of children, in the case of search trees the adjustment is a sequence of rotations.) Self-adjusting trees are efficient in an amortized sense: any particular operation may be slow but any sequence of operations must be fast. Self-adjusting trees have two advantages over the corresponding balanced trees in both applications. First, they are simpler to implement because there are fewer cases in the algorithms. Second, they are more storage-efficient because no balance information needs to be stored. Furthermore, a self-adjusting search tree has the remarkable property that its running time (for any sufficiently long sequence of search operations) is within a constant factor of the running time for the same set of searches on any fixed binary tree. It follows that a self-adjusting tree is (up to a constant factor) as fast as the optimal fixed tree for a particular probability distribution of search requests, even though the distribution is unknown.

REFERENCES

• 1: G. M. Adel'son-Vel'skii and E. M. Landis, "An algorithm for the organization of information," Soviet Math. Dokl., 3 (1962), 1259-1262.
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Brian Allen , Ian Munro, Self-Organizing Binary Search Trees, Journal of the ACM (JACM), v.25 n.4, p.526-535, Oct. 1978 [doi>10.1145/322092.322094]
• 4: S. W. Bent, Dynamic Weighted Data Structures, TM STAN-CS-82-916 Computer Science Dept., Stanford University, Stanford, CA 94305, 1982.
• 5: S. W. Bent, D. D. Sleator and R. E. Tarjan, "Biased 2-3 trees," Proc. Twenty-First Annual IEEE Symp. on Foundations of Computer Science (1980), 248-254
• 6: S. W. Bent, D. D. Sleator and R. E. Tarjan, "Biased search trees," to appear.
• 7: J. R. Bitner, "Heuristics that dynamically organize data structures," SIAM Journal on Computing8 (1979), 82-110.
• 8: M. R. Brown, The Analysis Of a Practical and Nearly Optimal Priority Queue, TM STAN-CS-77-600 Computer Science Dept., Stanford University, Stanford, CA 94305, 1977.
• 9: C. A. Crane, Linear Lists and Priority Queues as Balanced Binary Trees, TM STAN-CS-72-259 Computer Science Dept., Stanford University, Stanford, CA 94305, 1972.
• 10: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 11: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 12: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 13: J. Nievergelt and E. M. Reingold, "Binary search trees of bounded balance," SIAM journal on Computing, 2 (1973) 33-43.
• 14: Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 [doi>10.1145/359997.360000]
• 15: D. D. Sleator, An O(nmlog n) Algorithm for Maximum Network Flow, TM STAN-CS-80-831 Computer Science Dept., Stanford University, Stanford, CA 94305, 1980.
• 16: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 17: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 18: Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Theory