Instructions
Objective
Write a Racket assignment to create a BST tree.
Requirements and Specifications
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 implementation of “helper” functions to streamline the code. Also, a few other functions to support display and testing will be implemented.
Create a new Racket source file, copy all definitions from part 1 to use as your starting point for part 2.
Then add the following definitions for part 2.
- Define (bst-node-add x v)
- Function adds new value v to existing bst with root x
- If x is empty, create a new bst-node with value v, node is value of function
- Else
o call find-path to find path p to insertion point.
o call helper function bst-add-path with arguments for x, path p, and value v.
- Define (bst-add-path x p v)
- Helper function that adds new node for value v
- p: path from root to insertion point node, (car p) is the insertion point node
- if insertion point node has value v, increment count field, don’t insert new node
- if insertion point node doesn’t have value v, create new node for v, add it at insertion point
- In either case, the find-path function will find the node to be modified.
- Define (gen-random-list n rng)
- If n is 1, create a list of a random number from 0 to rng
- Else gen one random number, create a list, append to recursive call to function with n
- The function (random) produces a random number between 0.0 and 1.0. Multiply it by rng, take the floor, then convert inexact to exact to get a random integer:
replaced with n-1.
(inexact->exact (floor (* rng (random))))
- Define (bst-node-add-list x y)
- x: existing bst
- y: list of values to add
- If y is empty, result is x
- Else call (bst-node-add x (car y)) to add one value to bst, use set! to make value the new
value of x, then call function recursively using x and (cdr y).
A Typical BST Add Test
- Generate a list of 10 random numbers from 0 to 1000
- Add list of numbers to an initially empty tree
- Convert tree to an in-order traversal list
- Display values in list
- Use find-path to check paths to some nodes
- may need to sketch tree to confirm paths are correct
Screenshots of output
Source Code
Part 1
#lang racket
;------------------------
; Part 1 definitions
;------------------------
(struct bst-node (value count left right) #:mutable #:transparent)
(define (bst-to-list x)
(if (empty? x)
null
(append (bst-to-list (bst-node-left x)) (list x) (bst-to-list (bst-node-right x)))))
(define (display-values-list x)
(cond
[(null? x) (display "")]
[(null? (cdr x)) (display (bst-node-value (car x)))]
[else (display (bst-node-value (car x)))
(display " ")
(display-values-list (cdr x))]))
(define (find-path x v)
(cond
[(empty? x) null]
[(= v (bst-node-value x)) (list x)]
[(< v (bst-node-value x)) (append (find-path (bst-node-left x) v) (list x))]
[(> v (bst-node-value x)) (append (find-path (bst-node-right x) v) (list x))]))
(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
;------------------------------------------------
;------------------------------------------------
; 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)
Part 2
#lang racket
;------------------------
; Part 1 definitions
;------------------------
(struct bst-node (value count left right) #:mutable #:transparent)
(define (bst-to-list x)
(if (empty? x)
null
(append (bst-to-list (bst-node-left x)) (list x) (bst-to-list (bst-node-right x)))))
(define (display-values-list x)
(cond
[(null? x) (display "")]
[(null? (cdr x)) (display (bst-node-value (car x)))]
[else (display (bst-node-value (car x)))
(display " ")
(display-values-list (cdr x))]))
(define (find-path x v)
(cond
[(empty? x) null]
[(= v (bst-node-value x)) (list x)]
[(< v (bst-node-value x)) (append (find-path (bst-node-left x) v) (list x))]
[(> v (bst-node-value x)) (append (find-path (bst-node-right x) v) (list x))]))
(define (display-find-path x v)
(display "test find-path for ")
(display v)
(display ": ")
(display-values-list (find-path x v))
(displayln ""))
;------------------------
; Part 2 definitions
;------------------------
(define (bst-node-add x v)
(if (empty? x)
(bst-node v 1 empty empty)
(bst-add-path x (find-path x v) v)))
(define (bst-add-path x p v)
(let ([n (car p)])
(cond
[(= v (bst-node-value n))
(set-bst-node-count! n (+ (bst-node-count n) 1))]
[(< v (bst-node-value n))
(set-bst-node-left! n (bst-node v 1 empty empty))]
[else
(set-bst-node-right! n (bst-node v 1 empty empty))]))
x)
(define (gen-random-list n rng)
(if (= n 0)
null
(cons (inexact->exact (floor (* rng (random)))) (gen-random-list (- n 1) rng))))
(define (bst-node-add-list x y)
(if (null? y)
x
(bst-node-add-list (bst-node-add x (car y)) (cdr y))))
;------------------------
; test for list add with nested function calls
;------------------------
(displayln "")
(display "add rand list to empty bst ")
(display-values-list (bst-to-list (bst-node-add-list empty (gen-random-list 10 1000))));------------------------
; test for list add with symbols defined for intermediate steps
;------------------------
(define rand-list-1 (gen-random-list 10 1000))
(define tree-1 (bst-node-add-list empty rand-list-1))
(define tree-1-list (bst-to-list tree-1))
(displayln "") (display "random list") rand-list-1 (displayln "")
(display-values-list (bst-to-list tree-1)) (displayln "")
; first displays original random numbers
; then displays tree after inserting random numbers and traversing
; note that traversal displays numbers in sorted order
(display-find-path tree-1 (list-ref rand-list-1 0))
(display-find-path tree-1 (list-ref rand-list-1 3))
(display-find-path tree-1 (list-ref rand-list-1 4))
(display-find-path tree-1 (list-ref rand-list-1 5))
(display-find-path tree-1 (list-ref rand-list-1 7))
; displays path for a few of the values in the tree
; note that random values will be different for each run
Part 3
#lang racket
;------------------------
; Part 1 definitions
;------------------------
(struct bst-node (value count left right) #:mutable #:transparent)
(define (bst-to-list x)
(if (empty? x)
null
(append (bst-to-list (bst-node-left x)) (list x) (bst-to-list (bst-node-right x)))))
(define (display-values-list x)
(cond
[(null? x) (display "")]
[(null? (cdr x)) (display (bst-node-value (car x)))]
[else (display (bst-node-value (car x)))
(display " ")
(display-values-list (cdr x))]))
(define (find-path x v)
(cond
[(empty? x) null]
[(= v (bst-node-value x)) (list x)]
[(< v (bst-node-value x)) (append (find-path (bst-node-left x) v) (list x))]
[(> v (bst-node-value x)) (append (find-path (bst-node-right x) v) (list x))]))
(define (display-find-path x v)
(display "test find-path for ")
(display v)
(display ": ")
(display-values-list (find-path x v))
(displayln ""))
;------------------------
; Part 2 definitions
;------------------------
(define (bst-node-add x v)
(if (empty? x)
(bst-node v 1 empty empty)
(bst-add-path x (find-path x v) v)))
(define (bst-add-path x p v)
(let ([n (car p)])
(cond
[(= v (bst-node-value n))
(set-bst-node-count! n (+ (bst-node-count n) 1))]
[(< v (bst-node-value n))
(set-bst-node-left! n (bst-node v 1 empty empty))]
[else
(set-bst-node-right! n (bst-node v 1 empty empty))]))
x)
(define (gen-random-list n rng)
(if (= n 0)
null
(cons (inexact->exact (floor (* rng (random)))) (gen-random-list (- n 1) rng))))
(define (bst-node-add-list x y)
(if (null? y)
x
(bst-node-add-list (bst-node-add x (car y)) (cdr y))))
;------------------------
; Part 3 definitions
;------------------------
(define (get-child-count x)
(+ (if (empty? (bst-node-left x)) 0 1) (if (empty? (bst-node-right x)) 0 1)))
(define (find-path-pred x)
(find-path-pred-right (list (bst-node-left x) x)))
(define (find-path-pred-right p)
(let ([n (car p)])
(if (empty? (bst-node-right n))
p
(find-path-pred-right (cons (bst-node-right n) p)))))
(define (bst-node-delete x v)
(bst-node-delete-path x (find-path x v) v))
(define (bst-node-delete-path x p v)
(if (null? p)
x
(let ([n (car p)])
(cond
[(not (= v (bst-node-value n))) x]
[(> (bst-node-count n) 1)
(set-bst-node-count! n (- (bst-node-count n) 1))
x]
[(= (get-child-count n) 0) (bst-node-delete-path-0 x p v)]
[(= (get-child-count n) 1) (bst-node-delete-path-1 x p v)]
[(= (get-child-count n) 2) (bst-node-delete-path-2 x p v)]))))
(define (bst-node-delete-path-0 x p v)
(if (null? (cdr p))
empty
(let ([n (car p)]
[pp (cadr p)])
(if (equal? n (bst-node-left pp))
(set-bst-node-left! pp empty)
(set-bst-node-right! pp empty))
x)))
(define (bst-node-delete-path-1 x p v)
(let* ([n (car p)]
[nl (bst-node-left n)]
[nr (bst-node-right n)])
(if (null? (cdr p))
(if (null? nr) nl nr)
(let ([pp (cadr p)])
(if (equal? n (bst-node-left pp))
(if (null? nr)
(set-bst-node-left! pp nl)
(set-bst-node-left! pp nr))
(if (null? nr)
(set-bst-node-right! pp nl)
(set-bst-node-right! pp nr)))
x))))
(define (bst-node-delete-path-2 x p v)
(let* ([n (car p)]
[pp (find-path-pred n)]
[r (car pp)]
[q (cadr pp)])
(set-bst-node-value! n (bst-node-value r))
(set-bst-node-count! n (bst-node-count r))
(if (equal? r (bst-node-left q))
(set-bst-node-left! q (bst-node-left r))
(set-bst-node-right! q (bst-node-left r)))
x))
; create test tree t1
; each call to (bst-node-add ...) adds a new node to t
; the (set! ...) function ensures that t1 is always bound to root of tree
; even if the root was changed by the (bst-node-add ...) function
(define t1 (bst-node-add empty 50)) ; 1 st node 50
(set! t1 (bst-node-add t1 25)) ; 2 nd node 25
(set! t1 (bst-node-add t1 75)) ; ...
(set! t1 (bst-node-add t1 12))
(set! t1 (bst-node-add t1 37))
(set! t1 (bst-node-add t1 60))
(set! t1 (bst-node-add t1 80))
(set! t1 (bst-node-add t1 13))
(set! t1 (bst-node-add t1 36))
(set! t1 (bst-node-add t1 59))
(set! t1 (bst-node-add t1 81))
(display-values-list (bst-to-list t1))
(displayln ""); test cases to delete specific values then display resulting tree
; delete cases for 12, 37, 60, 80 test cases 1.3 through 1.6
(set! t1 (bst-node-delete t1 12)) (display-values-list (bst-to-list t1))
(displayln "")
(set! t1 (bst-node-delete t1 37)) (display-values-list (bst-to-list t1))
(displayln "")
(set! t1 (bst-node-delete t1 60)) (display-values-list (bst-to-list t1))
(displayln "")
(set! t1 (bst-node-delete t1 80)) (display-values-list (bst-to-list t1))
(displayln "")
; delete cases for 13, 36, 59, 81 test cases 0.2 and 0.3
(set! t1 (bst-node-delete t1 13)) (display-values-list (bst-to-list t1))
(displayln "")
(set! t1 (bst-node-delete t1 36)) (display-values-list (bst-to-list t1))
(displayln "")
(set! t1 (bst-node-delete t1 59)) (display-values-list (bst-to-list t1))
(displayln "")
(set! t1 (bst-node-delete t1 81)) (display-values-list (bst-to-list t1))
(displayln "")
; start with original t1 before deletion tests
(set! t1 (bst-node-add empty 50))
(set! t1 (bst-node-add t1 25))
(set! t1 (bst-node-add t1 75))
(set! t1 (bst-node-add t1 12))
(set! t1 (bst-node-add t1 37))
(set! t1 (bst-node-add t1 60))
(set! t1 (bst-node-add t1 80))
(set! t1 (bst-node-add t1 13))
(set! t1 (bst-node-add t1 36))
(set! t1 (bst-node-add t1 59))
(set! t1 (bst-node-add t1 81))
; following displays paths from specific node to its predecessor
(displayln "")
(display "Path from predecessor of 50 to 50: ")
(display-values-list (find-path-pred (car (find-path t1 50))))
(displayln "")
(display "Path from predecessor of 75 to 75: ")
(display-values-list (find-path-pred (car (find-path t1 75))))
(displayln "")
(display "Path from predecessor of 25 to 25: ")
(display-values-list (find-path-pred (car (find-path t1 25))))
(displayln "")
(set! t1 (bst-node-delete t1 50)) (display-values-list (bst-to-list t1))
(displayln "")
(displayln "")
(displayln "Final Test Case for Add and Delete:")
; create list of random values
(define r-list-1 (gen-random-list 10 1000))
r-list-1
; create initially empty BST
(define bst-1 empty)
bst-1
; use for loop to insert all values from list into BST
; display tree after every insert
(for ((n r-list-1)) ; run for loop setting n to each value in r-list-1
(display "insert ") ; formatting
(display n) ; formatting
(display ": ") ; formatting
(set! bst-1 (bst-node-add bst-1 n)) ; add n to bst-1, update bst-1 binding
(display-values-list (bst-to-list bst-1)) ; display updated bst-1
(displayln ""))
; use for loop to delete all values from BST
; display tree after every delete
(for ((n r-list-1)) ; run for loop setting n to each value in r-list-1
(display "delete ") ; formatting
(display n) ; formatting
(display ": ") ; formatting
(set! bst-1 (bst-node-delete bst-1 n)) ; delete n from bst-1, update bst-1 binding
(display-values-list (bst-to-list bst-1)) ; display updated bst-1
(displayln ""))