Faster, Simpler Red-Black Trees in Guile Scheme

Introduction
Implementation
Usage Example
Conclusion

Introduction

This file implements the faster, simpler red-black trees described in Chris Okasaki's paper "Faster, Simpler Red-Black Trees" using Guile Scheme. It demonstrates key concepts like lazy evaluation and structural abstraction.

Implementation

Basic Tree Structure

(define-module (red-black-tree)
  #:export (empty insert lookup))

(define-record-type <tree>
  (make-tree color left key value right)
  tree?
  (color tree-color)
  (left tree-left)
  (key tree-key)
  (value tree-value)
  (right tree-right))

(define (black left key value right)
  (make-tree 'black left key value right))

(define (red left key value right)
  (make-tree 'red left key value right))

(define empty #f)

(define (empty? tree) (not tree))

Insertion

(use-modules (red-black-tree))

(define (balance color left k v right)
  (match `(,color ,left ,k ,v ,right)
    (('black ($ <tree> 'red ($ <tree> 'red a x xv b) y yv c) z zv d)
     (red (black a x xv b) y yv (black c z zv d)))
    (('black ($ <tree> 'red a x xv ($ <tree> 'red b y yv c)) z zv d)
     (red (black a x xv b) y yv (black c z zv d)))
    (('black a x xv ($ <tree> 'red ($ <tree> 'red b y yv c) z zv d))
     (red (black a x xv b) y yv (black c z zv d)))
    (('black a x xv ($ <tree> 'red b y yv ($ <tree> 'red c z zv d)))
     (red (black a x xv b) y yv (black c z zv d)))
    (_ (make-tree color left k v right))))

(define (insert-aux tree key value)
  (if (empty? tree)
      (red empty key value empty)
      (let ((color (tree-color tree))
            (left (tree-left tree))
            (k (tree-key tree))
            (v (tree-value tree))
            (right (tree-right tree)))
        (cond
         ((< key k)
          (balance color (insert-aux left key value) k v right))
         ((> key k)
          (balance color left k v (insert-aux right key value)))
         (else (make-tree color left key value right))))))

(define (insert tree key value)
  (let ((new-tree (insert-aux tree key value)))
    (black (tree-left new-tree)
           (tree-key new-tree)
           (tree-value new-tree)
           (tree-right new-tree))))

Lookup

(use-modules (red-black-tree))

(define (lookup tree key)
  (if (empty? tree)
      #f
      (let ((k (tree-key tree))
            (v (tree-value tree)))
        (cond
         ((< key k) (lookup (tree-left tree) key))
         ((> key k) (lookup (tree-right tree) key))
         (else v)))))

Usage Example

(use-modules (red-black-tree))

(define tree empty)
(set! tree (insert tree 5 'a))
(set! tree (insert tree 3 'b))
(set! tree (insert tree 7 'c))

(display (lookup tree 3)) ; Should display 'b'
(newline)
(display (lookup tree 6)) ; Should display #f
(newline)

Conclusion

This implementation demonstrates the key ideas from Okasaki's paper in Guile Scheme. It uses pattern matching for the balancing operation and implements the basic operations of insertion and lookup. The tree structure is purely functional, maintaining persistence.