Lesson 26: Self-Balancing Trees

Outline:

  1. Questions?
  2. 2-3 Tree ADT
  3. Time complexity of 2-3 tree operations
  4. Wrap-up

After class:

  1. Evaluations: complete before finals end

What’s next

Upcoming assignments:

  • Assignment 6 resubmissions are due Friday night (finalized Monday)
  • Assignment 7 resubmissions are due next Wednesday (finalized then)
  • Assignment 8 is due next Wednesday (finalized then)

What you should do now:

  • The readings (see below)
  • Resubmit Assignment 6 for free today or by Monday with a token
  • Try to complete at least Part A (and C) of Assignment 8 this weekend

Reminder: Quiz #9 on Monday

You will see these last new Quiz Learning Objectives:

  • TR 3: balanced search tree insertion/deletion
  • GS 1: breadth-first search
  • GS 2: BFS time complexity
  • GS 3: depth-first search
  • GS 4: DFS time complexity

You will also see these Quiz Learning Objectives again:

  • KF 3: loops
  • OO 2: interfaces
  • OO 3: inheritance
  • LT 1: linked lists
  • LT 4: array-based list time complexity
  • LT 5: debugging lists
  • SK 2: stack time complexity
  • QQ 2: queue time complexity
  • HT 2: hashing time complexity
  • RC 2: debugging recursion
  • TR 4: debugging trees
  • QS 1: quicksort
  • QS 2: quicksort time complexity
  • HP 2: heapsort time complexity

Let me know what extra questions you want on it!!

Reading assignment (to be completed by the next class):

Balanced search trees (from today):

Locking protocol data structure (for next time, just for fun):