Background

Binary search trees are fundamental to computer science. Not only do they demonstrate a number of interesting algorithms, they are also inherently useful (as abstract tools) for building more sophisticated structures like sets and maps. Today we will look at two implementations of BSTs and visualize how these data structures work. We will also make connections to previous material on programming paradigms.

Download:   Lab10-Worksheet.txt

Objectives

• Summarize the role of algorithms, data structures, and languages in programming.

• Explain how data are represented, stored, and manipulated by computer hardware.

NOTE: The goal of today's lab is to understand how the algorithms and data structures actually work. Don't cheat yourself by just "getting the lab done". Make sure you are able to describe to another person what is going on in the code (i.e., practice teaching the material).

Part 1: Imperative, Recursive Version

Download:   tree1.py

The tree1.py module is an implementation of binary search trees that doesn't use a class to design the data structure.

1. If you haven't done so already, you may want to review the algorithms in Section 8.4 (pages 382--387) of the textbook.

2. Open tree1.py in IDLE and run the program. Scroll down to the main function, and figure out where each line of output came from.

3. Copy/paste the contents of tree1.py into Online Python Tutor. You may wish to change the "draw references using arrows" option to "use text labels for references" for this example.

4. Step through the visualization and answer the corresponding questions in your lab worksheet.

Part 2: Object-Oriented, Non-Recursive

Download:   tree2.py

The tree2.py module is based on binary_tree.py from the python-algorithms library by Laurent Luce.

5. Skim through Luce's blog post on BSTs to get a general understanding of how the code works. We will discuss the syntax of Python classes during the lab.

6. Open tree2.py in IDLE and run the program. Scroll down to the bottom, and figure out where each line of output came from.

7. Copy/paste the contents of tree2.py into Online Python Tutor. You may wish to change the "draw references using arrows" option to "use text labels for references" for this example.

8. Step through the visualization and answer the corresponding questions in your lab worksheet.

Submission Instructions

• Submit your completed worksheet via canvas.jmu.edu by 11:59 PM today.