Orient BlackSwan

About the BookAbout the AuthorTable of Contents

This new edition provides a comprehensive and technically rigorous introduction to data structures such as arrays, stacks, queues, linked lists, trees and graphs and techniques such as sorting hashing that form the basis of all software. In addition, this text presents advanced or specialized data structures such as priority queues, efficient binary search trees, multiway search trees and digital search structures. The book has been updated to include the latest features of the C++ language. Features such as exceptions and templates are now incorporated throughout the text along with limited exposure to STL. Treatment of queues, iterators and dynamic hashing has been improved. The book now discusses topics such as secure hashing algorithms, weightbiased leftist trees, pairing heaps, symmetric min–max heaps, interval heaps, top-down splay trees, B+ trees and suffix trees. Red–black trees have been made more accessible. The section on multiway tries has been significantly expanded and discusses several trie variations and their application to Internet packet forwarding.

Ellis Horowitz is a Professor of Computer Science and Electrical Engineering at the University of Southern California. Dr. Horowitz is the author of ten books and numerous journal articles and refereed conference proceedings.

Sartaj Sahni is a Distinguished Professor and Chair of Computer and Information Sciences and Engineering at the University of Florida. Dr. Sahni has published over three hundred research papers and written 15 texts.

Dinesh Mehta is a Professor and Assistant Department Head of Mathematical and Computer Sciences at the Colorado School of Mines. Dr. Mehta has published over 30 journal and conference papers.

CHAPTER 1 BASIC CONCEPTS
1.1 Overview: System Life Cycle
1.2 Object-Oriented Design
       1.2.1 Algorithmic Decomposition versus 00 Decomposition
       1.2.2 Fundamental Definitions and Concepts of 00 Programming
       1.2.3 Evolution of Programming Languages and History of C++
1.3 Data Abstraction and Encapsulation
1.4 Basics of C++
       1.4.1 Program Organization in C++
       1.4.2 Scope in C++
       1.4.3 C++ Statements and Operators
       1.4.4 Data Declarations in C++
       1.4.5 Comments in C++
       1.4.6 Input/Output in C++
       1.4.7 Functions in C++
       1.4.8 Parameter Passing in C++
       1.4..9 Function Name Overloading in C++
       1.4.10 Inline Functions
       1.4.11Dynamic Memory Allocation in C++
       1.4.12 Exceptions
1.5 Algorithm Speci fication
        1.5.1 Introduction
        1.5.2 Recursive Algorithms
1.6 The Standard Template Library
1.7 Performance Analysis And Measurement
         1.7.1 Performance Analysis
         1.7.2 Performance Measurement
         1.7.3 Generating Test Data
1.8 References And Selected Readings
CHAPTER 2 ARRAYS
2.1 Abstract Data Types and the C++ Class
          2.1.1 An Introduction to the C++ Class
          2.1.2 Data Abstraction and Encapsulation in C++
          2.1.3 Declaring Class Objects and Invoking Member Functions
          2.1.4 Special Class Operations
          2.1.5 Miscellaneous Topics
          2.1.6 ADTs and C++ Classes
2.2 The Array as an Abstract Data Type
2.3 The Polynomial Abstract Data Type
           2.3.1 Polynomial Representation
           2.3.2 Polynomial Addition
2.4 Sparse Matrices
            2.4.1 Introduction
            2.4.2 Sparse Matrix Representation
            2.4.3 Transposing a Matrix
            2.4.4 Matrix Multiplication
2.5 Representation of Arrays
2.6 The String Abstract Data Type
            2.6.1 String Pattern Matching: A Simple Algorithm
            2.6.2 String Pattern Matching: The KMP Algorithm
2.7 References and Selected Readings
2.8 Additional Exercises
CHAPTER 3 STACKS AND QUEUES
3.1 Templates in C++
            3.1.1 Template Functions
            3.1.2 Using Templates to Represent Container Classes
   3.2 The Stack Abstract Data Type
   3.3 The Queue Abstract Data Type
   3.4 Subtyping and Inheritance in C++
   3.5 A Mazing Problem
   3.6 Evaluation of Expressions
            3.6.1 Expressions
            3.6.2 Postfix Notation
            3.6.3 Infix to Postfix
3.7 Additional Exercises
CHAPTER 4 LINKED LISTS
4.1 Singly Linked Lists and Chains
4.2 Representing Chains in C++
          4.2.1 Defining a Node in C++
          4.2.2 Designing a Chain Class in C++
          4.2.3 Pointer Manipulation in C++
          4.2.4 Chain Manipulation Operations
4.3 The Template Class Chain
          4.3.1 Implementing Chains with Templates
          4.3.2 Chain Iterators
          4.3.3 Chain Operations
          4.3.4 Reusing a Class
4.4 Circular Lists
4.5 Available Space Lists
4.6 Linked Stacks and Queues
4.7 Polynomials
          4.7.1 Polynomial Representation
          4.7.2 Adding Polynomials
          4.7.3 Circular List Representation of Polynomials
4.8 Equivalence Classes
4.9 Sparse Matrices
         4.9.1 Sparse Matrix Representation
         4.9.2 Sparse Matrix Input
         4.9.3 Deleting a Sparse Matrix
4.10 Doubly Linked Lists
4.11 Generalized Lists
         4.11.1 Representation of Generalized Lists
         4.11.2 Recursive Algorithms for Lists
         4.11.3 Reference Counts, Shared and Recursive Lists
CHAPTER 5 TREES
5.1 Introduction
          5.1.1 Terminology
          5.1.2 Representation of Trees
5.2 Binary Trees
          5.2.1 The Abstract Data Type
          5.2.2 Properties of Binary Trees
          5.2.3 Binary Tree Representations
5.3 Binary Tree Traversal and Tree Iterators
          5.3.1 Introduction
          5.3.2 Inorder Traversal
          5.3.3 Preorder Traversal
          5.3.4 Postorder Traversal
          5.3.5 Iterative Inorder Traversal
          5.3.6 Level-Order Traversal
          5.3.7 Traversal Without a Stack
5.4 Additional Binary Tree Operations
          5.4.1Copying Binary Trees
          5.4.2 Testing Equality
          5.4.3 The Satisfiability Problem
5.5 Threaded Binary Trees
          5.5.1 Threads
          5.5.2 Inorder Traversal of a Threaded Binary Tree
          5.5.3 Inserting a Node into a Threaded Binary Tree
5.6 Heaps
          5.6.1 Priority Queues
          5.6.2 Definition of a Max Heap
          5.6.3 Insertion into a Max Heap
          5.6.4 Deletion from a Max Heap
          5.7 Binary Search Trees
5.7.1 Definition
          5.7.2 Searching a Binary Search Tree
          5.7.3 Insertion into a Binary Search Tree
          5.7.4 Deletion from a Binary Search Tree
          5.7.5 Joining and Splitting Binary Search Trees
          5.7.6 Height of a Binary Search Tree
5.8 Selection Trees
          5.8.1 Introduction
          5.8.2 Winner Trees
          5.8.3 Loser Trees
5.9 Forests
          5.9.1 Transforming a Forest into a Binary Tree
          5.9.2 Forest Traversals
5.10 Representation of Disjoint Sets
          5.10.1 Introduction
          5.10.2 Union and Find Operations
          5.10.3 Application to Equivalence Classes
5.11 Counting Binary Trees
          5.11.1 Distinct Binary Trees
          5.11.2 Stack Permutations
          5.11.3 Matrix Multiplication
          5.1l.4 Number of Distinct Binary Trees
5.12 References and Selected Readings
CHAPTER 6 GRAPHS
6.1 The Graph Abstract Data Type
          6.1.1 Introduction
          6.1.2 Definitions
          6.1.3 Graph Representations
6.2 Elementary Graph Operations
          6.2.1 Depth First Search
          6.2.2 Breadth First Search
          6.2.3 Connected Components
          6.2.4 Spanning Trees
          6.2.5 Biconnected Components
6.3 Minimum Cost Spanning Trees
          6.3.1 Kruska1 s Algorithm
          6.3.2 Prim s Algorithm
          6.3.3 SoUin s Algorithm
6.4 Shortest Paths and Transitive Closure
          6.4.1 Single Source/All Destination: Nonnegative Edge Costs
          6.4.2 Single Source/All Destination: General Weights
          6.4.3 All-Pairs Shortest Paths
          6.4.4 Transitive Closure
6.5 Activity Networks
          6.5.1 Activity on Vertex (AOV) Networks
          6.5.2 Activity on Edge (AOE) Networks
6.6 References and Selected Readings
6.7 Additional Exercises
CHAPTER 7 SORTING
7.1 Motivation
7.2 Insertion Sort
7.3 Quick Sort
7.4 How Fast Can We Sort?
7.5 Merge Sort
           7.5.1 Merging
           7.5.2 Iterative Merge Sort
           7.5.3 Recursive Merge Sort
7.6 Heap Sort
7.7 Sorti ng on Several Keys
7.8 List and Table Sorts
7.9 Summary oflnternal Sorting
7.10 External Sorting
            7.10.1 Introduction
            7.10.2 k-way Merging
            7.10.3 Butter Handling for Parallel Operation
            7.10.4 Run Generation
            7.10.5 Optimal Merging of Runs
7. 11 References and Selected Readings
CHAPTER 8 HASHING
8.1 Introduction
8.2 Static Hashing
             8.2.1 Hash Tables
             8.2.2 Hash Functions
             8.2.3 Secure Hash Functions
             8.2.4 Overflow Handling
             8.2.5 Theoretical Evaluation of Overflow Techniques
8.3 Dynamic Hashing
             8.3.1 Motivation for Dynamic Hashing
             8.3.2 Dynamic Hashing using Directories
             8.3.3 Directoryless Dynamic Hashing
8.4 Bloom Filters
             8.4.1 An Application -- Differential Files
             8.4.2 Bloom Filter Design
8.5 References and selected Readings
CHAPTER 9 PRIORITY QUEUES
9.1 Single- and Double-Ended Priority Queues
9.2 Leftist Trees
             9.2.1 Height-Biased Leftist Trees
             9.2.2 Weight-Biased Leftist Trees
9.3 Binomial Heaps
             9.3.1 Cost Amortization
             9.3.2 Definition of Binomial Heaps
             9.3.3 Insertion into a Binomial Heap
             9.3.4 Melding Two Binomial Heaps
             9.3.5 Deletion of Min Element
             9.3.6 Analysis
9.4 Fibonacci Heaps
             9.4.1 Definition
             9.4.2 Deletion from an F-heap
             9.4.3 Decrease Key
             9.4.4 Cascading Cut
             9.4.5 Analysis
             9.4.6 Application to The Shortest Paths Problem
9.5 Pairing Heaps
             9.5.1 Definition
             9.5.2 Meld and Insert
             9.5.3 Decrease Key
             9.5.4 Delete Min
             9.5.5 Arbitrary Delete
             9.5.6 Implementation Considerations
             9.5.7 Complexity
9.6 Symmetric Min-Max Heaps
             9.6.1 Definition and Properties
             9.6.2 SMMH Representation
             9.6.3 Inserting into an SMMH
             9.6.4 Deleting from an SMMH
9.7 Interval Heaps
             9.7.1 Definition and Properties
             9.7.2 Inserting into an Interval Heap
             9.7.3 Deleting the Min Element
             9.7.4 Initializing an Interval Heap
             9.7.5 Complexity of Interval Heap Operations
             9.7.6 The Complemenary Range Search Problem
9.8 References and Selected Readings
CHAPTER 10 EFFICIENT BINARY SEARCH TREES
10.1 Optimal Binary Search Trees
10.2 AVL Trees
10.3 Red-Black Trees
             10.3.1 Definition
             10.3.2 Representastion of a Red-Black Tree
             10.3.3 Searching a Red-Black Tree
             10.3.4 Inserting into a Red-Black Tree
             10.3.5 Deletion from a Red-Black Tree
             10.3.6 Joining Red-Black Trees
             10.3.7 Splitting a Red-Black Tree
10.4 Splay Trees
             10.4.1 Bottom-Up Splay Trees
             10.4.2 Top-Down Splay Trees
10.5 References and Selected Readings
CHAPTER 11 MULTIWAY SEARCH TREES
11.1 m-way Search Trees
             11.1.1 Definition and Properties
             11.1.2 Searching an m-way Search Tree
11.2 B- Trees
             11.2.1 Definition and Properties
             11.2.2 Number of Elements in a B- Tree
             11.2.3 Insertion into a B-tree
             11.2.4 Deletion from a B-tree
11.3 B+-Trees
             11.3.1 Definition
             11.3.2 Searching a B+-Tree
             11.3.3 Insertion into a B+-Tree
             11.3.4 Deletion from a B+-Tree
             11.4 References and Selected Readings
CHAPTER 12 DIGITAL SEARCH STRUCTURES
12.1 Digital Search Trees
             12.1.1 Defintiion
             12.1.2 Search, Insert and Delete
12.2 Binary Tries and Patricia
             12.2.1 Binary Tries
             12.2.2 Compressed Binary Tries
             12.2.3 Patricia
12.3 Multiway Tries
             12.3.1 Definition
             12.3.2 Searching a Trie
             12.3.3 Sampling Strategies
             12.3.4 Insertion into a Trie
             12.3.5 Deletion from a Trie
             12.3.6 Keys with Different Length
             12.3.7 Height of a Trie
             12.3.8 Space Required and Alternative Node Structures
             12.3.9 Prefix Search and Applications
             12.3.10 Compressed Tries
             12.3.11 Compressed Tries with Skip Fields
             12.3.12 Compressed Tries with Labeled Edges
             12.3.13 Space Required by a Compressed Trie
12.4 Suffix. Trees
             12.4.1 Have You Seen this String?
             12.4.2 The Suffix. Tree Data Structure
             12.4.3 Let's Find That Substring (Searching a Suffix Tree)
             12.4.4 Other Nifty Things You Can Do with a Suffix Tree
12.5 Tries and Internet Packet Forwarding
             12.5.1 IP Routing
             12.5.2 I-Bit Tries
             12.5.3 Fixed-Stride Tries
             12.5.4 Variable-Stride Tries
12.6 References and Selected Readings
INDEX