README
¶
Rbtree 
This is an implementation of Red-Black tree written by Golang.
Installation
With a healthy Go language installed, simply run go get github.com/HuKeping/rbtree
Example
All you have to do is implement a comparison function Less() bool for your Item
which will be store in the Red-Black tree, here are some examples.
A simple case for int items.
package main
import (
"fmt"
"github.com/HuKeping/rbtree"
)
func main() {
rbt := rbtree.New()
m := 0
n := 10
for m < n {
rbt.Insert(rbtree.Int(m))
m++
}
m = 0
for m < n {
if m%2 == 0 {
rbt.Delete(rbtree.Int(m))
}
m++
}
// 1, 3, 5, 7, 9 were expected.
rbt.Ascend(rbt.Min(), Print)
}
func Print(item rbtree.Item) bool {
i, ok := item.(rbtree.Int)
if !ok {
return false
}
fmt.Println(i)
return true
}
A simple case for string items.
package main
import (
"fmt"
"github.com/HuKeping/rbtree"
)
func main() {
rbt := rbtree.New()
rbt.Insert(rbtree.String("Hello"))
rbt.Insert(rbtree.String("World"))
rbt.Ascend(rbt.Min(), Print)
}
func Print(item rbtree.Item) bool {
i, ok := item.(rbtree.String)
if !ok {
return false
}
fmt.Println(i)
return true
}
A quite interesting case for struct items.
package main
import (
"fmt"
"github.com/HuKeping/rbtree"
"time"
)
type Var struct {
Expiry time.Time `json:"expiry,omitempty"`
ID string `json:"id",omitempty`
}
// We will order the node by `Time`
func (x Var) Less(than rbtree.Item) bool {
return x.Expiry.Before(than.(Var).Expiry)
}
func main() {
rbt := rbtree.New()
var1 := Var{
Expiry: time.Now().Add(time.Second * 10),
ID: "var1",
}
var2 := Var{
Expiry: time.Now().Add(time.Second * 20),
ID: "var2",
}
var3 := Var{
Expiry: var2.Expiry,
ID: "var2-dup",
}
var4 := Var{
Expiry: time.Now().Add(time.Second * 40),
ID: "var4",
}
var5 := Var{
Expiry: time.Now().Add(time.Second * 50),
ID: "var5",
}
rbt.Insert(var1)
rbt.Insert(var2)
rbt.Insert(var3)
rbt.Insert(var4)
rbt.Insert(var5)
tmp := Var{
Expiry: var4.Expiry,
ID: "This field is not the key factor",
}
// var4 and var5 were expected
rbt.Ascend(rbt.Get(tmp), Print)
}
func Print(item rbtree.Item) bool {
i, ok := item.(Var)
if !ok {
return false
}
fmt.Printf("%+v\n", i)
return true
}
Documentation
¶
Overview ¶
Package rbtree implements operations on Red-Black tree.
Index ¶
- Constants
- type Int
- type Item
- type Iterator
- type Node
- type Rbtree
- func (t *Rbtree) Ascend(pivot Item, iterator Iterator)
- func (t *Rbtree) AscendRange(ge, lt Item, iterator Iterator)
- func (t *Rbtree) Delete(item Item) Item
- func (t *Rbtree) Descend(pivot Item, iterator Iterator)
- func (t *Rbtree) First() *Node
- func (t *Rbtree) Get(item Item) Item
- func (t *Rbtree) Init() *Rbtree
- func (t *Rbtree) Insert(item Item) *Node
- func (t *Rbtree) InsertOrGet(item Item) Item
- func (t *Rbtree) Len() uint
- func (t *Rbtree) Max() Item
- func (t *Rbtree) Min() Item
- func (t *Rbtree) Next(x *Node) *Node
- func (t *Rbtree) Prev(x *Node) *Node
- func (t *Rbtree) Search(item Item) *Node
- func (t *Rbtree) SearchLe(item Item) *Node
- func (t *Rbtree) Tail() *Node
- type String
- type Uint32
Constants ¶
const ( RED = true BLACK = false )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
Red-Black tree properties: http://en.wikipedia.org/wiki/Rbtree
- A node is either red or black
- The root is black
- All leaves (NULL) are black
- Both children of every red node are black
- Every simple path from root to leaves contains the same number of black nodes.
type Rbtree ¶
type Rbtree struct {
NIL *Node
// contains filtered or unexported fields
}
Rbtree represents a Red-Black tree.
func (*Rbtree) Ascend ¶
Ascend will call iterator once for each element greater or equal than pivot in ascending order. It will stop whenever the iterator returns false.
func (*Rbtree) AscendRange ¶
AscendRange will call iterator once for elements greater or equal than @ge and less than @lt, which means the range would be [ge, lt). It will stop whenever the iterator returns false.
func (*Rbtree) Descend ¶
Descend will call iterator once for each element less or equal than pivot in descending order. It will stop whenever the iterator returns false.
func (*Rbtree) InsertOrGet ¶
InsertOrGet inserts or retrieves the item in the tree. If the item is already in the tree then the return value will be that. If the item is not in the tree the return value will be the item you put in.
Source Files
Directories