Simple Balanced Binary Search Trees

Prabhakar Ragde
(University of Waterloo, Waterloo, Ontario, Canada)

Efficient implementations of sets and maps (dictionaries) are important in computer science, and balanced binary search trees are the basis of the best practical implementations. Pedagogically, however, they are often quite complicated, especially with respect to deletion. I present complete code (with justification and analysis not previously available in the literature) for a purely-functional implementation based on AA trees, which is the simplest treatment of the subject of which I am aware.

In James Caldwell, Philip Hölzenspies and Peter Achten: Proceedings 3rd International Workshop on Trends in Functional Programming in Education (TFPIE 2014), Soesterberg, The Netherlands, 25th May 2014, Electronic Proceedings in Theoretical Computer Science 170, pp. 78–87.
Published: 12th December 2014.

ArXived at: https://dx.doi.org/10.4204/EPTCS.170.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org