Containers - Trees - 《[英文] Go Data Structures 文档手册》

Trees

Trees

A tree is a widely used data data structure that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes; thus no cyclic links.

Implements Container interface.

type Tree interface {
    containers.Container
    // Empty() bool
    // Size() int
    // Clear()
    // Values() []interface{}
}

RedBlackTree

A red–black tree is a binary search tree with an extra bit of data per node, its color, which can be either red or black. The extra bit of storage ensures an approximately balanced tree by constraining how nodes are colored from any path from the root to the leaf. Thus, it is a data structure which is a type of self-balancing binary search tree.

The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time. _^Wikipedia

Implements Tree, ReverseIteratorWithKey, JSONSerializer and JSONDeserializer interfaces.

package main
import (
    "fmt"
    rbt "github.com/emirpasic/gods/trees/redblacktree"
)
func main() {
    tree := rbt.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)
    //
    //  RedBlackTree
    //  │           ┌── 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)
    //
    //  RedBlackTree
    //  │       ┌── 6
    //  │   ┌── 5
    //  └── 4
    //      │   ┌── 3
    //      └── 1
    tree.Clear() // empty
    tree.Empty() // true
    tree.Size()  // 0
    // Other:
    tree.Left() // gets the left-most (min) node
    tree.Right() // get the right-most (max) node
    tree.Floor(1) // get the floor node
    tree.Ceiling(1) // get the ceiling node
}

Extending the red-black tree’s functionality has been demonstrated in the following example.

AVLTree

AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

AVL trees are often compared with red–black trees because both support the same set of operations and take O(log n) time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced. _^Wikipedia

Implements Tree, ReverseIteratorWithKey, JSONSerializer and JSONDeserializer interfaces.

_{AVL tree with balance factors (green)}

package main
import (
    "fmt"
    avl "github.com/emirpasic/gods/trees/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
}

BTree

B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children.

According to Knuth’s definition, a B-tree of order m is a tree which satisfies the following properties:

Every node has at most m children.
Every non-leaf node (except root) has at least ⌈m/2⌉ children.
The root has at least two children if it is not a leaf node.
A non-leaf node with k children contains k−1 keys.
All leaves appear in the same level

Each internal node’s keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost subtree will be greater than a2._^Wikipedia

Implements Tree, ReverseIteratorWithKey, JSONSerializer and JSONDeserializer interfaces.

package main
import (
    "fmt"
    "github.com/emirpasic/gods/trees/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
}

BinaryHeap

A binary heap is a tree created using a binary tree. It can be seen as a binary tree with two additional constraints:

Shape property:

A binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
Heap property:

All nodes are either greater than or equal to or less than or equal to each of its children, according to a comparison predicate defined for the heap. _^Wikipedia

Implements Tree, ReverseIteratorWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main
import (
    "github.com/emirpasic/gods/trees/binaryheap"
    "github.com/emirpasic/gods/utils"
)
func main() {
    // Min-heap
    heap := binaryheap.NewWithIntComparator() // empty (min-heap)
    heap.Push(2)                              // 2
    heap.Push(3)                              // 2, 3
    heap.Push(1)                              // 1, 3, 2
    heap.Values()                             // 1, 3, 2
    _, _ = heap.Peek()                        // 1,true
    _, _ = heap.Pop()                         // 1, true
    _, _ = heap.Pop()                         // 2, true
    _, _ = heap.Pop()                         // 3, true
    _, _ = heap.Pop()                         // nil, false (nothing to pop)
    heap.Push(1)                              // 1
    heap.Clear()                              // empty
    heap.Empty()                              // true
    heap.Size()                               // 0
    // Max-heap
    inverseIntComparator := func(a, b interface{}) int {
        return -utils.IntComparator(a, b)
    }
    heap = binaryheap.NewWith(inverseIntComparator) // empty (min-heap)
    heap.Push(2, 3, 1)                              // 3, 2, 1 (bulk optimized)
    heap.Values()                                   // 3, 2, 1
}