Module: Binary Search Trees

Queries, insertion, deletion, modification, height, performance.

Learning Outcomes

Understand binary search trees

Understand the properties of binary search trees and how to apply them.

Readings

Introduction to binary search trees

Basic qualitative facts about BSTs

Screencast Suthers 15 min

BST Queries

How to perform queries on BSTs

Screencast Suthers 22 min

Modifying BSTs

How to modify binary search trees.

Screencast Suthers 21 min

Analyzing BSTs

Determine the height of binary search trees.

Screencast Suthers 5 min

CLRS 12 - Binary search trees

What is a binary search tree; querying, insertion, and deletion.

Textbook 13 pages

Chapter 8 Notes

Notes on binary search trees

Notes

Experiential Learning

More reasoning about binary search trees

Apply your learning about binary trees some more.

Homework

Battle of the Dynamic Sets

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

Programming