Documentation
¶
Overview ¶
Package avl implements an easy-to-use AVL tree in Golang.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DebugPreorder ¶
func DebugPreorder(t *Tree) (ret []interface{})
DebugPreorder will traverse the tree in preorder. For debug-use only.
Types ¶
type BytesTree ¶
type BytesTree Tree
BytesTree is a high-performance AVL tree for []byte.
type ITree ¶ added in v0.2.0
ITree is an AVL tree implement with type parameters support.
func NewOrderedTree ¶ added in v0.2.0
func NewOrderedTree[T constraints.Ordered]() ITree[T]
NewOrderedTree creates a new high-performance AVL tree instance for ordered types, such as integer, float, and string.
Example (Int) ¶
package main
import (
"fmt"
"github.com/sym01/algo/avl"
)
func main() {
ints := []int{
9, 85, 45, 76, 53, 52, 66, 12, 13, 65,
98, 33, 28, 42, 38, 84, 24, 37, 36, 35,
27, 41, 77, 48, 46, 81, 78, 60, 25, 5,
3, 93, 11, 49, 74, 96, 94, 39, 51, 95,
58, 90, 91, 20, 7, 44, 97, 29, 2, 8,
19, 14, 86, 61, 54, 79, 64, 16, 67, 6,
26, 73, 50, 72, 10, 83, 70, 80, 89, 15,
17, 4, 100, 71, 55, 75, 69, 87, 34, 92,
43, 18, 88, 82, 30, 57, 23, 99, 59, 21,
32, 22, 68, 56, 47, 40, 63, 62, 1, 31,
}
tree := avl.NewOrderedTree[int]()
for _, i := range ints {
tree.Insert(i)
}
fmt.Println(tree.Search(42))
fmt.Println(tree.Search(96))
fmt.Println(tree.Search(1024))
}
Output: true true false
Example (String) ¶
package main
import (
"fmt"
"github.com/sym01/algo/avl"
)
func main() {
strs := []string{
"eKSI9wZlde",
"j1ORx3W0ph",
"1Lw7uwm4VS",
"WcOTlexQqG",
"hqDGapsHq1",
"mDy5mwwNzx",
"VhY3HfqmG5",
"Y5doxlrZe6",
"VbR2pKkv9E",
"OpUWxSI2eP",
"Ja6CqjnFq5",
"h6dlJ5m",
"PBBKZnRBYu",
"AgX3njkaZT",
"ytXkDnD0vr",
"8QJFS2fLGd",
"PAarEfdt1w", // same string
"PAarEfdt1w", // same string
"PAarEfdt1w", // same string
"8QJFS2fLGd",
}
tree := avl.NewOrderedTree[string]()
for _, s := range strs {
tree.Insert(s)
}
for _, s := range strs {
if !tree.Search(s) {
fmt.Printf("%s not in tree\n", s)
}
}
s := "abccc"
if !tree.Search(s) {
fmt.Printf("%s not in tree\n", s)
}
}
Output: abccc not in tree
type IntTree ¶
type IntTree Tree
IntTree is a high-performance AVL tree for int.
Example ¶
package main
import (
"fmt"
"github.com/sym01/algo/avl"
)
func main() {
ints := []int{
9, 85, 45, 76, 53, 52, 66, 12, 13, 65,
98, 33, 28, 42, 38, 84, 24, 37, 36, 35,
27, 41, 77, 48, 46, 81, 78, 60, 25, 5,
3, 93, 11, 49, 74, 96, 94, 39, 51, 95,
58, 90, 91, 20, 7, 44, 97, 29, 2, 8,
19, 14, 86, 61, 54, 79, 64, 16, 67, 6,
26, 73, 50, 72, 10, 83, 70, 80, 89, 15,
17, 4, 100, 71, 55, 75, 69, 87, 34, 92,
43, 18, 88, 82, 30, 57, 23, 99, 59, 21,
32, 22, 68, 56, 47, 40, 63, 62, 1, 31,
}
tree := new(avl.IntTree)
for _, i := range ints {
tree.Insert(i)
}
fmt.Println(tree.Search(42))
fmt.Println(tree.Search(96))
fmt.Println(tree.Search(1024))
}
Output: true true false
type Range ¶
type Range interface {
// Compare returns an integer comparing two elements.
// The result will be -1 if current element is less than the right,
// and +1 if current element is greater that the right.
// Otherwise, 0 will be return.
Compare(right Range) int
// Contains returns true if the right is a subset of current element.
Contains(right Range) bool
// Union returns the union of current element and the right.
Union(right Range) Range
}
Range is the basic node for the AVL tree leaves. The concept Range can be a real data range in most cases, such as [LOWER_BOUND, UPPER_BOUND] . A Range can also be a single value, such as [VALUE_A, VALUE_A] .
type StringTree ¶
type StringTree Tree
StringTree is a high-performance AVL tree for String.
Example ¶
package main
import (
"fmt"
"github.com/sym01/algo/avl"
)
func main() {
strs := []string{
"eKSI9wZlde",
"j1ORx3W0ph",
"1Lw7uwm4VS",
"WcOTlexQqG",
"hqDGapsHq1",
"mDy5mwwNzx",
"VhY3HfqmG5",
"Y5doxlrZe6",
"VbR2pKkv9E",
"OpUWxSI2eP",
"Ja6CqjnFq5",
"h6dlJ5m",
"PBBKZnRBYu",
"AgX3njkaZT",
"ytXkDnD0vr",
"8QJFS2fLGd",
"PAarEfdt1w", // same string
"PAarEfdt1w", // same string
"PAarEfdt1w", // same string
"8QJFS2fLGd",
}
tree := new(avl.StringTree)
for _, s := range strs {
tree.Insert(s)
}
for _, s := range strs {
if !tree.Search(s) {
fmt.Printf("%s not in tree\n", s)
}
}
s := "abccc"
if !tree.Search(s) {
fmt.Printf("%s not in tree\n", s)
}
}
Output: abccc not in tree
func (*StringTree) Insert ¶
func (t *StringTree) Insert(val string)
Insert a new Range into the AVL tree.
func (*StringTree) Search ¶
func (t *StringTree) Search(val string) bool
Search returns true if the AVL tree contains the <val>.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is a high-performance AVL tree.
Example ¶
package main
import (
"fmt"
"github.com/sym01/algo/avl"
)
// customized data struct for AVL tree
type intRange struct {
min int
max int
}
func (l *intRange) Compare(right avl.Range) int {
r := right.(*intRange)
if l.max < r.min {
return -1
}
if l.min > r.max {
return 1
}
return 0
}
func (l *intRange) Contains(right avl.Range) bool {
r := right.(*intRange)
if l.min > r.min {
return false
}
if l.max < r.max {
return false
}
return true
}
func (l *intRange) Union(right avl.Range) avl.Range {
r := right.(*intRange)
ret := &intRange{
min: l.min,
max: l.max,
}
if ret.min > r.min {
ret.min = r.min
}
if ret.max < r.max {
ret.max = r.max
}
return ret
}
func main() {
data := []*intRange{
{10, 15},
{20, 25},
{30, 35},
{40, 45},
{21, 26},
{50, 55},
{60, 65},
}
tree := new(avl.Tree)
for _, item := range data {
tree.Insert(item)
}
fmt.Println(tree.Search(&intRange{20, 26}))
fmt.Println(tree.Search(&intRange{20, 27}))
}
Output: true false
Source Files
Click to show internal directories.
Click to hide internal directories.