Faster, Simpler Red-Black Trees

Summary
Racket Implementation
Notes

Summary

This paper presents improvements to functional red-black tree algorithms:

A faster insertion algorithm using a monad to communicate balancing information
A simpler deletion algorithm using the same monad and new auxiliary operations
Performance evaluation comparing several red-black tree implementations

Key points:

Uses a Result monad to handle balancing information
New balance' and eq functions simplify deletion logic
Monadic insertion is up to 1.56x faster than Okasaki's original
Monadic deletion performs similarly to the best existing algorithm
Provides implementations in both Haskell and Racket

Racket Implementation

#lang racket

;; Data structures
(struct E ())
(struct N (color left value right))

(define-syntax-rule (define-color name)
  (begin
    (define-for-syntax (transf stx)
      (syntax-case stx ()
        [(_ a x b) #'(N 'name a x b)]))
    (define-match-expander name transf transf)))

(define-color R)
(define-color B)

;; Monad helper functions
(define-syntax-rule (todo x)
  (values true x))

(define-syntax-rule (done x)
  (values false x))

(define-syntax-rule (from-result x)
  (let-values ([(_ y) x])
    y))

(define-syntax-rule (<$$> f x)
  (let-values ([(a d) x])
    (values a (f d))))

(define-syntax-rule (=<< f x)
  (let-values ([(ax dx) x])
    (if ax (f dx) (values ax dx))))

;; Deletion function
(define (delete t x)
  (define (del t)
    (match-define (N k a y b) t)
    (cond
      [(< x y) (=<< del-left (<$$> (λ (a) (N k a y b)) (del a)))]
      [(> x y) (=<< del-right (<$$> (λ (b) (N k a y b)) (del b)))]
      [else (del-root t)]))
  (from-result (del t)))

(define (del-root t)
  (match t
    [(B a y (E)) (blacken* a)]
    [(R a y (E)) (done a)]
    [(N k a y b)
     (define m (box false))
     (=<< del-right (<$$> (λ (b) (N k a (unbox m) b)) (del-min b m)))]))

(define (del-min t m)
  (match t
    [(B (E) y b) (set-box! m y) (blacken* b)]
    [(R (E) y b) (set-box! m y) (done b)]
    [(N k a y b)
     (=<< del-left (<$$> (λ (a) (N k a y b)) (del-min a m)))]))

(define (del-left t)
  (match t
    [(N k a y (R c z d))
     (<$$> (λ (a) (B a z d)) (del-left (R a y c)))]
    [(N k a y (B c z d))
     (balance* (N k a y (R c z d)))]))

(define (del-right t)
  (match t
    [(N k (R a x b) y c)
     (<$$> (λ (b) (B a x b)) (del-right (R b y c)))]
    [(N k (B a x b) y c)
     (balance* (N k (R a x b) y c))]))

(define (balance* t)
  (match t
    [(or (N k (R a x (R b y c)) z d)
         (N k (R (R a x b) y c) z d)
         (N k a x (R (R b y c) z d))
         (N k a x (R b y (R c z d))))
     (done (N k (B a x b) y (B c z d)))]
    [_ (blacken* t)]))

(define (blacken* t)
  (match t
    [(R a x b) (done (B a x b))]
    [_ (todo t)]))

;; Example usage
(module+ main
  (define tree (N 'B (N 'R (E) 1 (E)) 2 (N 'R (E) 3 (E))))
  (displayln "Original tree:")
  (pretty-print tree)
  (displayln "After deleting 2:")
  (pretty-print (delete tree 2)))

Notes

The implementation focuses on the deletion algorithm, as it's the main contribution of the paper
The insertion algorithm improvement is not shown here, but follows a similar pattern using the Result monad
The performance evaluation results are not reproduced, but the paper reports significant improvements over existing implementations

Faster, Simpler Red-Black Trees

Table of Contents

Summary

Racket Implementation

Notes