Binary Search Trees: Preview

 The goal for this exercise is to familiarize yourself with what Binary Search Trees are. 

 

I would suggest skimming this document entirely, then going back & looking at the examples in detail.  Once you've done all that, you should be able to do the exercises at the end.

As a note, your instructor likes to abbreviate Binary Search Tree as BST, although this practice may not be commonplace.

            I'd suggest looking online for whatever materials you need to get a handle on what a BST is. Since we'll go over the details in class, you want to mainly get the 'gist' of what a BST is, rather than getting bogged down in all the details.  In particular, you aren't expected to be able to write compiling code for these quite yet, but you should be able to draw out (on paper, by hand) a BST, and then demonstrate how to find a particular value within the tree, and how to add a new value.  Removing stuff from the tree can be complicated – we'll go over that later, so skip that for now.

            Wikipedia has a good entry that should help orient you to the concept (http://en.wikipedia.org/wiki/Binary_search_tree).    In particular, you should focus on the picture at the top-right of the article:

(Image Source: http://en.wikipedia.org/wiki/Image:Binary_search_tree.svg, This image is in the public domain)

            Using the above picture as a guide, you should first examine the BST properties listed at the top of the Wikipedia article, and figure out (intuitively) how you'd find various nodes (using the article, and other online resources). 

            You may want to look for online visualizations / visualizers that demonstrate how the BST works.  For example, the following visualization will let you add, find, and remove stuff from the tree.  Since you're expected to figure out the search & add logic, I'd focus on those.   

 

https://www.cs.usfca.edu/~galles/visualization/BST.html

 If you examine the Wikipedia article in detail, you'll notice that it has code (in a somewhat random assortment of languages J  ) that demonstrate searching, adding, and removing values.  Notice that the search code in Wikipedia is recursive, while the searching demonstrated by the applets would be better implemented iteratively (i.e., using a loop)

Consider how your searching algorithm should be set up if duplicate values are allowed (such as in the above tree), as opposed to a tree in which no duplicate values are present: in which case would a recursive solution make sense, and in which case an iterative solution would be better.  If you use the Wikipedia article as a guide, consider whether the recursive "Find" is really necessary when there are no duplicate values – see if you can figure out how to search the tree iteratively if there are no duplicate values in the tree.

             Next, look at the Insertion/Add routine, and figure out how that works.  Since the "Insert" logic basically searches the tree to figure out where the node SHOULD go, and then adds it there, this shouldn't be too hard.

Exercises:

(Do these before class, and show up in class ready to go over these)

  1. Using the picture shown above, trace out how you'd go about finding the values 3, 10, 13, and 23 (which is not present).  You should be able to trace the path (through the nodes) to each node, explaining at each node where you go next and (more importantly, WHY). 
  2. Using the picture shown above, trace out how you'd go about adding  the values 0, 2, 13.5, and 200.  You should be able to trace the path (through the nodes) to each node, explaining at each node where you go next and (more importantly, WHY). 

What you need to do for this exercise: 

  1. There are no concrete deliverables for this exercise.  You should spend some time making sure that you’re clear on these concepts, however, since you’ll be using them to produce concrete results in future exercises.