Week 6 - Binary Search Trees

Learning objectives

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

Class Schedule

Monday

  • Priority Queues and HeapSort

Tuesday

  • Watch this Tree Video and take prep quiz before class.
  • BSTs

Wednesday

  • Watch this BST Memory Video and take prep quiz before class.
  • BST Memory
  • BSTs Removal

Thursday

  • BST Iterators

Gnarly Trees

Gnarly Trees is a data structure simulator that is particularly valuable for learning how trees work. You can download it from the Gnarly Trees webpage or this direct link. You will need to have java installed on your computer to us it.

This video shows how Gnarly Trees works:

Topics

Priority Queues and HeapSort

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.