avltree

AVL平衡二叉树

type Iterator

func (iterator *Iterator) Begin()  // 将迭代器重置为初始状态，然后调用Next获取第一个元素
func (iterator *Iterator) End()    // 将迭代器移过最后一个元素，然后调用Prev获取最后一个元素
// 将迭代器移动到第一个元素，如果容器中有第一个元素则返回true。
// 如果First()返回true，则可以通过index()和value()检索第一个元素的索引和值。修改迭代器的状态
func (iterator *Iterator) First() bool
// 将迭代器移动到最后元素，如果容器中有第一个元素则返回true。
// 如果Last()返回true，则可以通过index()和value()检索第一个元素的索引和值。修改迭代器的状态
func (iterator *Iterator) Last() bool
func (iterator *Iterator) Next() bool
func (iterator *Iterator) Prev() bool
func (iterator *Iterator) Index() int 
func (iterator *Iterator) Value() interface{}

type Node

type Node struct {
    Key      interface{}
    Value    interface{}
    Parent   *Node    // Parent node
    Children [2]*Node // Children nodes
    // contains filtered or unexported fields
}
func (n *Node) Next() *Node
func (n *Node) Prev() *Node
func (n *Node) String() string

type Tree

func NewWith(comparator utils.Comparator) *Tree
// 实例化一个具有IntComparator的树，即键是int类型的
func NewWithIntComparator() *Tree
// 用StringComparator实例化一个树，即键的类型是string
func NewWithStringComparator() *Tree
// 找打大于或等于key节点的最小节点
func (t *Tree) Ceiling(key interface{}) (floor *Node, found bool)
func (t *Tree) Clear()
func (t *Tree) Empty() bool
// 找打小于或等于key节点的最小节点
func (t *Tree) Floor(key interface{}) (floor *Node, found bool)
func (tree *Tree) FromJSON(data []byte) error
func (t *Tree) Get(key interface{}) (value interface{}, found bool)
// 返回一个有序迭代器
func (tree *Tree) Iterator() containers.ReverseIteratorWithKey
func (t *Tree) Keys() []interface{}
func (t *Tree) Left() *Node
func (t *Tree) Put(key interface{}, value interface{})
func (t *Tree) Remove(key interface{})
func (t *Tree) Right() *Node
func (t *Tree) Size() int
func (t *Tree) String() string
func (tree *Tree) ToJSON() ([]byte, error)
func (t *Tree) Values() []interface{}

例子：

package main
import (
    "fmt"
    avl "github.com/emirpasic/gods/trees/avltree"
)
// AVLTreeExample to demonstrate basic usage of AVLTree
func main() {
    tree := avl.NewWithIntComparator() // empty(keys are of type int)
    tree.Put(1, "x") // 1->x
    tree.Put(2, "b") // 1->x, 2->b (in order)
    tree.Put(1, "a") // 1->a, 2->b (in order, replacement)
    tree.Put(3, "c") // 1->a, 2->b, 3->c (in order)
    tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order)
    tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order)
    tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)
    fmt.Println(tree)
    //
    //  AVLTree
    //  │       ┌── 6
    //  │   ┌── 5
    //  └── 4
    //      │   ┌── 3
    //      └── 2
    //          └── 1
    _ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f"} (in order)
    _ = tree.Keys()   // []interface {}{1, 2, 3, 4, 5, 6} (in order)
    tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order)
    fmt.Println(tree)
    //
    //  AVLTree
    //  │       ┌── 6
    //  │   ┌── 5
    //  └── 4
    //      └── 3
    //          └── 1
    tree.Clear() // empty
    tree.Empty() // true
    tree.Size()  // 0
}