Session Details

Week 4, Session 12 — Fri Jan 10

Preparation

Due

  1. Written Assignment 4 (moved to Monday, 11:59 pm, no late days may be gained/used)

Topics

  1. Rank and efficiently finding kth element of a BST
  2. Need for trees that are height-balanced but not completely balanced

Outline

  1. Finding kth element of a BST, need for rank
  2. Definition of Height-balanced tree
  3. Induction example: Fibonacci
  4. Completely-balanced trees: nice idea, but ...
  5. Height-balanced trees, maximum height

Resources

  1. Slides

HW Assigned

  1. See Preparation, Due, and Major Programs columns on the main schedule page