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
Augmenting Data Structures

Chapter Objectives

We’ll be looking at methods for designing algorithms. In some cases, the design
will be intermixed with analysis. In other cases, the analysis is easy, and it’s the
design that’s harder.

Augmenting data structures

  • It’s unusual to have to design an all-new data structure from scratch.
  • It’s more common to take a data structure that you know and store additional information in it.
  • With the new information, the data structure can support new operations.

But. . . you have to figure out how to correctly maintain the new information without loss of efficiency.


We’ll look at a couple of situations in which we augment red-black trees.










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.