***LANGUAGE IS SCHEME*** 3. In lab this week, you wrote some functions to work w
ID: 3603750 • Letter: #
Question
***LANGUAGE IS SCHEME***
3. In lab this week, you wrote some functions to work with binary trees. In this question, you will develop some code for binary search trees, as we have been doing in lecture. The representation of a binary search tree will be the same as the binary trees we used in lab, that is, a tree is a three-element list: the value of the node, the left subtree, and the right subtree, with empty trees represented as the empty list. Unlike the binary search trees we have been discussing in lecture, for the questions here we will assume all of the values are strings, so you will need to use the comparison functions string string>?, and string-? functions to build and search through your trees. Note: For all of the binary search tree problems in 3 and 4, you should work with the data in the tree (or trees), and not extract the data from the tree into a list and solve the problem on the list. While that strategy could work, you would lose the advantages of having the data in a binary search tree, and will not get credit for these even if the code passes the Mimir tests.Explanation / Answer
An important special kind of binary tree is the binary search tree (BST). In a BST, each node stores some information including a unique key value, and perhaps some associated data. A binary tree is a BST iff, for every node n in the tree:
Note: if duplicate keys are allowed, then nodes with values that are equal to the key in node n can be either in n's left subtree or in its right subtree (but not both). In these notes, we will assume that duplicates are not allowed.
Here are some BSTs in which each node just stores an integer key
The reason binary-search trees are important is that the following operations can be implemented efficiently using a BST:
To implement a BST that stores some data with each key, we would use the following class definitions (changes are in red):
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.