Week 6 - Binary Search Trees

Learning objectives

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

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:

Day 1

Trees

Watch this video on trees:

  • Do the Tree WS

Day 2

BSTs

  • Read Liang Ch21.0 - 21.2 to learn about the basics of Binary Search Trees

  • Watch this video on BST basic operations:

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

  • Do the BST WS

  • Do the BST Basics CPPLab

Day 3

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

Day 4

Iterating over BSTs

  • 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.