article

Alternatives to two classic data structures

Author:

Chris OkasakiAuthors Info & Claims

ACM SIGCSE Bulletin, Volume 37, Issue 1

Pages 162 - 165

https://doi.org/10.1145/1047124.1047407

Published: 23 February 2005 Publication History

Get Access

Abstract

Red-black trees and leftist heaps are classic data structures that are commonly taught in Data Structures (CS2) and/or Algorithms (CS7) courses. This paper describes alternatives to these two data structures that may offer pedagogical advantages for typical students.

References

[1]

G. M. Adel'son-Vel'skiǐ and E. M. Landis. An algorithm for the organization of information. Soviet Mathematics--Doklady, 3(5):1259--1263, Sept. 1962. English translation of Russian orginal appearing in Doklady Akademia Nauk SSSR, 146:263--266.

Google Scholar

[2]

S. Cho and S. Sahni. Weight-biased leftist trees and modified skip lists. ACM Journal of Experimental Algorithmics, 1998. Article 2.

Digital Library

Google Scholar

[3]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT Press, 2001.

Digital Library

Google Scholar

[4]

C. A. Crane. Linear lists and priority queues as balanced binary trees. PhD thesis, Computer Science Department, Stanford University, Feb. 1972. Available as STAN-CS-72-259.

Digital Library

Google Scholar

[5]

L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In IEEE Symposium on Foundations of Computer Science, pages 8--21, Oct. 1978.

Digital Library

Google Scholar

[6]

D. E. Knuth. Searching and Sorting, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973.

Digital Library

Google Scholar

[7]

C. Okasaki. Red-black trees in a functional setting. Journal of Functional Programming, 9(4):471--477, July 1999.

Digital Library

Google Scholar

[8]

C. Okasaki. Fun with binary heap trees, pages 1--16. Palgrave MacMillan, 2003.

Google Scholar

[9]

M. A. Weiss. Data Structures & Algorithm Analysis in Java. Addison-Wesley, 1998.

Digital Library

Google Scholar

Index Terms

Alternatives to two classic data structures
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Directory structures
        B-trees
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees

Recommendations

Alternatives to two classic data structures
SIGCSE '05: Proceedings of the 36th SIGCSE technical symposium on Computer science education

Red-black trees and leftist heaps are classic data structures that are commonly taught in Data Structures (CS2) and/or Algorithms (CS7) courses. This paper describes alternatives to these two data structures that may offer pedagogical advantages for ...
Rank-Balanced Trees

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the ...
Comparative performance evaluation of the AVL and red-black trees
BCI '12: Proceedings of the Fifth Balkan Conference in Informatics

The AVL and red-black trees are the suboptimal variants of the binary search trees which can achieve the logarithmic performance of the search operation withot an excessive cost of the optimal balancing. After presenting a brief theoretical background, ...

Comments

Information & Contributors

Information

Published In

ACM SIGCSE Bulletin Volume 37, Issue 1

2005

562 pages

ISSN:0097-8418

DOI:10.1145/1047124

Issue’s Table of Contents

SIGCSE '05: Proceedings of the 36th SIGCSE technical symposium on Computer science education
February 2005
610 pages
ISBN:1581139977
DOI:10.1145/1047344
Conference Chairs:
Wanda Dann
Ithaca College
,
Tom Naps
University of Wisconsin - Oshkosh
,
Program Chairs:
Paul Tymann
Rochester Institute of Technology
,
Doug Baldwin
SUNY Geneseo

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 February 2005

Published in SIGCSE Volume 37, Issue 1

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
869
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)2

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Index Terms

Recommendations