CS200 Bridge--Binary Search Trees

--- tags: CS200Prep, 2021 title: CS200 Bridge--Binary Search Trees --- # CS20 Bridge Assignment: Binary Search Trees *[Work in Pyret, putting your work in a file called `bsts.arr`]* In class, we saw ancestor trees, in which we linked horses to their parents. The datatype we had for this was: ``` data HorseAncestry: | horse(name :: String, year :: Number, country :: String, mom-horse :: HorseAncestry, dad-horse :: HorseAncestry ) | no-horse-info end ``` Tree-shaped data (data in which multiple "next" pieces of data branch off a single datum) arises in various contexts in CS. Think of the layers of menus of options you select through when trying to call customer service: first you indicate the general nature of your call, then you get a more refined set of questions, and so on. Each question is a data point that branches off to other questions, each of which has their own set of questions, and so on. Ancestor trees and phone-call menus are examples where our data is inherently tree-shaped: the relationships we want to capture branch off between data points. But in CS we also use trees in a more artificial manner: we impose a branching structure on data to allow us to work with that data more efficiently. This assignment has you work with *binary search trees* (henceforth abbreviated as BST), a way of organizing a collection of data with order to help us find data items faster than searching in lists. :::info See **[here](https://brown.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=f1ebe4e2-178c-4632-85b2-b0ac01152459)** for the summer 2022 office hours recording on this assignment. *Note: as with all of the office hours recordings, you will get a lot more out of watching this recording ***after*** you've attempted the problems in this assignment.* ::: ## BSTs (on Numbers) Imagine that you had a set of numbers such as ```8, 5, 7, 1, 3, 12, 6, 10, 2, 4``` and you wanted to organize it in a way that showed the ordering relationship among the numbers. You could make a sorted list, but as we have seen, checking whether a specific number is in a list can take time linear in the size of the list. A binary search tree (BST) is a binary tree (meaning a tree with at most two branches from each node/point) in which every node has the following property: ``` Every element in the left subtree is smaller than the element at the root, every element in the right subtree is larger than the element at the root, and both the left and right subtrees are BSTs. ``` (this statement assumes no duplicates, but that is okay since we are modeling sets. If you want duplicates, change less-than to less-than-or-equal in the definition). Here is one example BST on our sample set: ``` 10 / \ 4 12 / \ 2 7 / \ / \ 1 3 6 8 / 5 ``` :::info **Practice (not for turn in):** Draw two more BSTs on the same collection of numbers. Start with a different number at the top (called the *root*) and see what you come up with. Can you make distinctly different shapes? ::: :::info **Practice (not for turn in):** Which of the following are BSTs on the numbers from 1 through 5? ``` 4 3 4 3 / \ / \ / \ / \ 5 3 2 5 2 5 1 5 / \ / / / \ / 1 2 1 4 1 2 4 \ 3 ``` ::: ## A Datatype for BSTs Generalizing from our ancestor tree, here's a general datatype for BSTs on numbers: ``` data BST: | leaf | node(val :: Any, left :: BST, right :: BST) end ``` This has the same shape as the `AncTree` definition, but it is not specific to relationships on people. Instead, it allows any kind of data (through the type `Any`). It also uses the term `leaf`, instead of `unknown`, for the empty tree.  ## Searching in BSTs Imagine you were given a BST representing a set of numbers, and were asked whether a specific number is in the set. How would you proceed? - **If the tree is a leaf**, return false - **If the tree is not a leaf** - **if the number you're seeking is at the root**, return true - **If the number you are seeking is smaller than the number at the root**, search in the left subtree - **If the number you are seeking is larger than the number at the root**, search in the right subtree :::info **Practice (not for turn in):** Using the same tree we provided, work through a couple of example searches, some of numbers in the tree and some not in the tree. ::: :::warning **Exercise (to turn in):** When you understand the algorithm, implement the function. Don't forget to include test cases. ``` fun has-elt(num :: number, t :: BST) -> Boolean ``` ::: **Note:** even though the definition of BST is more general than just numbers, you can assume we are working with trees of numbers when writing your code. ## Creating BSTs How do we build-up a BST, however? For lists, we know how to use `link` to add an element. How do we add an element to a BST? Assume you are given a BST and a number. You add an element to the BST by looking through the tree for the leaf where the number should be, then putting the number in that spot. For example, assume you wanted to insert the number 4 into the following tree: ``` 8 / \ 5 9 / \ 3 7 ``` We'd start at the root, and ask whether 4 is less than or greater than 8. Less than, so we should insert 4 on the left (so that we maintain the requirement on a BST). Now we compare 4 to 5. Less than, so we insert on the left. Now compare 4 to 3. Larger than, so we insert on the right. But the right is a leaf, so that is where we put the 4. Here's the resulting BST: ``` 8 / \ 5 9 / \ 3 7 \ 4 ``` Notice that in this algorithm, new elements are always inserted at the leaves, not in the middle of the tree. This disrupts the tree as little as possible, while still maintaining the BST requirement. :::info **Practice (not for turn in):** By hand, follow the above algorithm to create BSTs for each of the following setups on the same numbers: - start with a leaf, then add `3, 1, 2, 4` in that order - start with a leaf, then add `4, 3, 2, 1` in that order - start with a leaf, then add `4, 2, 1, 3` in that order ::: :::warning **Exercise (to turn in):** Implement `add-elt` (our description explained the algorithm, which inserts at leaves). Don't forget to write test cases (and writing them first could *really* help you here, especially in the leaf case). ``` fun add-elt(num :: number, to :: BST) -> BST ``` Also, follow the template code skeleton that we discussed on trees in lecture. It is easy to overthink this problem and get your code in a mess. The code should follow fairly naturally from the examples and template if you use them carefully. :::  ## Reflection In a comment, describe any questions you have (if any) based on these exercises. ## Handin Turn in a file `bsts.arr` with your code. :::warning ***Information about the Autograder*** After you submit your work, Gradescope will run our autograder tests and display the results. **It is your responsibility to make sure that all six autograder tests pass**. * If you get an error message saying the autograder failed to run, check to make sure that your code file is named `bsts.arr` and that the function names and inputs are *exactly* as asked for in the handout. Also make sure that the `#` character does not appear anywhere in your code (except to start comments). **Specifically for this assignment, make sure that your `BST` data declaration is exactly the same as in this handout (with a `leaf` and a `node` with the relevant fields)** * If you are failing some tests, go back and write some tests of your own and reason through them in your code. Part of the transition from 111 to 200 is getting more practice reasoning about what a comprehensive set of tests looks like. What kind of input trees should you try to make sure that your algorithms are working correctly? The autograder runs our tests on your add-elt and has-elt implementations. Getting a full autograder score does not guarantee that you passed the assignment -- Milda will manually grade your code to make sure that the algorithms were implemented as described in the handout. :::

Read more

Final Exam Prep Guide (Spring 2024)

Mini-Project - Spring 2024

Lab 11

From CS111 to CS200 (Current Version)