Week 6 - Binary Search Trees

Learning objectives

• Implement a Binary Search Tree
• Use a stack to iterate through a BST

Class Schedule

Monday

• Trees

Tuesday

• BST Intro

Wednesday

• BST Continued

Thursday

• Tree Iterators

Gnarly Trees

Gnarly Trees is a data structure simulator that is particularly valuable for learning how trees work. There is a copy of it in the Files area of Elearn. You will need to have java installed on your computer to us it.

This video shows how Gnarly Trees works:

Topics

Trees

Watch this video on trees:

• Do the Tree WS

BSTs

• Read Liang Ch21.0 - 21.2

• Watch this video on BST basic operations:

• Experiment with Gnarly Trees. Chose DataStructures->Dictionaries->BST.

• Do the BST WS

• Do the BST Basics CPPLab

BST Memory

• Watch this video on memory management in BSTs:

• Do the BST Memory CPPLab

BST Removal

• Read Ch21.3 and watch this video on the removal of values from BSTs:

• Experiment with Gnarly Trees. Chose DataStructures->Dictionaries->BST

• Do the BST Removal WS

• Do the BST Removal CPPLab

BST Iteration

• Watch this video on transforming lists to BSTs and iterating over them

• Do the BST IterationByHand WS

• This material is covered in Ch21.4. However, the book version makes an iterator by converting the whole tree to a vector, which is quite wasteful. So consider this optional and don't worry too much about the code sample shown in 21.4

Assignment 3

Complete assignment 3 while you work on this week's material.