Next:
4.1 Introduction
Up:
DSA
Previous:
4.6.5 Amortized Analysis of Splaying
4. Binary Trees
4.1 Introduction
4.1.1 Definitions
4.1.2 Preorder, Inorder, Postorder
4.1.3 The Tree ADT
4.1.4 Data Structures for Tree Representation
4.2 Binary Trees
4.3 An Application of Binary Trees: Huffman Code Construction
4.3.1 Implementation
4.3.2 Sketch of Huffman Tree Construction
4.4 Binary Search Tree
4.4.1 Average Case Analysis of BST Operations
4.5 Splay Trees
4.5.1 Search, Insert, Delete in Bottom-up Splaying
4.6 Amortized Algorithm Analysis
4.6.1 Example of Sorting
4.6.2 Example of Tree Traversal (Inorder)
4.6.3 Credit Balance
4.6.4 Example of Incrementing Binary Integers
4.6.5 Amortized Analysis of Splaying
4.7 To Probe Further
4.8 Problems
4.8.1 General Trees
4.8.2 Binary Search Trees
4.8.3 Splay Trees
4.9 Programming Assignments
4.9.1 Huffman Coding
4.9.2 Comparison of Hash Tables and Binary Search Trees
4.9.3 Comparison of Skip Lists and Splay Trees
eEL,CSA_Dept,IISc,Bangalore
