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

Class Schedule

Monday

• Rotations & Splay Trees

Tuesday

• Balancing Intro
• AVL Trees

Wednesday

• BTrees

Thursday

• Red Black Trees

Topics

Rotations & Splay Trees

• Read Ch25.1 - 25.2

• Watch this video on rotations and splaying:

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

• Do the BST Rotation WS

Balancing Basics

• Watch this video about basic balancing techniques in BSTs:

• Do the BST Balancing CPPLab

AVL Trees

• Read ch 25.8. Don't stress about about the detailed 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 on assignment 4. Use this week to get a good start on it.