Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-23T21:22:55.681Z Has data issue: false hasContentIssue false
  • English
  • Français

Red-black trees in a functional setting

Published online by Cambridge University Press:  01 July 1999

CHRIS OKASAKI
CHRIS OKASAKI
Affiliation:
School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, Pennsylvania 15213, USA
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Everybody learns about balanced binary search trees in their introductory computer science classes, but even the stouthearted tremble at the thought of actually implementing such a beast. The details surrounding rebalancing are usually just too messy. To show that this need not be the case, we present an algorithm for insertion into red-black trees (Guibas and Sedgewick, 1978) that any competent programmer should be able to implement in fifteen minutes or less.

Type
FUNCTIONAL PEARL
Information
Journal of Functional Programming , Volume 9 , Issue 4 , July 1999 , pp. 471 - 477
Copyright
© 1999 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.