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

BSTs Continued

BST's continued

  • Read Ch21.3

  • Watch these videos:

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

  • Do the BST Memory CPPLab

  • Do the BST Removal WS

  • Do the BST Removal CPPLab

BST Iteration

  • BST Practice and Tips

Tree Iterators

  • Read Ch21.4.
The chapter iterator converts the whole tree to a vector, which is quite wasteful. In class we are studying a different internal representation using a stack. So don't worry too much about the code sample shown in 21.4

  • Watch this video on transforming lists to BSTs and iterators:

  • Do the BST IterationByHand WS

Assignment 3

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