Week 7 - Balanced Trees

Learning objectives

  • Perform rotations in a tree and correctly splay a node to root using rotations
  • Perform basic operations in an AVL tree
  • Identify how adding items to a B-Tree will affect its structure
  • Convert between equivalent Red-Black trees and B-Trees
  • Perform insertions on a Red-Black tree
Schedule your midterm NOW for next week. See the discussion board for details!

Day 1

  • Rotations
  • Balancing

Day 2

  • Balancing Intro
  • AVL Trees

Day 3

  • BTrees

Day 4

  • Red Black Trees

Topics

Rotations

  • Read Ch25.1 - 25.2

  • Watch this video on rotations:

  • Experiment with Gnarly Trees. Chose DataStructures->Dictionaries->Rotations. The Rotations simulator uses "child" notation to specify a rotation.

  • Do the BST Rotation WS

Balancing

  • Watch this video about basic balancing techniques in BSTs:

  • Do the BST Balancing CPPLab

AVL Trees

  • Read ch 25.8. Don't worry about the code, focus on what an AVL tree does to maintain balance. Then watch this video:

  • Experiment with Gnarly Trees. Chose DataStructures->Dictionaries->AVL.

  • Do AVL WS

B-Trees

  • Watch this video on B-Trees:

  • Experiment with Gnarly Trees. Chose DataStructures->Dictionaries->B-Tree.

Red Black Trees

  • Watch this video on Red-Black trees:

  • Experiment with Gnarly Trees. Chose DataStructures->Dictionaries->RB.

  • Do Red Black WS

Assignment 4

You are 100% ready to do assignment 4. Use this week to get a good start on it.