A base implementation of Robert Sedgewick's Left-Leaning Red-Black Tree (LLRB), written in Go (GOLANG). LLRB Trees are a variant of red-black trees with the aim of reducing the complexity of Insert and Delete functionality. They are self-balancing, maintaining the balance characteristics of a 2-3 tree, while retaining the Get(Key) performance of…

llrb.go

/*

package llrb implements a Left-Leaning Red-Black Tree (2-3 Variant),
as described by Robert Sedgewick:

	* http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

	* http://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree

The goal of this implementation is a one-to-one correlation to the ideas
and code mentioned in Sedgewick's PDF, with a couple of noted exceptions:

	* Several null (nil) checks were added to avoid segfaulting

	* In Delete, we re-compare the keys after modifying the tree

NOTE: Although RS claims that the presented Delete strategy works for both
      2-3 and 2-3-4 trees, a cursory experiment suggests that it does not
      work for 2-3-4 trees.  Thus this implementation is only focused on
      the 2-3 variant.

This file represents the version of the code that first passed all of my tests.

Before moving onto trying to find optimizations or adding functionality, I
thought I would release this version of the code for others who might be
interested in playing with a base implementation.

Since this implementation did pass all of my tests, I assume it to be a
correctly-functioning LLRB.  If you find out otherwise, please let me know.

Author:
-------
	David Farrell <[email protected]>
	https://github.com/iNamik

License:
--------
This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to http://unlicense.org

*/
package llrb

/*********************************************************************
 ** Comparator - Adapted to make this file self-contained
 **              Comparators provided for int and string
 *********************************************************************/

// Compare Constants
const (
	CMP_EQUAL   = 0
	CMP_LESS    = -1
	CMP_GREATER = 1
)

type Key interface {
	CompareTo(k Key) int
}

type Int int

func (a Int) CompareTo(b_ Key) int {
	b := b_.(Int)
	switch {
	case a < b:
		return CMP_LESS
	case a > b:
		return CMP_GREATER
	default:
		return CMP_EQUAL
	}
	//panic("Unreachable")
}

type String string

func (a String) CompareTo(b_ Key) int {
	b := b_.(String)
	switch {
	case a < b:
		return CMP_LESS
	case a > b:
		return CMP_GREATER
	default:
		return CMP_EQUAL
	}
	//panic("Unreachable")
}

/*********************************************************************
 ** LLRB - Everything below this is the LLRB implementation
 *********************************************************************/

// Tree interface
type Tree interface {
	// Insert inserts a key into the tree, replacing an existing entry (Associative)
	Insert(key Key, value interface{})
	// Get returns (value,true) if the key was found, else (nil,false)
	Get(key Key) (value interface{}, found bool)
	// Delete removes a key/value from the tree
	Delete(key Key)
}

type node struct {
	key   Key
	value interface{}
	left  *node
	right *node
	red   bool
}

type tree struct {
	root *node
}

func New() Tree {
	return &tree{root: nil}
}

func (t *tree) Insert(key Key, value interface{}) {
	t.root = insert(t.root, key, value)
	t.root.red = false
}

func (t *tree) Get(key Key) (interface{}, bool) {
	h := get(t.root, key)
	if h != nil {
		return h.value, true
	}
	return nil, false
}

func (t *tree) Delete(key Key) {
	t.root = deleteNode(t.root, key)
	// RS did not check to see if root existed before coloring it
	if t.root != nil {
		t.root.red = false
	}
}

func insert(h *node, key Key, value interface{}) *node {
	if h == nil {
		return &node{key: key, value: value, red: true}
	}
	switch key.CompareTo(h.key) {
	case CMP_LESS:
		h.left = insert(h.left, key, value)
	case CMP_GREATER:
		h.right = insert(h.right, key, value)
	default:
		h.value = value
		return h
	}
	return fixUp(h)
}

func get(h *node, key Key) *node {
	for h != nil {
		switch key.CompareTo(h.key) {
		case CMP_LESS:
			h = h.left
		case CMP_GREATER:
			h = h.right
		default:
			return h
		}
	}
	return nil
}

func deleteNode(h *node, key Key) *node {
	if h == nil {
		return nil
	}
	c := key.CompareTo(h.key)
	if c == CMP_LESS {
		// RS forgot to ensure left exists before left.left check
		if h.left != nil && !isRed(h.left) && !isRed(h.left.left) {
			h = moveRedLeft(h)
		}
		h.left = deleteNode(h.left, key)
	} else {
		if isRed(h.left) {
			h = rotateRight(h)
			// RS forgot to re-compare here
			c = key.CompareTo(h.key)
		}
		if c == CMP_EQUAL && h.right == nil {
			return nil
		}
		// RS forgot to ensure right exists before right.left check
		if h.right != nil && !isRed(h.right) && !isRed(h.right.left) {
			h = moveRedRight(h)
			// RS forgot to re-compare here
			c = key.CompareTo(h.key)
		}
		if c == CMP_EQUAL {
			h.key = min(h.right).key
			h.value = get(h.right, h.key)
			h.right = deleteMin(h.right)
		} else {
			h.right = deleteNode(h.right, key)
		}
	}
	return fixUp(h)
}

func min(h *node) *node {
	if h != nil {
		for h.left != nil {
			h = h.left
		}
	}
	return h
}

func deleteMin(h *node) *node {
	if h.left == nil {
		return nil
	}
	if !isRed(h.left) && !isRed(h.left.left) {
		h = moveRedLeft(h)
	}
	h.left = deleteMin(h.left)
	return fixUp(h)
}

func isRed(h *node) bool {
	return h != nil && h.red
}

func colorFlip(h *node) {
	h.red = !h.red
	h.left.red = !h.left.red
	h.right.red = !h.right.red
}

func rotateLeft(h *node) *node {
	x := h.right
	h.right = x.left
	x.left = h
	x.red = h.red
	h.red = true
	return x
}

func rotateRight(h *node) *node {
	x := h.left
	h.left = x.right
	x.right = h
	x.red = h.red
	h.red = true
	return x
}

func moveRedLeft(h *node) *node {
	colorFlip(h)
	if isRed(h.right.left) {
		h.right = rotateRight(h.right)
		h = rotateLeft(h)
		colorFlip(h)
	}
	return h
}

func moveRedRight(h *node) *node {
	colorFlip(h)
	if isRed(h.left.left) {
		h = rotateRight(h)
		colorFlip(h)
	}
	return h
}

func fixUp(h *node) *node {
	if h == nil {
		return nil
	}
	if isRed(h.right) {
		h = rotateLeft(h)
	}
	if isRed(h.left) && isRed(h.left.left) {
		h = rotateRight(h)
	}
	if isRed(h.left) && isRed(h.right) {
		colorFlip(h)
	}
	return h
}

This is exactly what I needed. Thanks!