Red-Black Trees
October 2, 2009
A red-black tree is a data structure, similar to a binary tree, which is always approximately balanced, so that individual insert and lookup operations take only O(log n) time. Red-black trees are popular because of their good performance and the relative simplicity of their balancing operations. Our discussion of red-black trees is drawn from Section 3.3 of Chris Okasaki’s book Purely Functional Data Structures.
A red-black tree is a binary search tree in which each node is colored either red or black. A red-black tree maintains two invariants that ensure its balance:
- No red node ever has a red child.
- Every path from the root to an empty node has the same number of black nodes.
Thus, the shortest possible path has only black nodes, and the longest possible path has alternating red and black nodes, so the longest path is never more than twice as long as the shortest path, and the tree is approximately balanced.
Lookup in red-black trees is identical to its binary-tree counterpart; the colors make no difference. The balance condition is maintained by the insert operation. Each new node is initially colored red. If its parent is black, the tree remains balanced, and nothing need be done. However, if its parent is red, the first invariant is violated, and a balancing function is called to repair the violation by rewriting the black-red-red path as a red node with two black children. This may propagate the invariant up the tree, so the balancing function is called recursively until it reaches the root of the tree, which is always recolored black.
Your task is to write functions to maintain red-black trees; you should provide an insert function, a lookup function, and an enlist function that returns a list with the nodes of the tree in order. Each node should contain a key and a value, so the red-black tree can be used as a dictionary, in the manner of the treaps and ternary search tries that we have written in previous exercises. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
I needed red-black trees for some static analysis work, but I wanted to be able to add tags to internal nodes.
Here’s the implementation I came up with for Scala based on the Okasaki book:
http://matt.might.net/articles/implementation-of-immutable-purely-functional-okasaki-red-black-tree-maps-in-scala/
#include <stdlib.h> typedef struct RedBlackTreeNode { int key; int color; struct RedBlackTreeNode* left; struct RedBlackTreeNode* right; }rbtree; static rbtree* RedBlackTree_insert_imp(rbtree *p, int key, int direction); static rbtree* rightRotation(rbtree *p); static rbtree* leftRotation(rbtree *p); static rbtree* create_node(int key); enum {BLACK = 0, RED}; enum {LEFT = 0, RIGHT}; /* insert function */ rbtree* RedBlackTree_insert(rbtree *p, int key) { rbtree *root; root = RedBlackTree_insert_imp(p, key, LEFT); /* the color of root should always be black */ root->color = BLACK; return root; } /* lookup function */ rbtree* RedBlackTree_find(rbtree *p, int key) { while(p) { if(p->key == key) return p; else if(key < p->key) p = p->left; else p = p->right; } return NULL; } void RedBlackTree_free(rbtree *p) { if(p == NULL) return; RedBlackTree_free(p->left); RedBlackTree_free(p->right); free(p); } static rbtree* RedBlackTree_insert_imp(rbtree *p, int key, int direction) { if(p == NULL) return create_node(key); /* while moving from top to bottom, check for 4-nodes and split them*/ if(p->left != NULL && p->right != NULL) { if((p->left->color == RED) && (p->right->color == RED)) { /* split the 4-node into two 2-nodes by changing the color of left and right child from red to black. Also, convert the parent of 4-node from n-node to (n+1)-node */ p->color = RED; p->left->color = BLACK; p->right->color = BLACK; } } if(key < p->key) { /* move to left subtree */ p->left = RedBlackTree_insert_imp(p->left, key, LEFT); /* three nodes are connected by red links. the nodes orientation is n1--right--p--left-n3. rotate p right */ if(p->color == RED && p->left->color == RED && direction == RIGHT) { p = rightRotation(p); } /* three nodes are connected by red links. the nodes orientation is n1--left--p--left-n3. rotate p right */ if(p->left != NULL && p->left->left != NULL && p->left->color == RED && p->left->left->color == RED) { p = rightRotation(p); /* change the color of p to black and right child to red */ p->color = BLACK; p->right->color = RED; } } else { /* move to right subtree */ p->right = RedBlackTree_insert_imp(p->right, key, RIGHT); /* three nodes are connected by red links. the nodes orientation is n1--left--p--right-n3. rotate p left */ if(p->color == RED && p->right->color == RED && direction == LEFT) { p = leftRotation(p); } /* three nodes are connected by red links. the nodes orientation is n1--right--p--right-n3. rotate p left */ if(p->right != NULL && p->right->right != NULL && p->right->color == RED && p->right->right->color == RED) { p = leftRotation(p); /* change the color of p to black and right child to red */ p->color = BLACK; p->left->color = RED; } } return p; } static rbtree* create_node(int key) { rbtree *p; p = (rbtree*)malloc(sizeof(*p)); if(p == NULL) return NULL; p->color = RED; p->key = key; p->left = p->right = NULL; return p; } static rbtree* rightRotation(rbtree *p) { rbtree *ptr = p->left; p->left = ptr->right; ptr->right = p; return ptr; } static rbtree* leftRotation(rbtree *p) { rbtree *ptr = p->right; p->right = ptr->left; ptr->left = p; return ptr; };; runs in Chicken Scheme, however portable to most Scheme implementations that have pattern matching (most do)
(module red-black-tree
(key value color left right make-node search insert traverse-inorder
traverse-preorder traverse-postorder leaf)
(import chicken scheme matchable data-structures)
(require-library matchable utf8-srfi-13)
(define-syntax define*
(syntax-rules ()
((_ name body …) (define name (match-lambda* body …)))))
;; _ :: [string] -> string
(define ++ string-append)
;; _ :: node a b -> maybe a
(define (key n) (vector-ref n 0))
;; _ :: node a b -> maybe b
(define (value n) (vector-ref n 1))
;; _ :: node a b -> maybe symbol
(define (color n) (vector-ref n 2))
;; _ :: node a b -> maybe node a b
(define (left n) (vector-ref n 3))
(define (right n) (vector-ref n 4))
;; _ :: a -> b -> symbol -> node a b -> node a b -> node a b
(define (make-node k v c lc rc) (vector k v c lc rc))
;; _ :: node a b
(define (leaf) (make-node ‘null ‘null ‘B ‘null ‘null))
(define root leaf)
;; _ :: a -> b -> symbol -> node a b
(define (make-leaves key val color) (make-node key val color (leaf) (leaf)))
;; _ :: node a b -> boolean
(define (leaf? n) (equal? n (leaf)))
;; _ :: node a b -> a
(define* search
((T K) (search T K node a b
(define (recolor-parent n)
(make-node (key n) (value n) ‘B (left n) (right n)))
;; _ :: node a b -> a -> b -> function-symbol -> node a
(define* insert
((T K V) (insert T K V node a b
(define* balance
;; 1) red left child has red left grandchild
(#(K V ‘B #(K* V* ‘R #(K** V** ‘R L** R**) R*) R)
(make-node K* V* ‘R (make-node K** V** ‘B L** R**) (make-node K V ‘B R* R)))
;; 2) red left child has red right grandchild
(#(K V ‘B #(K* V* ‘R L* #(K** V** ‘R L** R**)) R)
(make-node K** V** ‘R (make-node K* V* ‘B L* L**) (make-node K V ‘B R** R)))
;; 3) red right child has red left grandchild
(#(K V ‘B L #(K* V* ‘R #(K** V** ‘R L** R**) R*))
(make-node K** V** ‘R (make-node K V ‘B L L**) (make-node K* V* ‘B R** R*)))
;; 4) red right child has red right grandchild
(#(K V ‘B L #(K* V* ‘R L* #(K** V** ‘R L** R**)))
(make-node K* V* ‘R (make-node K V ‘B L L*) (make-node K** V** ‘B L** R**)))
((T) T))
;; _ :: node a b -> maybe IO ()
(define (traverse-inorder t)
(if (leaf? t) “”
(let ((key* (->string (key t))) (val (->string (value t)))
(color* (->string (color t))))
(traverse-inorder (left t))
(display (++ “(” key* “,” val “,” color* “) “))
(traverse-inorder (right t)))))
(define (traverse-preorder t)
(if (leaf? t) “”
(let ((key* (->string (key t))) (val (->string (value t)))
(color* (->string (color t))))
(display (++ “(” key* “,” val “,” color* “) “))
(traverse-preorder (left t))
(traverse-preorder (right t)))))
(define (traverse-postorder t)
(if (leaf? t) “”
(let ((key* (->string (key t))) (val (->string (value t)))
(color* (->string (color t))))
(traverse-preorder (left t))
(traverse-preorder (right t))
(display (++ “(” key* “,” val “,” color* “) “)))))
;; example:
;;(define t root)
;;(define t (insert t 2 “b” <))
;;(display (++ (traverse-inorder t) "\n"))
;;(define t (insert t 5 "e" <))
;;(display (++ (traverse-inorder t) "\n"))
;;(define t (insert t 3 "c" <))
;;(display (++ (traverse-inorder t) "\n"))
;;(define t (insert t 4 "d" <))
;;(display (++ (traverse-inorder t) "\n"))
;;(define t (insert t 1 "a" <))
;;(display (++ (traverse-inorder t) "\n"))
)
sorry, it didn’t post it correctly due to formatting errors, here is a link:
http://beyert.dyndns.org/files/src/red-black-tree.scm
Here is a more permanent link, please delete my other posts:
http://codepad.org/YiMdrEem
Sorry about all of the extra posts, this one has a saved link on codepad, and the proper semi-permanent link on my webpage…
http://codepad.org/HETfVVJz
http://beyert.dyndns.org/src/red-black-tree.scm
[…] functional data structures. The example that really interested me was Okasaki’s functional Red-Black tree. The insertion and balance routines were so short and elegant that I felt I had to be able to […]