Documentation ¶
Overview ¶
Package flattree implements a series of functions to map a binary tree to a list.
You can represent a binary tree in a simple flat list using the following structure
3 1 5 0 2 4 6 ...
This module exposes a series of functions to help you build and maintain this data structure.
See also ¶
flat-tree for node: https://github.com/mafintosh/flat-tree.
print-flat-tree: https://github.com/mafintosh/print-flat-tree.
flat-tree for rust: https://github.com/mafintosh/flat-tree-rs.
Example ¶
package main import ( "fmt" "github.com/bcomnes/flattree" ) func main() { var list = make([]uint64, 16, 50) i := flattree.Index(1, 0) // get array index for depth: 0, offset: 0 j := flattree.Index(3, 0) // get array index for depth: 1, offset: 0 // use these indexes to store some data list[i] = i list[j] = j parent := flattree.Parent(j, 0) list[parent] = parent fmt.Println(i) fmt.Println(j) fmt.Println(parent) fmt.Println(list) }
Output: 1 7 15 [0 1 0 0 0 0 0 7 0 0 0 0 0 0 0 15]
Index ¶
- func Count(index, depth uint64) uint64
- func Depth(index uint64) uint64
- func FullRoots(index uint64, result []uint64) ([]uint64, error)
- func Index(depth, offset uint64) uint64
- func LeftChild(index, depth uint64) (uint64, error)
- func LeftSpan(index, depth uint64) uint64
- func Offset(index, depth uint64) uint64
- func Parent(index, depth uint64) uint64
- func RightChild(index, depth uint64) (uint64, error)
- func RightSpan(index, depth uint64) uint64
- func Sibling(index, depth uint64) uint64
- type Iterator
- func (i *Iterator) IsLeft() bool
- func (i *Iterator) IsRight() bool
- func (i *Iterator) LeftChild() uint64
- func (i *Iterator) LeftSpan() uint64
- func (i *Iterator) Next() uint64
- func (i *Iterator) Parent() uint64
- func (i *Iterator) Prev() uint64
- func (i *Iterator) RightChild() uint64
- func (i *Iterator) RightSpan() uint64
- func (i *Iterator) Seek(index uint64)
- func (i *Iterator) Sibling() uint64
- type Range
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func FullRoots ¶
FullRoots returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) `<` index. For example `fullRoots(8)` returns `[3]` since the subtree rooted at `3` spans `0 -> 6` and the tree rooted at `7` has a child located at `9` which is `>= 8`.
func RightChild ¶
RightChild returns the right most child at index and depth.
Types ¶
type Iterator ¶
type Iterator struct {
Index, Offset, Factor uint64
}
Iterator is a stateful iterator type. Use NewIterator to create tree Iterators at a given index.
func NewIterator ¶
NewIterator returns a stateful tree iterator at a given index.
func (*Iterator) RightChild ¶
RightChild moves the iterator to the current right child index.