Documentation
¶
Overview ¶
Package bmtree encode a binary tree into a bitmap. Present nodes are set to 1 in bitmap, absent nodes are set to 0.
A node is identified with its searching path: E.g. a path 0110 means going from root node and then choose left, right, right and left branch.
"bmtree" supports encoding a binary tree of up to 30 levels and the result bitmap size is 0~2^31-1. E.g. the following three nodes "0", "01", "10" can be encoded into a 7 bits bitmap: "0101010". The mapping of all nodes in a 2 level tree are:
path index in bitmap "" 0 "0" 1 "00" 2 "01" 3 "1" 4 "10" 5 "11" 6
How it works ¶
If there is a binary tree: an empty bit array is mapped to root node, "01" is mapped to node 01, etc.
root h=2
/ \
0 1 h=1
/ \ / \
00 01 10 11 h=0
To assign a node to a index in bitmap, We places them in "pre-order"(or NLR: parent node comes before left child, then right child), thus "0" comes before "00" in the bitmap:
Put a node at index x, then start from x+1 to put its left-subtree, then right-subtree, recursively.
Root node is at the 0-th bit.
Path:
A path is for selecting a node. E.g.: a "0" in a path for selecting left child, a "1" for right child.
The representation of a path is a uint64, the higher 32 bits are path mask, the lower 32 bits are searching bits:
0...011111000 0...0xxxxx000 <-- significant bits
The Left most bit in path-mask indicates the tree height.
A full binary tree has 2^(h+1)-1 nodes thus the result bitmap has 2^(h+1)-1 bits.
Since 0.1.9
Index ¶
- func AllPaths(bitmapSize int32, from, to uint64) []uint64
- func Decode(bitmapSize int32, bm []uint64) []uint64
- func Height(bitmapSize int32) int32
- func IndexToPath(treeheight int32, index int32) uint64
- func NewPath(searchingBits uint64, length, height int32) uint64
- func PathBits(path uint64) uint64
- func PathHeight(path uint64) int32
- func PathLen(p uint64) int32
- func PathMask(path uint64) uint64
- func PathOf(s string, frombit int32, height int32) uint64
- func PathStr(path uint64) string
- func PathToIndex(bitmapSize int32, path uint64) int32
- func PathToIndexLoose(bitmapSize int32, path uint64) (int32, int32)
- func PathsOf(keys []string, frombit int32, height int32, dedup bool) []uint64
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func IndexToPath ¶
IndexToPath returns the path encoded to index.
It determines every bit in path one by one:
If the highest bit in path, p[h-1] == 0, then index is in range [1, 2^h); If p[h-1] == 1, then index is in range [2^h, 2^h+2^h-1). This way we narrow down the query into a subtree. Repeat it until index becomes to 0:
index[h] == 0: p[h-1] = 0, index -= 1 index[h] == 1: p[h-1] = 1, index -= 2^h
In our implementation we have two optimization: First, the last 4 levels query with a lookup table. Second, before bit-by-bit parsing, it tries to find the longest common prefix of index - treeheight and index:
Because index = p*2 + rank0(p), then we have index - width <= p*2 <= index. Thus common prefix of index - width and index is also a prefix of p*2
Since 0.1.9
func NewPath ¶
NewPath creates a path, which is a uint64, from node searching path, path length and tree height.
Since 0.1.9
func PathBits ¶ added in v0.1.12
PathBits returns the searching bit, e.g., discard the height info.
Since 0.1.12
func PathMask ¶ added in v0.1.12
PathMask returns the mask, e.g., discard the searching bits.
Since 0.1.12
func PathOf ¶
PathOf creates a path, which is a uint64, from a string and sepcified starting bit position and height.
Since 0.1.9
func PathToIndex ¶
PathToIndex convert a node searching path to a bit index in bitmap.
Bitmap size ¶
The tree height is "h". The following is a tree of height 2.
root h=2
/ \
0 1 1
/ \ / \
00 01 10 11 0
The bitmap size for a full binary tree is 2^(h+1) - 1, or
11111...111 `-- h+1 --'
If we do not need to store a entire level of a tree, we do not need to assign bits for these node. Thus we reduce the bitmap size by 2^(h-i) for a tree without i-th level. E.g. if a tree of height 2 does not need level-1 nodes, the bitmap size is: 101 instead of 111.
Thus the bitmap size "T" for a tree with some levels absent is:
T = t[h]t[h-1]...t[1]t[0] = 101110..011
`-- h+1 --'
In which t[h-i] == "1" indicates the bitmap stores i-th level nodes. And we see that the size of a subtree rooted at i-th level node is:
T>>(h-i)
Mapping node to bitmap index ¶
If we start encode a subtree of height i from the x-th bit in bitmap, then:
if the bitmap stores the i-th level nodes(t[h-i] == 1): then its left subtree starts from x + 1, otherwise its left subtree starts from x.
Thus its left subtree starts from x + t[h-i]. And its right subtree starts from x + t[h-i] + T>>(h-i+1).
Because we starts with x=0, and i from h down to l:
Thus the bit position of a path of length l is:
bitIndex = t[0] + p[h-1] * (T>>1) // root at h
+ t[1] + p[h-2] * (T>>2) // at h - 1
+ t[2] + p[h-3] * (T>>3) // at h - 2
...
+ t[l-1] + p[0] * (T>>l)
Quick path ¶
If T is all "1", there is a quick path:
h-1
bitIndex = l + sum(p[i] * 2^(i+1)) - rank1(p)
i=0
= p * 2 + l - rank1(p)
= p * 2 + rank1(pathmask) - rank1(p)
= p * 2 + rank1(pathmask) - 32 + rank1(^p)
// "rank1" returns count of "1" in a int.
Because we store the path-mask togeter with the path in uint64, we can use just one rank1 to get the index:
bitIndex = p * 2 + rank1(path^0xffffffff) - 32
Since 0.1.9
func PathToIndexLoose ¶
PathToIndexLoose is same as PathToIndex except it allows the path to locate at a level the bitmap does not store. It returns the index and 1 if the level exist, otherwise the index and 0.
Since 0.1.9
Types ¶
This section is empty.
Source Files