41.1 Introduction to binary search trees

The binary search trees are tree structures in which every node has at most two children. Every node is associated to a “sort key”: a value that can be used to establish an ordering among the nodes. The node insertion and node removal operations are implemented in such a way that:

• The left child of a node has key less than the one the node.
• The right child of a node has key greater than, or equal to, the one of the node.

Here is an example of binary search tree, with nodes in the correct order:

5-------10----12
|        |     |
1--3--4  7--9 11
   |     |  |
   2     6  8

the root node has sort key ‘5’; the left child of the root has sort key ‘1’; the right child of the root has sort key ‘10’. Let’s take ‘10’ as example: every node in its left subtree has key less than ‘10’; every node in its right subtree has key greater than, or equal to, ‘10’. This is a general property of binary search trees.

The library (vicare containers binary-search-trees) is the core library for binary search tree implementation; it implements trees in such a way that:

• The empty tree is represented by #f.
• A node is represented by an instance of type <binary-node> or a subtype of this type.
• The type <binary-node> has 3 fields: parent, left, right. The value of these fields can be #f or an instance of <binary-node>.
• If the parent field of a node is set to #f: it means that node is the root of a tree.

All the functions acting on instances of <binary-node> are meant to be usable on trees implementing any node balancing strategy; they only expect the binary tree to be a binary search tree as defined above. The core library only implements unbalanced binary search trees, in which nodes have the type <unbalanced-binary-node>. The type hierarchy is:

(define-record-type <binary-node>
  ---)

(define-record-type <unbalanced-binary-node>
  (parent <binary-node>)
  ---)

By themselves, these types have no sort key; to associate a sort key with a node instance we need to subtype them. The following is an example of binary search tree of fixnums:

(import (vicare)
  (vicare containers binary-search-trees))

(define-record-type <fixnum-node>
  (parent <unbalanced-binary-node>)

  (fields (immutable sort-key))

  (protocol
   (lambda (make-unbalanced-binary-node)
     (case-lambda*
       (()
        ((make-unbalanced-binary-node #f #f) (void)))

       ((key)
        ((make-unbalanced-binary-node #f #f) key))

       (({key   fixnum?}
         {left  false-or-unbalanced-binary-node?}
         {right false-or-unbalanced-binary-node?})
        ((make-unbalanced-binary-node left right) key)))))

  #| end of DEFINE-RECORD-TYPE |# )

(define (key< new old)
  (fx<? (<fixnum-node>-sort-key new)
        (<fixnum-node>-sort-key old)))

(define (make-comparison-proc target-key)
  (lambda (node)
    (let ((key (<fixnum-node>-sort-key node)))
      (cond ((fx=? target-key key)       0)
            ((fx<? target-key key)      -1)
            (else                       +1)))))

we can build a tree from a list and then search for a node as follows:

(define (tree . key*)
  (fold-left (lambda (root key)
               (unbalanced-tree-insert! root key<
                  (make-<fixnum-node> key)))
    #f key*))

;; 5-------10----12
;; |        |     |
;; 1--3--4  7--9 11
;;    |     |  |
;;    2     6  8
(define root
  (tree 5 1 3 2 4 10 7 12 6 9 8 11))

(define node
  (binary-tree-find root (make-comparison-proc 8)))

we can perform a forwards in–order iteration as follows:

(binary-tree-fold-in-order-forwards
    (lambda (knil node)
      (cons (<fixnum-node>-sort-key node) knil))
  '() root))
⇒ (12 11 10 9 8 7 6 5 4 3 2 1)

in the result of this operation: the sort key in the first node from the search is the last item in the list.