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. Most of the well-known text books/monographs on this subject have discussed the concepts in relation to a programming language – beginning with Pascal and spanning a spectrum of them such as C, C++, C#, Java, Python and so on, essentially calling for ample knowledge of the language, before one proceeds to try and understand the data structure. There does remain a justification in this. The implementation of data structures in the specific programming language need to be demonstrated or the algorithms pertaining to the data structures concerned need a convenient medium of presentation and when this is the case, why not a programming language? Again, while some authors have insisted on using their books for an advanced level course, there are some who insist on a working knowledge of the specific programming language as a prerequisite to using the book. However, in the case of a core course, as it is in most academic programs, it is not uncommon for a novice or a sophomore to be bewildered by the “miles of code” that demonstrate or explain a data structure, rendering the subject difficult to comprehend.
Author(s): G.A. Vijayalakshmi Pai
Publisher: Wiley
Year: 2022
Language: English
Pages: 304
Cover
Title Page
Copyright Page
Contents
Preface
Acknowledgments
Chapter 8. Trees and Binary Trees
8.1. Introduction
8.2. Trees: definition and basic terminologies
8.2.1. Definition of trees
8.2.2. Basic terminologies of trees
8.3. Representation of trees
8.4. Binary trees: basic terminologies and types
8.4.1. Basic terminologies
8.4.2. Types of binary trees
8.5. Representation of binary trees
8.5.1. Array representation of binary trees
8.5.2. Linked representation of binary trees
8.6. Binary tree traversals
8.6.1. Inorder traversal
8.6.2. Postorder traversal
8.6.3. Preorder traversal
8.7. Threaded binary trees
8.7.1. Linked representation of a threaded binary tree
8.7.2. Growing threaded binary trees
8.8. Applications
8.8.1. Expression trees
8.8.2. Traversals of an expression tree
8.8.3. Conversion of infix expression to postfix expression
8.8.4. Segment trees
8.9. Illustrative problems
Chapter 9. Graphs
9.1. Introduction
9.2. Definitions and basic terminologies
9.3. Representations of graphs
9.3.1. Sequential representation of graphs
9.3.2. Linked representation of graphs
9.4. Graph traversals
9.4.1. Breadth first traversal
9.4.2. Depth first traversal
9.5. Applications
9.5.1. Single source shortest path problem
9.5.2. Minimum cost spanning trees
9.6. Illustrative problems
Chapter 10. Binary Search Trees and AVL Trees
10.1. Introduction
10.2. Binary search trees: definition and operations
10.2.1. Definition
10.2.2. Representation of a binary search tree
10.2.3. Retrieval from a binary search tree
10.2.4. Why are binary search tree retrievals more efficient than sequential list retrievals?
10.2.5. Insertion into a binary search tree
10.2.6. Deletion from a binary search tree
10.2.7. Drawbacks of a binary search tree
10.2.8. Counting binary search trees
10.3. AVL trees: definition and operations
10.3.1. Definition
10.3.2. Retrieval from an AVL search tree
10.3.3. Insertion into an AVL search tree
10.3.4. Deletion from an AVL search tree
10.3.5. R category rotations associated with the delete operation
10.3.6. L category rotations associated with the delete operation
10.4. Applications
10.4.1. Representation of symbol tables in compiler design
10.5. Illustrative problems
Chapter 11. B Trees and Tries
11.1. Introduction
11.2. m-way search trees: definition and operations
11.2.1. Definition
11.2.2. Node structure and representation
11.2.3. Searching an m-way search tree
11.2.4. Inserting into an m-way search tree
11.2.5. Deleting from an m-way search tree
11.2.6. Drawbacks of m-way search trees
11.3. B trees: definition and operations
11.3.1. Definition
11.3.2. Searching a B tree of order m
11.3.3. Inserting into a B tree of order m
11.3.4. Deletion from a B tree of order m
11.3.5. Height of a B tree of order m
11.4. Tries: definition and operations
11.4.1. Definition and representation
11.4.2. Searching a trie
11.4.3. Insertion into a trie
11.4.4. Deletion from a trie
11.4.5. Some remarks on tries
11.5. Applications
11.5.1. File indexing
11.5.2. Spell checker
11.6. Illustrative problems
Chapter 12. Red-Black Trees and Splay Trees
12.1. Red-black trees
12.1.1. Introduction to red-black trees
12.1.2. Definition
12.1.3. Representation of a red-black tree
12.1.4. Searching a red-black tree
12.1.5. Inserting into a red-black tree
12.1.6. Deleting from a red-black tree
12.1.7. Time complexity of search, insert and delete operations on a red-black tree
12.2. Splay trees
12.2.1. Introduction to splay trees
12.2.2. Splay rotations
12.2.3. Some remarks on amortized analysis of splay trees
12.3. Applications
12.4. Illustrative problems
References
Index
Summaries of other volumes
EULA
