Preface xvii

Chapter 3 covers lists, stacks, and queues. This chapter includes a discussion of the STL

vector and list classes, including material on iterators, and it provides implementations

of a signiﬁcant subset of the

STL vector and list classes.

Chapter 4 covers trees, with an emphasis on search trees, including external search

trees (B-trees). The

UNIX ﬁle system and expression trees are used as examples. AVL trees

and splay trees are introduced. More careful treatment of search tree implementation details

is found in Chapter 12. Additional coverage of trees, such as ﬁle compression and game

trees, is deferred until Chapter 10. Data structures for an external medium are considered

as the ﬁnal topic in several chapters. Included is a discussion of the STL

set and map classes,

including a signiﬁcant example that illustrates the use of three separate maps to efﬁciently

solve a problem.

Chapter 5 discusses hash tables, including the classic algorithms such as sepa-

rate chaining and linear and quadratic probing, as well as several newer algorithms,

namely cuckoo hashing and hopscotch hashing. Universal hashing is also discussed, and

extendible hashing is covered at the end of the chapter.

Chapter 6 is about priority queues. Binary heaps are covered, and there is additional

material on some of the theoretically interesting implementations of priority queues. The

Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12.

Chapter 7 covers sorting. It is very speciﬁc with respect to coding details and analysis.

All the important general-purpose sorting algorithms are covered and compared. Four

algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. New to

this edition is radix sort and lower bound proofs for selection-related problems. External

sorting is covered at the end of the chapter.

Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a

short and speciﬁc chapter that can be skipped if Kruskal’s algorithm is not discussed.

Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only

because they frequently occur in practice but also because their running time is so heavily

dependent on the proper use of data structures. Virtually all of the standard algorithms

are presented along with appropriate data structures, pseudocode, and analysis of running

time. To place these problems in a proper context, a short discussion on complexity theory

(including NP-completeness and undecidability) is provided.

Chapter 10 covers algorithm design by examining common problem-solving tech-

niques. This chapter is heavily fortiﬁed with examples. Pseudocode is used in these later

chapters so that the student’s appreciation of an example algorithm is not obscured by

implementation details.

Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and

6 and the Fibonacci heap, introduced in this chapter, are analyzed.

Chapter 12 covers search tree algorithms, the sufﬁx tree and array, the k-d tree, and

the pairing heap. This chapter departs from the rest of the text by providing complete and

careful implementations for the search trees and pairing heap. The material is structured so

that the instructor can integrate sections into discussions from other chapters. For example,

the top-down red-black tree in Chapter 12 can be discussed along with AVL trees (in

Chapter 4).

Chapters 1 to 9 provide enough material for most one-semester data structures courses.

If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis

could cover chapters 7 to 11. The advanced data structures analyzed in Chapter 11 can

easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9