McGraw-Hill OnlineMcGraw-Hill Higher EducationLearning Center
Student Center | Instructor's Center | Introduction to Algorithms | Home
Glossary A-B
Glossary B-D
Glossary D-F
Glossary F-J
Glossary J-M
Glossary M-O
Glossary O-P
Glossary P-S
Glossary S-T
Glossary T-Z
Chapter Objectives
Chapter Overview
Glossary
PowerPoint Slides
Algorithm Pseudocode
Feedback
Help Center


small text cover image
Introduction to Algorithms, 2/e
Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University
Red-Black Trees

Chapter Objectives

Red-black trees

  • A variation of binary search trees.
  • Balanced: height is O(lg n), where n is the number of nodes.
  • Operations will take O(lg n) time in the worst case.


[These notes are a bit simpler than the treatment in the book, to make them more
amenable to a lecture situation. Our students first see red-black trees in a course
that precedes our algorithms course. This set of lecture notes is intended as a
refresher for the students, bearing in mind that some time may have passed since
they last saw red-black trees.
The procedures in this chapter are rather long sequences of pseudocode. You might
want to make arrangements to project them rather than spending time writing them
on a board.]










Copyright2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.