rbtree

package
v1.4.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 22, 2024 License: MIT Imports: 0 Imported by: 0

Documentation

Overview

Package rbtree provides Red-black search binary tree implementation that supports ordered statistic

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func GetInt 

func GetInt(c Comparable) int

GetInt gets int value from Comparable

func GetInt64 added in v0.7.0 

func GetInt64(c Comparable) int64

GetInt64 gets int64 value from Comparable

Types

type Comparable 

type Comparable interface {
	// Less gets whether value specified less then current value
	Less(y Comparable) bool

	// Equal gets whether value specified equal current value
	Equal(y Comparable) bool
}

Comparable defines comparable type interface

func NewString 

func NewString(v string) Comparable

NewString creates new string Comparable implementation

type Enumerable added in v0.9.0 

type Enumerable interface {
	// Iterator gets underlying Iterator
	Iterator() Iterator

	// Foreach enumerates tree and calls the callback for
	// every value in the tree until callback returns false.
	Foreach(callback NodeAction)
}

Enumerable represents tree enumeration interface

func NewAscend added in v0.5.0 

func NewAscend(t RbTree) Enumerable

NewAscend creates Enumerable that walks tree in ascending order

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewAscend(tree)

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

3
6
18

func NewAscendRange added in v0.5.0 

func NewAscendRange(t RbTree, from, to Comparable) Enumerable

NewAscendRange creates Enumerable that walks tree in ascending order within the range [from, to]

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewAscendRange(tree, Int(3), Int(6))

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

3
6

func NewDescend added in v0.5.0 

func NewDescend(t RbTree) Enumerable

NewDescend creates Enumerable that walks tree in descending order

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewDescend(tree)

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

18
6
3

func NewDescendRange added in v0.5.0 

func NewDescendRange(t RbTree, from, to Comparable) Enumerable

NewDescendRange that walks tree in descending order within the range [from, to]

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewDescendRange(tree, Int(6), Int(3))

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

6
3

func NewOpenAscendRange added in v1.1.0 

func NewOpenAscendRange(t RbTree, from, to Comparable) Enumerable

NewOpenAscendRange creates Enumerable that walks tree in ascending order within the range (from, to]) open means that both ends not necessary present in the tree. If not the nearest tree nodes will be found and iteration starts and stops using them

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewOpenAscendRange(tree, Int(2), Int(10))

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

3
6

func NewOpenDescendRange added in v1.1.0 

func NewOpenDescendRange(t RbTree, from, to Comparable) Enumerable

NewOpenDescendRange that walks tree in descending order within the range (from, to) open means that both ends not necessary present in the tree. If not the nearest tree nodes will be found and iteration starts and stops using them

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewOpenDescendRange(tree, Int(20), Int(5))

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

18
6

func NewWalkInorder added in v0.5.0 

func NewWalkInorder(t RbTree) Enumerable

NewWalkInorder creates Enumerable that walks tree inorder (left, node, right)

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewWalkInorder(tree)

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

3
6
18

func NewWalkPostorder added in v0.5.0 

func NewWalkPostorder(t RbTree) Enumerable

NewWalkPostorder creates Enumerable that walks tree postorder (left, right, node)

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewWalkPostorder(tree)

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

3
18
6

func NewWalkPreorder added in v0.5.0 

func NewWalkPreorder(t RbTree) Enumerable

NewWalkPreorder creates Enumerable that walks tree preorder (node, left, right)

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

it := NewWalkPreorder(tree)

it.Foreach(func(n Comparable) {
	fmt.Println(n)
})

Output:

6
3
18

type Int 

type Int int

Int is the int type key that can be stored as Node's key

func (Int) Equal added in v0.11.0 

func (x Int) Equal(y Comparable) bool

Equal define Comparable interface member for Int

func (Int) Less added in v0.11.0 

func (x Int) Less(y Comparable) bool

Less define Comparable interface member for Int

type Int64 added in v0.7.0 

type Int64 int64

Int64 is the int64 type key that can be stored as Node's key

func (Int64) Equal added in v0.11.0 

func (x Int64) Equal(y Comparable) bool

Equal define Comparable interface member for Int64

func (Int64) Less added in v0.11.0 

func (x Int64) Less(y Comparable) bool

Less define Comparable interface member for Int64

type Iterator added in v0.5.0 

type Iterator interface {
	// Current gets current Node
	Current() Comparable

	// Next advances the iterator and returns whether
	// the next call to the item method will return a
	// non-nil item.
	//
	// Next should be called prior to any call to the
	// iterator's item retrieval method after the
	// iterator has been obtained
	//
	// The order of iteration is implementation
	// dependent.
	Next() bool
}

Iterator is an node iterator.

type Node 

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

Node represent red-black tree node

func (*Node) Key 

func (n *Node) Key() Comparable

Key gets Node's key

func (*Node) Predecessor 

func (n *Node) Predecessor() *Node

Predecessor gets Node's predecessor

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

root := tree.Root()

n := root.Predecessor()
fmt.Println(n.Key())

Output:

3

func (*Node) Size 

func (n *Node) Size() int64

Size gets subtree size including node itself

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

root := tree.Root()

size := root.Size()
fmt.Println(size)

Output:

3

func (*Node) Successor 

func (n *Node) Successor() *Node

Successor gets Node's successor

Example 
tree := New()

tree.Insert(Int(6))
tree.Insert(Int(18))
tree.Insert(Int(3))

root := tree.Root()

n := root.Successor()
fmt.Println(n.Key())

Output:

18

type NodeAction added in v0.9.0 

type NodeAction func(Comparable)

NodeAction defines function prototype that used by an iteration method to iterate over portions of the tree.

type RbTree 

type RbTree interface {
	// Len returns the number of nodes in the tree.
	Len() int64

	// Insert inserts new Node into Red-Black tree. Creates Root if tree is empty
	Insert(n Comparable)

	// ReplaceOrInsert inserts new Node into Red-Black tree. Creates Root if tree is empty
	// If an item in the tree
	// already equals the given one, it is removed from the tree and returned.
	// Otherwise, nil is returned.
	ReplaceOrInsert(n Comparable) Comparable

	// Delete searches and deletes Node with key value specified from Red-black tree
	// It returns true if Node was successfully deleted otherwise false
	Delete(c Comparable) bool

	// DeleteAll searches and deletes all found nodes with key value specified from Red-black tree
	// It returns true if nodes was successfully deleted otherwise false
	DeleteAll(c Comparable) bool

	// Search searches value specified within search tree
	Search(value Comparable) (Comparable, bool)

	// Floor searches value with the greatest data lesser than or equal to key value.
	Floor(value Comparable) (Comparable, bool)

	// Ceiling searches value with the smallest data larger than or equal to key value.
	Ceiling(value Comparable) (Comparable, bool)

	// SearchAll searches all values with the same key as specified within search tree
	SearchAll(value Comparable) []Comparable

	// SearchNode searches *Node which key is equals value specified
	SearchNode(value Comparable) (*Node, bool)

	// Minimum gets tree's min element
	Minimum() *Node

	// Maximum gets tree's max element
	Maximum() *Node

	// OrderStatisticSelect gets i element from subtree
	// IMPORTANT: numeration starts from 1 not from 0
	OrderStatisticSelect(i int64) (*Node, bool)

	// Root gets tree root Node
	Root() *Node
}

RbTree represents red-black tree interface

func New added in v0.11.0 

func New() RbTree

New creates new empty Red-Black tree

Example 
tree := New()
node := NewString("a")
tree.Insert(node)

size := tree.Len()
fmt.Println(size)

n, ok := tree.Search(node)
fmt.Println(n)
fmt.Println(ok)

n, ok = tree.Search(NewString("b"))
fmt.Println(n)
fmt.Println(ok)

Output:

1
a
true
<nil>
false

type String 

type String string

String is the string type key that can be stored as Node's key

func (*String) Equal added in v0.11.0 

func (x *String) Equal(y Comparable) bool

Equal define Comparable interface member for String

func (*String) Less added in v0.11.0 

func (x *String) Less(y Comparable) bool

Less define Comparable interface member for String

func (*String) String 

func (x *String) String() string

Source Files

View all Source files

Directories

Path Synopsis
Package special provides specialized Red-black search binary tree implementations
 Package special provides specialized Red-black search binary tree implementations

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.