Week 8 - Balanced Trees

Learning objectives

  • Convert between equivalent Red-Black trees and B-Trees
  • Perform insertions on a Red-Black tree
  • Describe how a Treap uses the logic of a heap to balance a sorted tree
  • Perform insertions on a Treap or Skip List

Class Schedule

Monday

  • Red–Black Trees

Tuesday

  • Treaps and Skip Lists

Wednesday

  • Midterm Review

Thursday

Pen-and-paper midterm in class

Topics

Red–Black Trees

  • Watch this video on Red–Black trees:

  • Experiment with Gnarly Trees. Chose DataStructures→Dictionaries→RB.

  • Do Red–Black WS

Probabilistically balanced structures - Treaps and Skip Lists

  • There are some clever ways we can use randomness to be pretty sure that we will get logn performance from a structure that provides similar functionality to a BST without keeping track of heights or colors. Watch this video:

Review

Midterm study guide available in Class Files link