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

Day 1

• Rotations and Balancing

Todo:

• Do the Rotation WS and check against the key

Day 2

• AVL Trees

Todo:

• Do the AVL WS and check against the key
• Do the Ch 32 Exercises

Day 3

• B-Trees

Todo:

• Do the B-Tree WS and check against the key

Day 4

• Red-Black Trees

Todo:

• Do the Red-Black Tree WS and check against the key

Recommended Schedule

Day 1

• Rotations and Balancing
• Do the Rotation WS and check against the key

Day 2

• AVL Trees
• Do the AVL WS and check against the key
• Do the Ch 32 Exercises

Day 3

• B-Trees
• Do the B-Tree WS and check against the key

Day 4

• Red-Black Trees
• Do the Red-Black Tree WS and check against the key

Rotations and Balancing

Read Ch31.1-32.3

• Watch this video about basic balancing techniques in BSTs:
  
  

These videos review the concepts:

Balance (32.1)

Rotations (32.2-32.3)

AVL Trees

AVL trees are covered in 32.4-32.5.

This video reviews the material:

B-Trees

B-Trees are covered in 32.6-32.7.

This video reviews the material:

Red-Black Trees

Red–Black trees are covered in 32.8-32.9.

This video reviews them: