Racket project on BST
COMP 333 Spring 2022 Racket Project: BST Part 1 In this project you will implement basic operations on a BST (unbalanced binary search tree). The main operations to implement are find, add (insert), remove (delete), and traverse. In most cases, these functions are supported by the implemented of “helper” functions to streamline the code. Also, a few other functions to support display and testing will be implemented. Detailed test cases will be provided so that you can know how your code will be evaluated. BSTs are normally covered in a basic data structure course such as COMP 182. I will review BSTs in lecture but I will not teach them in depth. If you have not previously studied BSTs, you will need to do some review on your own outside of class. A BST is a data structure that maintains a collection of values linked together in a way to offer O( log n) average-case time complexity for common operations such as insert and delete. This is in comparison to O( n ) for insert and delete in a singly linked list. Balanced BSTs (red-black, AVL, and others) go further and offer O( log n) worst-case time complexity, at the expense of more complex operations that require rotations and rebalancing. We will not consider balanced BSTs for this project. The most common implementation is to define a structure called a node that hold a value and left and right links to other nodes. The BST can then be built as a collection of nodes. The links between the nodes define the tree structure. The entry node to a BST is called the root, and a link to the root must be maintained to support access to the complete tree. The BST property states that for any node, values in the left subtree are less than the node value, and values in the right subtree are greater than the node value. A complete implementation must also decide how to handle multiple nodes with the same value. In this implementation, we will assume that two nodes with the same value are indistinguishable from one another and therefore don’t need to be represented independently. Instead, each node will maintain a count field. When the first occurrence of a value is inserted into the tree, a new node to represent it is created with the count field initialized to 1. When a duplicate value is inserted, a new node is not created. Instead, the count field for the existing node with the same value is incremented. Similar logic applies to the implementation of delete. Avoiding multiple nodes with the same value greatly simplifies the implementation of some operations, especially in the context of rotations. Rotations are used primarily when implementing balanced trees and won’t be implemented here. But avoiding duplicate nodes with identical values is still a good strategy for most implementations. To insert into a BST, the tree must be searched starting at the root and moving down the tree to the left or right, until either a node with the same value is located (increment count field of that node), or a parent node with an empty slot on the correct side for the new value is found (create new node and link to parent node on the appropriate side). While moving down the tree during the search, it will be convenient to create a list of all nodes on the path from root to insertion point. This path will be useful for implementing other operations such as delete. To delete from a BST, the tree must again be searched to locate the node to be deleted. If the node has a count > 1, then we just decrement the count field. If the count field is 1, then the node must actually be deleted. The deletion operation then breaks down into several cases and subcases. The main cases are based on how many child nodes the node to be deleted has. An even more basic operation than insert and delete is the find operation: for a given value v, find the node in the tree which has that value, or indicate that such a node does not exist. For this project, you will implement both insert and delete by first calling the find operation. Furthermore, the find operation will construct a path from the root the requested node, which will either be the node with value v, or in case no such node exists, the node that represents the insertion position for a new node with value v. Calling the find operation and obtaining the path to the node if it exists or its insertion position if it does not will greatly simplify the remaining implementation for both the insert and delete operations. Implementation To simplify the implementation and chop it into smaller pieces, I have divided the functions into three parts, for you to complete in the order shown. Each part has its own test cases. Don’t proceed to the next part until the current part is complete and passes all the tests. Part 1 bst-node struct definition find-path function to find path from root to node for a specific value convert bst to list of nodes using in-order traversal convert list of nodes to list of values (to more easily display contents) test cases Part 2 insert generate list of random numbers to support testing Part 3 delete Part 1 Assignment • Define (struct bst-node …) o Full definition provided as follows (struct bst-node (value count left right) #:mutable #:transparent) • Define (bst-to-list x) function o x: root node of tree or subtree o value: list of nodes of tree or subtree using in-order traversal o algorithm: if x is empty, result is empty list else result is append (inorder(left(x) , x , inorder(right(x)) ) note that result is a list of nodes, not a bst • Define (display-values-list x) function o x: list of nodes, not a bst o value: n/a, uses display, displayln to display text to screen o algorithm if (cdr x) is empty, display value of (car x) else display value of (car x) and call function recursively on (cdr x) use display “ “ to enter spaces or other formatting use bst-node value field accessor to obtain value of node • Define (find-path x v) function o x: root node of tree or subtree o v: value to find in tree or subtree o value: list of nodes from root to node o final node is either node with value v if v is found, or insertion point node if v not found o algorithm if value(x) = v, result is (list x) if v < value(x)="" and="" left(x)="" is="" empty,="" result="" is="" (list="" x)="" ="" if="" v=""> value(x) and right(x) is empty, result is (list x) if v < value(x)="" and="" left(x)="" is="" not="" empty,="" call="" function="" recursively="" on="" left(x),="" append="" result="" with="" (list="" x)="" ="" if="" v=""> value(x) and right(x) is not empty, call function recursively on right(x), append result with (list x) • Define (display-find-path x v) function o This function provides extra formatting for display of test cases o Complete definition provided (define (display-find-path x v) (display "test find-path for ") (display v) (display ": ") (display-values-list (find-path x v)) (displayln "") ) Test Cases for Part 1 The tree shown in the figure is the basis for several test cases for part 1. The test case code builds the tree by repeated calls to the bst-node constructor. The correct way to build the tree is to use the insert function and insert all values into an initially empty bst. But since insert is implemented in part 2, we’ll use this method to create a tree for testing. The test cases use conversion to list and display to display the entire tree. Then the remaining test cases use the find path function to find the path of nodes from root to a particular value. The first few cases show the path from root to a value that is found in the tree. The last few show the path from root to the insertion point node for values not in the tree. In parts 2 and 3, the find path function will be used as the initial part of both insert and delete. ;------------------------------------------------ ; test cases for Part 1 ;------------------------------------------------ ;------------------------------------------------ ; manual build for tree-1 example for testing ;------------------------------------------------ (define n15 (bst-node 77 1 null null)) (define n14 (bst-node 29 1 null null)) (define n13 (bst-node 90 1 null null)) (define n12 (bst-node 76 1 null n15)) (define n11 (bst-node 60 1 null null)) (define n10 (bst-node 28 1 null n14)) (define n9 (bst-node 15 1 null null)) (define n8 (bst-node 10 1 null null)) (define n7 (bst-node 80 1 n12 n13)) (define n6 (bst-node 55 1 null n11)) (define n5 (bst-node 30 1 n10 null)) (define n4 (bst-node 12 1 n8 n9)) (define n3 (bst-node 75 1 n6 n7)) (define n2 (bst-node 25 1 n4 n5)) (define n1 (bst-node 50 1 n2 n3)) (display "inorder traversal ") (display-values-list (bst-to-list n1)) (displayln "") (display-find-path n1 50) (display-find-path n1 30) (display-find-path n1 55) (display-find-path n1 10) (display-find-path n1 76) (display-find-path n1 77) (display-find-path n1 90) (display-find-path n1 61) (display-find-path n1 13) (display-find-path n1 78) Output From Test Cases for Part 1 inorder traversal 10 12 15 25 28 29 30 50 55 60 75 76 77 80 90 ; shows all nodes in tree in order test find-path for 50: 50 ; these tests show results for values in the tree test find-path for 30: 30 25 50 test find-path for 55: 55 75 50 test find-path for 10: 10 12 25 50 test find-path for 76: 76 80 75 50 test find-path for 77: 77 76 80 75 50 test find-path for 90: 90 80 75 50 test find-path for 61: 60 55 75 50 ; 61 not in tree, but 60 is insertion point for 61 test find-path for 13: 15 12 25 50