GoLLRB

module
v0.0.0-...-6e3e530 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 21, 2015 License: BSD-3-Clause

README

NOTE: This fork simply removes the example code that does not build and causes go build ... to fail.

GoLLRB

GoLLRB is a Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees in Go Language.

Overview

As of this writing and to the best of the author's knowledge, Go still does not have a balanced binary search tree (BBST) data structure. These data structures are quite useful in a variety of cases. A BBST maintains elements in sorted order under dynamic updates (inserts and deletes) and can support various order-specific queries. Furthermore, in practice one often implements other common data structures like Priority Queues, using BBST's.

2-3 trees (a type of BBST's), as well as the runtime-similar 2-3-4 trees, are the de facto standard BBST algoritms found in implementations of Python, Java, and other libraries. The LLRB method of implementing 2-3 trees is a recent improvement over the traditional implementation. The LLRB approach was discovered relatively recently (in 2008) by Robert Sedgewick of Princeton University.

GoLLRB is a Go implementation of LLRB 2-3 trees.

Maturity

GoLLRB has been used in some pretty heavy-weight machine learning tasks over many gigabytes of data. I consider it to be in stable, perhaps even production, shape. There are no known bugs.

Installation

With a healthy Go Language installed, simply run go get github.com/petar/GoLLRB/llrb

About

GoLLRB was written by Petar Maymounkov.

Follow me on Twitter @maymounkov!

Directories

Path Synopsis
A Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees, based on the following work: http://www.cs.princeton.edu/~rs/talks/LLRB/08Penn.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java 2-3 trees (and the run-time equivalent 2-3-4 trees) are the de facto standard BST algoritms found in implementations of Python, Java, and other libraries.
A Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees, based on the following work: http://www.cs.princeton.edu/~rs/talks/LLRB/08Penn.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java 2-3 trees (and the run-time equivalent 2-3-4 trees) are the de facto standard BST algoritms found in implementations of Python, Java, and other libraries.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL