tree

README

tree

In-memory Red-Black Tree implementation in Go.

Red-black trees are a self-balancing binary search tree that allow for O(log(n)) search, insertion, and deletion. To learn more, you can check out the Wikipedia page.

This library purposely maintains a similiar interface to the excellent btree implementation by Google:

https://github.com/google/btree

Which, in turn, was inspired by the great:

https://github.com/petar/GoLLRB

Usage

The zero value of a RedBlackTree is a ready to use empty tree.

import "github.com/ryanfowler/tree"

var rb tree.RedBlackTree

Items

Items put into the tree must implement the Item interface, which consists on a single method, Less(Item) bool. Two Items 'a' & 'b' are considered equal if:

equal := !a.Less(b) && !b.Less(a)

Convenience types that implement the Item interface are:

• Int
• String
• Bytes

However, most of the time you'll want to use a custom type.

Inserting

Items can be inserted or replaced in a RedBlackTree using Upsert. Upsert will return the Item that was replaced by the Upsert. If there was no matching Item in the tree, nil is returned.

var rb tree.RedBlackTree

item := rb.Upsert(tree.Int(10))
fmt.Println(item)
// Will print: <nil>

item = rb.Upsert(tree.Int(10))
fmt.Println(item)
// Will print: 10

Retrieving

An Item can be retrieved from a RedBlackTree using the following methods:

• Get(item Item) Item - returns an Item in the tree equal to the provided Item, or nil if there is no matching Item.
• Max() Item - returns the largest Item in the tree, or nil if the tree is empty.
• Min() Item - returns the smallest Item in the tree, or nil if the tree is empty.

var rb tree.RedBlackTree

rb.Upsert(tree.Int(4))
rb.Upsert(tree.Int(5))
rb.Upsert(tree.Int(6))

item := rb.Get(tree.Int(5))
fmt.Println(item)
// Will print: 5

item = rb.Get(tree.Int(8))
fmt.Println(item)
// Will print: <nil>

item = rb.Max()
fmt.Println(item)
// Will print: 6

item = rb.Min()
fmt.Println(item)
// Will print: 4

Deleting

An Item can be removed from a RedBlackTree using the following methods:

• Delete(item Item) Item - removes an Item in the tree equal to the provided Item, returning it. If there is no matching Item, nil is returned.
• DeleteMax() Item - deletes and returns the largest Item in the tree, or nil if the tree is empty.
• DeleteMin() Item - deletes and returns the smallest Item in the tree, or nil if the tree is empty.

var rb tree.RedBlackTree

rb.Upsert(tree.Int(4))
rb.Upsert(tree.Int(5))
rb.Upsert(tree.Int(6))

fmt.Println(rb.Size())
// Will print: 3

item := rb.Delete(tree.Int(5))
fmt.Println(item)
// Will print: 5
fmt.Println(rb.Size())
// Will print: 2

item = rb.Delete(tree.Int(8))
fmt.Println(item)
// Will print: <nil>
fmt.Println(rb.Size())
// Will print: 2

item = rb.DeleteMax()
fmt.Println(item)
// Will print: 6
fmt.Println(rb.Size())
// Will print: 1

item = rb.Min()
fmt.Println(item)
// Will print: 4
fmt.Println(rb.Size())
// Will print: 0

Example

Currently, a RedBlackTree does not allow for the storing of equal items. This can be worked around by including a second, unique field in the type's Less method.

For example, suppose you were designing a game and had a collection of users with their highest scores. If you wanted to retrieve the user(s) with the highest score, it could look something like this:

import (
	"fmt"

	"github.com/ryanfowler/tree"
)

type User struct {
	ID    int
	Score int
}

func (u *User) Less(than tree.Item) bool {
	thanUser := than.(*User)
	return u.Score < thanUser.Score || (u.Score == thanUser.Score && u.ID < thanUser.ID)
}

func main() {
	var rb tree.RedBlackTree

	// Create users.
	u1 := &User{ID: 1, Score: 10}
	u2 := &User{ID: 2, Score: 7}
	u3 := &User{ID: 3, Score: 12}
	u4 := &User{ID: 4, Score: 10}

	// Insert into the RedBlackTree.
	rb.Upsert(u1)
	rb.Upsert(u2)
	rb.Upsert(u3)
	rb.Upsert(u4)

	// Get the user with the highest score.
	item := rb.Max()
	if item == nil {
		// The tree is empty.
		return
	}
	maxItem := item.(*User)
	fmt.Printf("%+v\n", maxItem)
	// Will print:
	// &{ID: 3, Score: 12}

	// Insert another user with a matching high score.
	u5 := &User{ID: 5, Score: 12}
	rb.Upsert(u5)

	// Get all users with the highest score.
	var maxScore int
	var maxUsers []*User
	rb.Descend(func(item tree.Item) bool {
		user := item.(*User)
		if len(maxUsers) == 0 {
			maxScore = user.Score
			maxUsers = append(maxUsers, user)
			return true
		}
		if user.Score < maxScore {
			return false
		}
		maxUsers = append(maxUsers, user)
		return true
	})
	for _, user := range maxUsers {
		fmt.Printf("%+v\n", user)
	}
	// Will print:
	// &{ID: 5, Score: 12}
	// &{ID: 3, Score: 12}
}

License

MIT License

Copyright (c) 2017 Ryan Fowler

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

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 OR COPYRIGHT HOLDERS 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.

Documentation

Overview

Package tree provides an implementation of a red-black tree.

Index

• type Bytes
  • func (b Bytes) Less(than Item) bool
• type Int
  • func (i Int) Less(than Item) bool
• type Item
• type RedBlackTree
  • func (t *RedBlackTree) Ascend(fn func(Item) bool)
  • func (t *RedBlackTree) AscendGreaterOrEqual(than Item, fn func(Item) bool)
  • func (t *RedBlackTree) AscendLess(thanItem Item, fn func(Item) bool)
  • func (t *RedBlackTree) AscendRange(greaterOrEqual, lessThan Item, fn func(Item) bool)
  • func (t *RedBlackTree) Delete(item Item) Item
  • func (t *RedBlackTree) DeleteMax() Item
  • func (t *RedBlackTree) DeleteMin() Item
  • func (t *RedBlackTree) Descend(fn func(Item) bool)
  • func (t *RedBlackTree) Exists(item Item) bool
  • func (t *RedBlackTree) Get(item Item) Item
  • func (t *RedBlackTree) Max() Item
  • func (t *RedBlackTree) Min() Item
  • func (t *RedBlackTree) Size() int
  • func (t *RedBlackTree) Upsert(item Item) Item
• type String
  • func (s String) Less(than Item) bool

Types

type Bytes

type Bytes []byte

Bytes represents a slice of bytes that implements the Item interface.

func (Bytes) Less

func (b Bytes) Less(than Item) bool

Less returns true if the Bytes are less than the provided Bytes. If the provided Item is not of type Bytes, Less will panic.

type Int

type Int int

Int represents an integer that implements the Item interface.

func (Int) Less

func (i Int) Less(than Item) bool

Less returns true if the Int is less than the provided Int. If the provided Item is not an Int, Less will panic.

type Item

type Item interface {
	Less(Item) bool
}

Item is the interface that wraps the Less method.

Less should return 'true' if the instance is "less than" the provided Item. Items are considered equal if neither are less than each other. E.g. Items 'a' & 'b' are considered equal if: (!a.Less(b) && !b.Less(a))

type RedBlackTree

type RedBlackTree struct {
	// contains filtered or unexported fields
}

RedBlackTree is an in-memory implementation of a red-black tree.

The internal data structure will automatically re-balance, and therefore allow for O(log(n)) retrieval, insertion, and deletion.

Note: While read-only operations may occur concurrently, any write operation must be serially executed (typically protected with a mutex).

func (*RedBlackTree) Ascend

func (t *RedBlackTree) Ascend(fn func(Item) bool)

Ascend starts at the first Item and calls 'fn' for each Item until no Items remain or fn returns 'false'.

O(log(n) + m) where n is the total number of items in the tree and m is the number of items ranged over.

func (*RedBlackTree) AscendGreaterOrEqual

func (t *RedBlackTree) AscendGreaterOrEqual(than Item, fn func(Item) bool)

AscendGreaterOrEqual starts at the first Item greater or equal to the provided Item and calls 'fn' for each Item until no Items remain in the tree or fn returns 'false'.

O(log(n) + m) where n is the total number of items in the tree and m is the number of items ranged over.

func (*RedBlackTree) AscendLess

func (t *RedBlackTree) AscendLess(thanItem Item, fn func(Item) bool)

AscendLess starts at the first Item and calls 'fn' for each Item less than the provided Item or when fn returns 'false'.

O(log(n) + m) where n is the total number of items in the tree and m is the number of items ranged over.

func (*RedBlackTree) AscendRange

func (t *RedBlackTree) AscendRange(greaterOrEqual, lessThan Item, fn func(Item) bool)

AscendRange starts at the first Item greater or equal to 'greaterOrEqual' and calls 'fn' for each Item less than 'lessThan' or when fn returns 'false'.

O(log(n) + m) where n is the total number of items in the tree and m is the number of items ranged over.

func (*RedBlackTree) Delete

func (t *RedBlackTree) Delete(item Item) Item

Delete deletes an item in the RedBlackTree equal to the provided item. If an item was deleted, it is returned. Otherwise, nil is returned.

Note: equality for items a & b is: (!a.Less(b) && !b.Less(a)).

O(log(n))

func (*RedBlackTree) DeleteMax

func (t *RedBlackTree) DeleteMax() Item

DeleteMax deletes the maximum item in the RedBlackTree, returning it. If the tree is empty, nil is returned.

O(log(n))

func (*RedBlackTree) DeleteMin

func (t *RedBlackTree) DeleteMin() Item

DeleteMin deletes the minimum item in the RedBlackTree, returning it. If the tree is empty, nil is returned.

O(log(n))

func (*RedBlackTree) Descend

func (t *RedBlackTree) Descend(fn func(Item) bool)

Descend starts at the last Item and calls 'fn' for each Item until no Items remain or fn returns 'false'.

O(log(n) + m) where n is the total number of items in the tree and m is the number of items ranged over.

func (*RedBlackTree) Exists

func (t *RedBlackTree) Exists(item Item) bool

Exists returns 'true' if an item equal to the provided item exists in the RedBlackTree.

Note: equality for items a & b is: (!a.Less(b) && !b.Less(a)).

O(log(n))

func (*RedBlackTree) Get

func (t *RedBlackTree) Get(item Item) Item

Get retrieves an item in the RedBlackTree equal to the provided item. If an item was found, it is returned. Otherwise, nil is returned.

Note: equality for items a & b is: (!a.Less(b) && !b.Less(a)).

O(log(n))

func (*RedBlackTree) Max

func (t *RedBlackTree) Max() Item

Max returns the maximum item in the RedBlackTree. If the tree is empty, nil is returned.

O(log(n))

func (*RedBlackTree) Min

func (t *RedBlackTree) Min() Item

Min returns the minimum item in the RedBlackTree. If the tree is empty, nil is returned.

O(log(n))

func (*RedBlackTree) Size

func (t *RedBlackTree) Size() int

Size returns the number of items in the RedBlackTree.

O(1)

func (*RedBlackTree) Upsert

func (t *RedBlackTree) Upsert(item Item) Item

Upsert inserts (or replaces) an item into the RedBlackTree. If an item was replaced, it is returned. Otherwise, nil is returned.

Note: equality for items a & b is: (!a.Less(b) && !b.Less(a)).

O(log(n))

type String

type String string

String represents a string that implements the Item interface.

func (String) Less

func (s String) Less(than Item) bool

Less returns true if the String is less than the provided String. If the provided Item is not a String, Less will panic.