A Textbook of Data Structures and Algorithms, Volume 2: Mastering Nonlinear Data Structures

by G. A. Vijayalakshmi Pai

Overview

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.

Product Details

ISBN-13:	9781786308917
Publisher:	Wiley
Publication date:	02/14/2023
Pages:	304
Product dimensions:	6.14(w) x 9.21(h) x 0.69(d)

About the Author

G A Vijayalakshmi Pai SMIEEE is a Professor of Computer Applications at PSG College of Technology, Coimbatore, India. She has authored books and investigated research projects funded by government agencies in the disciplines of Computational Finance and Computational Intelligence.

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