(Ebook PDF)A Textbook of Data Structures and Algorithms Volume 2 Mastering Nonlinear Data Structures 1st edition by Vijayalakshmi Pai ISBN 1786308916 9781786308917 full chapters

Preface
Acknowledgments

Chapter 8: Trees and Binary Trees

• Introduction
• Trees: definition and basic terminologies
  • Definition of trees
  • Basic terminologies of trees
• Representation of trees
• Binary trees: basic terminologies and types
  • Basic terminologies
  • Types of binary trees
• Representation of binary trees
  • Array representation of binary trees
  • Linked representation of binary trees
• Binary tree traversals
  • Inorder traversal
  • Postorder traversal
  • Preorder traversal
• Threaded binary trees
  • Linked representation of a threaded binary tree
  • Growing threaded binary trees
• Applications
  • Expression trees
  • Traversals of an expression tree
  • Conversion of infix expression to postfix expression
  • Segment trees
• Illustrative problems

Chapter 9: Graphs

• Introduction
• Definitions and basic terminologies
• Representations of graphs
  • Sequential representation of graphs
  • Linked representation of graphs
• Graph traversals
  • Breadth first traversal
  • Depth first traversal
• Applications
  • Single source shortest path problem
  • Minimum cost spanning trees
• Illustrative problems

Chapter 10: Binary Search Trees and AVL Trees

• Introduction
• Binary search trees: definition and operations
  • Definition
  • Representation of a binary search tree
  • Retrieval from a binary search tree
  • Why are binary search tree retrievals more efficient than sequential list retrievals?
  • Insertion into a binary search tree
  • Deletion from a binary search tree
  • Drawbacks of a binary search tree
  • Counting binary search trees
• AVL trees: definition and operations
  • Definition
  • Retrieval from an AVL search tree
  • Insertion into an AVL search tree
  • Deletion from an AVL search tree
  • R category rotations associated with the delete operation
  • L category rotations associated with the delete operation
• Applications
  • Representation of symbol tables in compiler design
• Illustrative problems

Chapter 11: B Trees and Tries

• Introduction
• m-way search trees: definition and operations
  • Definition
  • Node structure and representation
  • Searching an m-way search tree
  • Inserting into an m-way search tree
  • Deleting from an m-way search tree
  • Drawbacks of m-way search trees
• B trees: definition and operations
  • Definition
  • Searching a B tree of order m
  • Inserting into a B tree of order m
  • Deletion from a B tree of order m
  • Height of a B tree of order m
• Tries: definition and operations
  • Definition and representation
  • Searching a trie
  • Insertion into a trie
  • Deletion from a trie
  • Some remarks on tries
• Applications
  • File indexing
  • Spell checker
• Illustrative problems

Chapter 12: Red-Black Trees and Splay Trees

• Red-black trees
  • Introduction to red-black trees
  • Definition
  • Representation of a red-black tree
  • Searching a red-black tree
  • Inserting into a red-black tree
  • Deleting from a red-black tree
  • Time complexity of search, insert and delete operations on a red-black tree
• Splay trees
  • Introduction to splay trees
  • Splay rotations
  • Some remarks on amortized analysis of splay trees
• Applications
• Illustrative problems

References
Index
Summaries of other volumes