Session 11: Data Structures II — Trees, Heaps, Graphs

Overview

Tree, heap and graph structures, with each one presented as a representation together with the invariant that makes its operations correct.

Lecturer

Georges Khater (CSE + Mathematics)

Session Information

Core Concepts

  • Binary trees: representation, height, traversals (pre/in/post-order), and traversals as folds
  • Binary search trees: the BST invariant stated as a proposition about all descendants; insert, search, and delete
  • Balance: why unbalanced BSTs degrade; AVL and red-black trees at the level of which invariant they maintain
  • Heaps: the heap property as an invariant; sift-up and sift-down; heapsort; priority queues
  • Graphs: adjacency lists vs matrices; BFS and DFS
  • Hash tables
  • Every data structure here as a representation plus an invariant

Slides

Session 11 Slides: Download PDF

Readings

Exercises & Extra Steps

  • Practice (not collected): write the BST invariant as a formal predicate over trees and prove in-order traversal yields a sorted list
  • Practice (not collected): exhibit a tree satisfying “node ≥ children” at every node that is not a BST
  • Practice (not collected): prove a binary heap of n elements has height ⌊log₂ n⌋
  • Problem Set 3 due today — hand it in on paper at the start of the session

Questions? Reach out on the course WhatsApp!