immutable-binary-search-trees

This is a more or less stream of consciousness implementation of an immutable binary search tree. Trees are represented as empty or three-element lists:

 (define (ibst-make . args) 
  
   ; Return a bst.  If there are no arguments, return an empty bst.  If 
   ; there is one argument, return a leaf bst having the argument as 
   ; its value.  If there are three arguments, return a bst with the 
   ; first, second, and third arguments as the bst's value, left child, 
   ; and right child respectively.  If there are any other number of 
   ; arguments, die with an error message. 
  
   (let ((n (length args))) 
     (cond 
       ((zero? n) 
          '()) 
       ((= n 1) 
         (ibst-makeo (car args) (ibst-make) (ibst-make))) 
       ((= n 3) 
         args) 
       (#t 
         (error "ibst-make argument count not 0, 1, or 3: " n))))) 
  
 (define ibst-value car) 
 (define ibst-left-child cadr) 
 (define ibst-right-child caddr) 
  
 (define ibst-empty? null?) 

The tree-membership procedure looks as you'd expect.

 (define (ibst-member? root v) 
  
   ; Return #t iff the given bst contains the given value. 
  
   (if (ibst-empty? root) 
     #f 
     (let ((value (ibst-value root))) 
       (if (= v value) 
         #t 
         (ibst-member? 
           ((if (< v value) ibst-left-child ibst-right-child) root) v))))) 

Because the trees are immutable, the element-add and element-delete procedures may have an unexpected look: each returns a tree with the appropriate relation to the tree and element given as input to the associated procedure.

 (define (ibst-add root v) 
  
   ; Return a bst containing all the values in the given bst and one 
   ; extra value equal to the given value.  The returned bst can 
   ; contain multiples of the same value. 
  
   (if (ibst-empty? root) 
     (ibst-make v) 
     (let 
       ((right (ibst-right-child root)) 
        (left (ibst-left-child root)) 
        (value (ibst-value root))) 
  
       (if (< v value) 
         (ibst-make value (ibst-add left v) right) 
         (ibst-make value left (ibst-add right v)))))) 
  
 (define (ibst-delete root v) 
  
   ; Return a bst that contains one fewer nodes with the value v than 
   ; does the bst root; if root doesn't contain v, the returned bst is 
   ; a copy of root. 
  
   (define (get-min root) 
  
     ; Return a pair (v . t), where v is the smallest value in the 
     ; non-empty bst root, and t is a bst containing all the values in 
     ; root except for v. 
  
     (let 
       ((right (ibst-right-child root)) 
        (left (ibst-left-child root)) 
        (value (ibst-value root))) 
  
       (if (ibst-empty? left) 
         (cons value right) 
         (let ((res (get-min left))) 
           (cons (car res) (ibst-make value (cdr res) right)))))) 
  
  
   (define (get-max root) 
  
     ; Return a pair (v . t), where v is the largest value in the 
     ; non-empty bst root, and t is a bst containing all the values in 
     ; root except for v. 
  
     (let 
       ((right (ibst-right-child root)) 
        (left (ibst-left-child root)) 
        (value (ibst-value root))) 
  
       (if (ibst-empty? right) 
         (cons value left) 
         (let ((res (get-max right))) 
           (cons (car res) (ibst-make value left (cdr res))))))) 
  
   (if (ibst-empty? root) 
     root 
     (let 
       ((value (ibst-value root)) 
        (left (ibst-left-child root)) 
        (right (ibst-right-child root))) 
  
       (cond 
         ((= value v) 
           (cond 
             ((not (ibst-empty? left)) 
                (let ((res (get-max left))) 
                  (ibst-make (car res) (cdr res) right))) 
  
             ((not (ibst-empty? right)) 
                (let ((res (get-min right))) 
                  (ibst-make (car res) left (cdr res)))) 
  
             (#t 
               (ibst-make)))) 
  
         ((< value v) 
            (ibst-make value left (ibst-delete right v))) 
  
         (#t 
            (ibst-make value (ibst-delete left v) right)))))) 

If you don't like trees implemented as lists, you can implement them as vectors.

 (define (ibst-make . args) 
  
   ; Return a bst.  If there are no arguments, return an empty bst.  If 
   ; there is one argument, return a leaf bst having the argument as 
   ; its value.  If there are three arguments, return a bst with the 
   ; first, second, and third arguments as the bst's value, left child, 
   ; and right child respectively.  If there are any other number of 
   ; arguments, die with an error message. 
  
   (let ((n (length args))) 
     (cond 
       ((zero? n) 
         (make-vector 0)) 
       ((= n 1) 
         (ibst-make (car args) (ibst-make) (ibst-make))) 
       ((= n 3) 
         (list->vector args)) 
       (#t 
         (error "ibst-make argument count not 0, 1, or 3: " n))))) 
  
 (define (ibst-value ibst) (vector-ref ibst 0)) 
 (define (ibst-left-child ibst) (vector-ref ibst 1)) 
 (define (ibst-right-child ibst) (vector-ref ibst 2)) 
  
 (define (ibst-empty? ibst) (zero? (vector-length ibst))) 

category-code