I am learning Racket and implemented a BST insert function (insert tree n)
where the format for a BST node is (left-tree value right-tree)
.
Example
'((() 2 ()) 3 ()) is isomorphic to:
(3)
(2) ()
() ()
Therefore (insert '((() 2 ()) 3 ()) 4)
yields ((() 2 ()) 3 (() 4 ()))
:
(3)
(2) (4)
() () () ()
Implementation
My implementation feels overly complicated. For example, I used append
with cons
so that the right-tree for 3, represented by ()
, would properly become (() 4 ())
after inserting 4.
How can I approach this problem more elegantly or more functionally?
#lang racket
(define (left tree)
(list-ref tree 0)
)
(define (value tree)
(list-ref tree 1)
)
(define (right tree)
(list-ref tree 2)
)
(define (merge left value right)
(append (cons left '()) (append (cons value '()) (cons right '())))
)
(define (insert tree n)
(cond
[(empty? tree) (append '(()) (cons n '()) '(()))] ; leaf
[(> (value tree) n) (merge (insert (left tree) n) (value tree)(right tree))] ; internal - go left
[(< (value tree) n) (merge (left tree) (value tree) (insert (right tree) n))] ; internal - go right
[(eq? (value tree) n) tree] ; internal - n already in tree
)
)
Update
Given the answer to the question, I updated my code:
(define (insert BST n)
(cond
[(empty? BST) ; leaf
(list empty n empty)]
[(< n (cadr BST)) ; internal - go left
(list (insert (car BST) n) (cadr BST) (caddr BST))]
[(> n (cadr BST)) ; internal - go right
(list (car BST) (cadr BST) (insert (caddr BST) n))]
[else
BST]
)
)