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 CPP Lab

BST Memory

  • Watch this video on memory management in BSTs:

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 CPP Lab

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.