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)))
}