Trees

Nievergelt & Hinrichs · Ch. 5 · Algorithms and Data Structures

A binary search tree keeps keys ordered: left child < parent < right child. Unbalanced, it degrades to a linked list. AVL trees restore balance after every insertion. B-trees generalize to disk-friendly multi-way branching.

Binary search tree

Insert, search, and delete all follow the same path from root to leaf. Average depth O(log n) for random insertions. Worst case O(n) for sorted input.

Scheme

; BST: insert and search
; Tree = () | (key left right)

(define (make-node key) (list key (list) (list)))
(define (node-key t) (car t))
(define (node-left t) (cadr t))
(define (node-right t) (caddr t))

(define (bst-insert tree key)
  (cond ((null? tree) (make-node key))
        ((< key (node-key tree))
         (list (node-key tree)
               (bst-insert (node-left tree) key)
               (node-right tree)))
        ((> key (node-key tree))
         (list (node-key tree)
               (node-left tree)
               (bst-insert (node-right tree) key)))
        (else tree)))

(define (bst-search tree key)
  (cond ((null? tree) #f)
        ((= key (node-key tree)) #t)
        ((< key (node-key tree)) (bst-search (node-left tree) key))
        (else (bst-search (node-right tree) key))))

(define t (list))
(set! t (bst-insert t 20))
(set! t (bst-insert t 10))
(set! t (bst-insert t 30))
(set! t (bst-insert t 5))
(set! t (bst-insert t 15))

(display "Search 15: ") (display (bst-search t 15)) (newline)
(display "Search 25: ") (display (bst-search t 25))

; BST: insert and search
; Tree = () | (key left right)

(define (make-node key) (list key (list) (list)))
(define (node-key t) (car t))
(define (node-left t) (cadr t))
(define (node-right t) (caddr t))

(define (bst-insert tree key)
  (cond ((null? tree) (make-node key))
        ((< key (node-key tree))
         (list (node-key tree)
               (bst-insert (node-left tree) key)
               (node-right tree)))
        ((> key (node-key tree))
         (list (node-key tree)
               (node-left tree)
               (bst-insert (node-right tree) key)))
        (else tree)))

(define (bst-search tree key)
  (cond ((null? tree) #f)
        ((= key (node-key tree)) #t)
        ((< key (node-key tree)) (bst-search (node-left tree) key))
        (else (bst-search (node-right tree) key))))

(define t (list))
(set! t (bst-insert t 20))
(set! t (bst-insert t 10))
(set! t (bst-insert t 30))
(set! t (bst-insert t 5))
(set! t (bst-insert t 15))

(display "Search 15: ") (display (bst-search t 15)) (newline)
(display "Search 25: ") (display (bst-search t 25))

Tree traversals

Inorder (left, root, right) gives sorted output. Preorder (root, left, right) gives a serialization that can reconstruct the tree. Postorder (left, right, root) evaluates expressions bottom-up.

Scheme

; Three traversals of the same tree
; Tree: (key left right)

(define tree
  (list 20
    (list 10 (list 5 (list) (list)) (list 15 (list) (list)))
    (list 30 (list 25 (list) (list)) (list 35 (list) (list)))))

(define (inorder t)
  (if (null? t) (list)
      (append (inorder (cadr t))
              (list (car t))
              (inorder (caddr t)))))

(define (preorder t)
  (if (null? t) (list)
      (append (list (car t))
              (preorder (cadr t))
              (preorder (caddr t)))))

(define (postorder t)
  (if (null? t) (list)
      (append (postorder (cadr t))
              (postorder (caddr t))
              (list (car t)))))

(display "Inorder:   ") (display (inorder tree)) (newline)
(display "Preorder:  ") (display (preorder tree)) (newline)
(display "Postorder: ") (display (postorder tree))

Neighbors

Cross-references

🐱 Milewski Ch.19 — trees as initial algebras: fold over a tree is a catamorphism

← Searching by june.kim Graphs →