Description
Book SynopsisData structures and algorithms is a fundamental course in Computer Science, which enables learners across any discipline to develop the much-needed foundation of efficient programming, leading to better problem solving in their respective disciplines.
A Textbook of Data Structures and Algorithms is a textbook that can be used as course material in classrooms, or as self-learning material. The book targets novice learners aspiring to acquire advanced knowledge of the topic. Therefore, the content of the book has been pragmatically structured across three volumes and kept comprehensive enough to help them in their progression from novice to expert.
With this in mind, the book details concepts, techniques and applications pertaining to data structures and algorithms, independent of any programming language. It includes 181 illustrative problems and 276 review questions to reinforce a theoretical understanding and presents a suggestive list of 108 programming assignments to aid in the implementation of the methods covered.
Table of ContentsPreface ix
Acknowledgments xv
Chapter 8 Trees and Binary Trees 1
8.1 Introduction 1
8.2 Trees: definition and basic terminologies 1
8.2.1 Definition of trees 1
8.2.2 Basic terminologies of trees 2
8.3 Representation of trees 3
8.4 Binary trees: basic terminologies and types 6
8.4.1 Basic terminologies 6
8.4.2 Types of binary trees 7
8.5 Representation of binary trees 8
8.5.1 Array representation of binary trees 8
8.5.2 Linked representation of binary trees 10
8.6 Binary tree traversals 11
8.6.1 Inorder traversal 12
8.6.2 Postorder traversal 16
8.6.3 Preorder traversal 19
8.7 Threaded binary trees 22
8.7.1 Linked representation of a threaded binary tree 24
8.7.2 Growing threaded binary trees 24
8.8 Applications 25
8.8.1 Expression trees 26
8.8.2 Traversals of an expression tree 27
8.8.3 Conversion of infix expression to postfix expression 27
8.8.4 Segment trees 31
8.9 Illustrative problems 42
Chapter 9 Graphs 61
9.1 Introduction 61
9.2 Definitions and basic terminologies 63
9.3 Representations of graphs 75
9.3.1 Sequential representation of graphs 76
9.3.2 Linked representation of graphs 80
9.4 Graph traversals 81
9.4.1 Breadth first traversal 81
9.4.2 Depth first traversal 83
9.5 Applications 87
9.5.1 Single source shortest path problem 87
9.5.2 Minimum cost spanning trees 90
9.6 Illustrative problems 97
Chapter 10 Binary Search Trees and AVL Trees 115
10.1 Introduction 115
10.2 Binary search trees: definition and operations 115
10.2.1 Definition 115
10.2.2 Representation of a binary search tree 116
10.2.3 Retrieval from a binary search tree 117
10.2.4 Why are binary search tree retrievals more efficient than sequential list retrievals? 118
10.2.5 Insertion into a binary search tree 120
10.2.6 Deletion from a binary search tree 122
10.2.7 Drawbacks of a binary search tree 125
10.2.8 Counting binary search trees 128
10.3 AVL trees: definition and operations 130
10.3.1 Definition 131
10.3.2 Retrieval from an AVL search tree 132
10.3.3 Insertion into an AVL search tree 133
10.3.4 Deletion from an AVL search tree 141
10.3.5 R category rotations associated with the delete operation 146
10.3.6 L category rotations associated with the delete operation 150
10.4 Applications 151
10.4.1 Representation of symbol tables in compiler design 151
10.5 Illustrative problems 154
Chapter 11 B Trees and Tries 175
11.1 Introduction 175
11.2 m-way search trees: definition and operations 176
11.2.1 Definition 176
11.2.2 Node structure and representation 176
11.2.3 Searching an m-way search tree 178
11.2.4 Inserting into an m-way search tree 178
11.2.5 Deleting from an m-way search tree 179
11.2.6 Drawbacks of m-way search trees 184
11.3 B trees: definition and operations 184
11.3.1 Definition 184
11.3.2 Searching a B tree of order m 186
11.3.3 Inserting into a B tree of order m 186
11.3.4 Deletion from a B tree of order m 190
11.3.5 Height of a B tree of order m 194
11.4 Tries: definition and operations 195
11.4.1 Definition and representation 195
11.4.2 Searching a trie 197
11.4.3 Insertion into a trie 197
11.4.4 Deletion from a trie 198
11.4.5 Some remarks on tries 200
11.5 Applications 200
11.5.1 File indexing 201
11.5.2 Spell checker 203
11.6 Illustrative problems 204
Chapter 12 Red-Black Trees and Splay Trees 215
12.1 Red-black trees 215
12.1.1 Introduction to red-black trees 215
12.1.2 Definition 216
12.1.3 Representation of a red-black tree 219
12.1.4 Searching a red-black tree 220
12.1.5 Inserting into a red-black tree 220
12.1.6 Deleting from a red-black tree 228
12.1.7 Time complexity of search, insert and delete operations on a red-black tree 236
12.2 Splay trees 236
12.2.1 Introduction to splay trees 236
12.2.2 Splay rotations 237
12.2.3 Some remarks on amortized analysis of splay trees 242
12.3 Applications 244
12.4 Illustrative problems 245
References 261
Index 263
Summaries of other volumes 265
