Data 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 Contents:
Preface 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