README
¶
redblacktree
Usage
Default tree expects keys to be of int type.
import (
"fmt"
rbt "github.com/erriapo/redblacktree"
)
func main() {
t := rbt.NewTree()
t.Put(7, "payload7")
t.Put(3, "payload3")
t.Put(1, "payload1")
fmt.Printf("size = %d\n", t.Size()) // size = 3
inorder := &rbt.InorderVisitor{}; t.Walk(inorder)
fmt.Printf("tree = %s\n", inorder) // tree = ((.1.)3(.7.))
if ok, payload := t.Get(3); ok {
fmt.Printf("%d is mapped to %s\n", 3, payload.(string))
}
fmt.Printf("t.Has(1) = %t\n", t.Has(1)) // true
t.Delete(1)
fmt.Printf("t.Has(1) = %t\n", t.Has(1)) // false
}
Example of a tree with custom keys
type Key struct {
Path, Country string
}
func KeyComparator(o1, o2 interface{}) int {
k1 := o1.(Key); k2 := o2.(Key)
return rbt.StringComparator(k1.Path + k1.Country, k2.Path + k2.Country)
}
func main() {
tree := rbt.NewTreeWith(KeyComparator)
kAU, kNZ := Key{"/", "au"}, Key{"/tmp", "nz"}
tree.Put(kAU, 999)
if ok, payload := tree.Get(kAU); ok {
fmt.Printf("%#v is mapped to %#v\n", kAU, payload)
// main.Key{Path:"/", Country:"au"} is mapped to 999
}
tree.Put(kNZ, 666)
fmt.Printf("size = %d\n", tree.Size()) // size = 2
}
License
- Code is released under Apache license. See LICENSE file.
Documentation
¶
Overview ¶
Package redblacktree provides a pure Golang implementation of a red-black tree as described by Thomas H. Cormen's et al. in their seminal Algorithms book (3rd ed). This data structure is not multi-goroutine safe.
Index ¶
- Constants
- Variables
- func IntComparator(o1, o2 interface{}) int
- func SetOutput(w io.Writer)
- func StringComparator(o1, o2 interface{}) int
- func TraceOff()
- func TraceOn()
- type Color
- type Comparator
- type Direction
- type InorderVisitor
- type Node
- type Tree
- func (t *Tree) Delete(key interface{})
- func (t *Tree) Get(key interface{}) (bool, interface{})
- func (t *Tree) GetParent(key interface{}) (found bool, parent *Node, dir Direction)
- func (t *Tree) Has(key interface{}) bool
- func (t *Tree) Put(key interface{}, data interface{}) error
- func (t *Tree) RotateLeft(x *Node)
- func (t *Tree) RotateRight(y *Node)
- func (t *Tree) Size() uint64
- func (t *Tree) Walk(visitor Visitor)
- type Visitable
- type Visitor
Constants ¶
Variables ¶
var ( ErrorKeyIsNil = errors.New("The literal nil not allowed as keys") ErrorKeyDisallowed = errors.New("Disallowed key type") )
Functions ¶
func IntComparator ¶
func IntComparator(o1, o2 interface{}) int
Default comparator expects keys to be of type `int`. Warning: if either one of `o1` or `o2` cannot be asserted to `int`, it panics.
func StringComparator ¶
func StringComparator(o1, o2 interface{}) int
Keys of type `string`. Warning: if either one of `o1` or `o2` cannot be asserted to `string`, it panics.
Types ¶
type Comparator ¶
type Comparator func(o1, o2 interface{}) int
Keys must be comparable. It's mandatory to provide a Comparator, which returns zero if o1 == o2, -1 if o1 < o2, 1 if o1 > o2
type InorderVisitor ¶
type InorderVisitor struct {
// contains filtered or unexported fields
}
InorderVisitor walks the tree in inorder fashion. This visitor maintains internal state; thus do not reuse after the completion of a walk.
func (*InorderVisitor) Eq ¶
func (v *InorderVisitor) Eq(other *InorderVisitor) bool
func (*InorderVisitor) String ¶
func (v *InorderVisitor) String() string
func (*InorderVisitor) Visit ¶
func (v *InorderVisitor) Visit(node *Node)
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
A node needs to be able to answer the query: (i) Who is my parent node ? (ii) Who is my grandparent node ? The zero value for Node has color Red.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree encapsulates the data structure.
func NewTree ¶
func NewTree() *Tree
NewTree returns an empty Tree with default comparator `IntComparator`. `IntComparator` expects keys to be type-assertable to `int`.
func NewTreeWith ¶
func NewTreeWith(c Comparator) *Tree
NewTreeWith returns an empty Tree with a supplied `Comparator`.
func (*Tree) Delete ¶
func (t *Tree) Delete(key interface{})
Delete removes the item identified by the supplied key. Delete is a noop if the supplied key doesn't exist.
func (*Tree) Get ¶
Get looks for the node with supplied key and returns its mapped payload. Return value in 1st position indicates whether any payload was found.
func (*Tree) GetParent ¶
GetParent looks for the node with supplied key and returns the parent node.
func (*Tree) Put ¶
Put saves the mapping (key, data) into the tree. If a mapping identified by `key` already exists, it is overwritten. Constraint: Not everything can be a key.
func (*Tree) RotateLeft ¶
Side-effect: red-black tree properties is maintained.
Source Files
Directories