avl

README

avl

AVL (Adelson-Velsky and Landis) immutable tree implementation.

Overview

This is an immutable implementation of the balanced binary search tree. Its goal is to be as simple as possible in terms of API as well as correct and generic.

Installation

go get github.com/gobwas/avl

Documentation

You can read the docs at GoDoc.

Usage

package main

import (
	"strings"

	"github.com/gobwas/avl"
)

func main() {
	var tree avl.Tree
	tree, _ = tree.Insert(StringItem("foo"))
	tree, _ = tree.Delete(StringItem("foo"))
	if tree.Search(StringItem("foo")) != nil {
		// whoa!
	}
}

type StringItem string

func (s StringItem) Compare(x Item) int {
	return strings.Compare(string(s), string(x.(StringItem)))
}

Documentation

Overview

Package avl implements immutable AVL (Adelson-Velsky and Landis) tree.

Immutability means that on any tree modifying operation (insert, update or delete) it does clone affected path up to the tree root. Since AVL is balanced binary tree, immutability property leads to O(log n) additional allocations.

Immutability lets applications to update the tree without holding a lock for the whole time span of operation. That is, it's possible to read the current tree "state", then update it locally and change the tree "state" in atomic way later. This technique lets other goroutines to read the tree contents without blocking while update operation is in progress:

var (
	mu   sync.RWMutex
	tree avl.Tree
)
writer := func() {
	for {
		// Read the tree state while holding read-lock, which means that
		// read-only goroutines are not blocked.
		mu.RLock()
		t := tree
		mu.RUnlock()

		// Modify the tree and update the t variable holding immutable
		// state.
		t, _ = t.Insert(x)
		t, _ = t.Delete(y)

		// Update the tree state while holding write-lock, which means that
		// read-only goroutines have to wait until we finish.
		mu.Lock()
		tree = t
		mu.Unlock()
	}
}
reader := func() {
	for {
		// Read the tree state while holding read-lock.
		mu.RLock()
		{
			// Make any read-only calls on tree such as Search() or
			// Successor() etc.
		}
		mu.RUnlock()
	}
}

go reader()
go reader()
go writer()

Note that usually there is a need to use second mutex to serialize tree updates across multiple writer goroutines.

Index

• type Item
• type Tree
  • func (t Tree) Delete(x Item) (_ Tree, existed Item)
  • func (t Tree) InOrder(fn func(Item) bool)
  • func (t Tree) Insert(x Item) (_ Tree, existing Item)
  • func (t Tree) Max() Item
  • func (t Tree) Min() Item
  • func (t Tree) PostOrder(fn func(Item) bool)
  • func (t Tree) PreOrder(fn func(Item) bool)
  • func (t Tree) Predecessor(x Item) Item
  • func (t Tree) Search(x Item) Item
  • func (t Tree) Size() int
  • func (t Tree) Successor(x Item) Item
  • func (t Tree) Update(x Item) (_ Tree, prev Item)

Examples

• Tree

Types

type Item

type Item interface {
	// Compare compares item itself with another item usually stored in a tree.
	// It reports whether the receiver is less, greater or equal to the given
	// Item by returning values less than, greater than or equal to zero
	// respectively.
	Compare(Item) int
}

Item holds a piece of information needed to be stored (or searched by) in a tree.

It's common to use different Item types for store and lookup while all of the types are consistent in comparisons:

type User struct {
	ID int
}

func (u User) Compare(x avl.Item) int {
	return u.ID - x.(User).ID
}

type ID int

func (id ID) Compare(x avl.Item) int {
	return int(id) - x.(User).ID
}

tree, _ = tree.Insert(User{ID: 42})
user := tree.Search(ID(42))

That is, Item can represent both the key for searching and value for storing (or searching).

type Tree

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

Tree is an immutable container holding root of an AVL tree. Modifying operations (Insert(), Update() and Delete()) are immutable and return copy of the tree.

Note that Tree holds pointer to the root of an AVL tree internally, which makes Tree so called reference type. That is, there is no cases when you may need to pass pointer to instance of the Tree.

Example

var tree Tree
tree, _ = tree.Insert(IntItem(1))
tree, _ = tree.Insert(IntItem(2))
tree, _ = tree.Insert(IntItem(3))
tree, _ = tree.Insert(IntItem(4))
tree, _ = tree.Delete(IntItem(4))
tree.InOrder(func(x Item) bool {
	fmt.Print(x, " ")
	return true
})

Output:

1 2 3

func (Tree) Delete

func (t Tree) Delete(x Item) (_ Tree, existed Item)

Delete deletes a node having value x from the tree. It returns a copy of the tree and a value of deleted node if such node was present.

func (Tree) InOrder

func (t Tree) InOrder(fn func(Item) bool)

InOrder prepares in-order traversal of the tree and calls fn with value of each visited node. If fn returns false it stops traversal.

func (Tree) Insert

func (t Tree) Insert(x Item) (_ Tree, existing Item)

Insert inserts a new node with value x in the tree. It returns a copy of the tree and already existing item, which non-nil value means that x was not inserted.

func (Tree) Max

func (t Tree) Max() Item

Max returns max value of the tree.

func (Tree) Min

func (t Tree) Min() Item

Min returns min value of the tree.

func (Tree) PostOrder

func (t Tree) PostOrder(fn func(Item) bool)

PostOrder prepares post-order traversal of the tree and calls fn with value of each visited node. If fn returns false it stops traversal.

func (Tree) PreOrder

func (t Tree) PreOrder(fn func(Item) bool)

PreOrder prepares pre-order traversal of the tree and calls fn with value of each visited node. If fn returns false it stops traversal.

func (Tree) Predecessor

func (t Tree) Predecessor(x Item) Item

Predecessor finds a node in the tree which is an in-order predecessor of a node having value x. It returns value of found node or nil.

func (Tree) Search

func (t Tree) Search(x Item) Item

Search searches for a node having value x and return its value. Note that x and node's value essentially can be a different types sharing comparison logic.

func (Tree) Size

func (t Tree) Size() int

Size returns the size of a tree. The time complexity is O(1).

func (Tree) Successor

func (t Tree) Successor(x Item) Item

Successor finds a node in the tree which is an in-order successor of a node having value x. It returns value of found node or nil.

func (Tree) Update

func (t Tree) Update(x Item) (_ Tree, prev Item)

Update updates a node having value x in the tree. It replaces the value of a node in the tree if it already exists or inserts new one with value x. It returns a copy of the tree and an old value if it was present and replaced by x.