Categories and Subject Descriptors: E.1 [Data Structures]
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Balanced trees, probablistic algebraic specification, randomized data structures, search trees, self-organizing data structures
Selected references
- Brian Allen and Ian Munro. Self-organizing binary search trees. Journal of the ACM, 25(4):526-535, October 1978.
- Cecilia R. Aragon and Raimund G. Seidel. Randomized search trees. In 30th Annual Symposium on Foundations of Computer Science, pages 540-545, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Joseph Culberson. The effect of updates in binary search trees. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 205-212, Providence, Rhode Island, 6-8 May 1985.
- Leo J. Guibas and Robert Sedgewick. A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science, pages 8-21, Ann Arbor, Michigan, 16-18 October 1978. IEEE.
- Thomas N. Hibbard. Some combinatorial properties of certain trees with applications to searching and sorting. Journal of the ACM, 9(1):13-28, January 1962.
- Arne T. Jonassen and Donald E. Knuth. A trivial algorithm whose analysis isn't. Journal of Computer and System Sciences, 16(3):301-322, June 1978.
- Donald E. Knuth. Deletions that preserve randomness. IEEE Transactions on Software Engineering, 3(5):351-359, September 1977.
- J. Nievergelt and E. M. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing, 2(1):33-43, March 1973.
- Salvador Roura and Conrado Martinez. Randomization of search trees by subtree size. In Josep Díaz and Maria Serna, editors, Algorithms -- ESA '96, Fourth Annual European Symposium, volume 1136 of Lecture Notes in Computer Science, pages 91-106, Barcelona, Spain, 25-27 September 1996. Springer.
- R. Seidel and C. R. Aragon. Randomized search trees. Algorithmica, 16(4/5):464-497, October/November 1996.