(2,4) trees, red-black trees, insertion, deletion, rotations, comparison of dictionary implementations.
Introduction to the Tree abstract data type.
Basic ideas about balanced trees
Screencast Suthers 11 min
Conceptual overview of balanced tree operations
Screencast Suthers 14 min
Red-Black trees as 2-4 and BSTs
Screencast Suthers 15 min
Red-Black tree insertion and deletion
Screencast Suthers 21 min
Properties, rotations, insertion, and deletion
Textbook 31 pages
Top-down 2-3-4 trees, red-black trees, other algorithms
Textbook 14 pages
Balanced trees and operations on them
Notes
Learn about balanced trees (at home).
Homework
Provide four implementations of the Dynamic Set ADT and compare their performance.
Programming