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

Class Schedule

Monday

  • Holiday

Tuesday

  • Rotations
  • Balancing

Wednesday

  • AVL Trees

Thursday

  • BTrees

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 CPP Lab

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.

Assignment 4

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