Module: Balanced Trees

(2,4) trees, red-black trees, insertion, deletion, rotations, comparison of dictionary implementations.

Prerequisite Modules

Trees

Introduction to the Tree abstract data type.

Learning Outcomes

Characterize the behavior of the balanced tree algorithm, including:

Show insertion and deletion procedures for red-black trees.

Readings

Introduction to (2,4) Trees

Basic ideas about balanced trees

Screencast Suthers 11 min

Insertion and deletion in (2,4) Trees

Conceptual overview of balanced tree operations

Screencast Suthers 14 min

Red-Black Trees

Red-Black trees as 2-4 and BSTs

Screencast Suthers 15 min

Red-Black Tree Mutation

Red-Black tree insertion and deletion

Screencast Suthers 21 min

CLRS 13 - Red-Back Trees

Properties, rotations, insertion, and deletion

Textbook 31 pages

Sedgewick 15 - Balanced Trees

Top-down 2-3-4 trees, red-black trees, other algorithms

Textbook 14 pages

Notes on balanced trees

Balanced trees and operations on them

Notes

Experiential Learning

Applying your understanding of red-black trees

Learn about balanced trees (at home).

Homework

Battle of the Dynamic Sets

Provide four implementations of the Dynamic Set ADT and compare their performance.

Programming