Version: 0.6.8

Trees

This module focuses on trees, probably the most ubiquitous structure in computer science. We will look at the general concept of tree, and at several data structures around this theme.

Contents

• 1. Trees
  • 1.1. What Is a Tree?
  • 1.2. Tree Implementations
  • 1.3. Tree Traversals
• 2. Binary Search Trees
  • 2.1. Ordered Sets
  • 2.2. Ordered Set Using a Binary Search Tree
• 3. Binary Heaps
  • 3.1. The Priority Queue ADT
  • 3.2. What Is a Binary Heap?
  • 3.3. Binary Heap Using an Array
  • 3.4. Heapification
  • 3.5. Heap Sort
• 4. AVL Trees
  • 4.1. Why BST Can Be Inefficient?
  • 4.2. AVL Trees
• 5. B-Trees
  • 5.1. External Storages
  • 5.2. The Disk-access Model (DAM)
  • 5.3. B-Trees
• 6. Prefix and Suffix Trees
  • 6.1. Prefix Trees
  • 6.2. Suffix Trees