btree

m阶b树是一棵树，它满足以下性质:—每个节点最多有m个子节点。-每个非叶节点(根节点除外)至少有⌈m/2⌉子节点。—如果根节点不是叶节点，则根节点至少有两个子节点。—具有k个子节点的非叶节点包含k−1个键。-所有的叶子出现在同一水平

type Entry

entry表示节点中包含的键值对

type Entry struct {
    Key   interface{}
    Value interface{}
}
func (entry *Entry) String() string

type Node

type Node struct {
    Parent   *Node
    Entries  []*Entry // Contained keys in node
    Children []*Node  // Children nodes
}

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 Tree

type Tree struct {
    Root       *Node            // Root node
    Comparator utils.Comparator // Key comparator
    // contains filtered or unexported fields
}
func NewWith(order int, comparator utils.Comparator) *Tree
// 实例化一个具有IntComparator的树，即键是int类型的
func NewWithIntComparator(order int) *Tree
// 用StringComparator实例化一个树，即键的类型是string
func NewWithStringComparator(order int) *Tree
func (tree *Tree) Clear()
func (tree *Tree) Empty() bool
func (tree *Tree) FromJSON(data []byte) error
func (tree *Tree) Get(key interface{}) (value interface{}, found bool)
func (tree *Tree) Height() int
func (tree *Tree) Iterator() Iterator
func (tree *Tree) Keys() []interface{}
func (tree *Tree) Left() *Node
func (tree *Tree) LeftKey() interface{}
func (tree *Tree) LeftValue() interface{}
func (tree *Tree) Put(key interface{}, value interface{})
func (tree *Tree) Remove(key interface{})
func (tree *Tree) Right() *Node
func (tree *Tree) RightKey() interface{}
func (tree *Tree) RightValue() interface{}
func (tree *Tree) Size() int
func (tree *Tree) String() string
func (tree *Tree) ToJSON() ([]byte, error)
func (tree *Tree) Values() []interface{}

例子：

package main
import (
    "fmt"
    "github.com/emirpasic/gods/trees/btree"
)
// BTreeExample to demonstrate basic usage of BTree
func main() {
    tree := btree.NewWithIntComparator(3) // 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)
    tree.Put(7, "g") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f, 7->g (in order)
    fmt.Println(tree)
    // BTree
    //         1
    //     2
    //         3
    // 4
    //         5
    //     6
    //         7
    _ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f", "g"} (in order)
    _ = tree.Keys()   // []interface {}{1, 2, 3, 4, 5, 6, 7} (in order)
    tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order)
    fmt.Println(tree)
    // BTree
    //     1
    //     3
    // 4
    //     5
    //     6
    tree.Clear() // empty
    tree.Empty() // true
    tree.Size()  // 0
    // Other:
    tree.Height()     // gets the height of the tree
    tree.Left()       // gets the left-most (min) node
    tree.LeftKey()    // get the left-most (min) node's key
    tree.LeftValue()  // get the left-most (min) node's value
    tree.Right()      // get the right-most (max) node
    tree.RightKey()   // get the right-most (max) node's key
    tree.RightValue() // get the right-most (max) node's value
}