FlatTree (Flat Tree v0.1.0) View Source

You can represent a binary tree in a simple flat list using the following structure:

      3
  1       5
0   2   4   6  ...

FlatTree exposes a series of functions to help you build and maintain this data structure.

import FlatTree

list = []
i = FlatTree.index(0, 0) # get array index for depth: 0, offset: 0
j = FlatTree.index(1, 0) # get array index for depth: 1, offset: 0

# use these indexes to store some data
list = List.insert_at(list, i, "a")
list = List.insert_at(list, j, "b")
list = List.insert_at(list, FlatTree.parent(i), "parent of a and b")

Link to this section Summary

Functions

children(index, depth \\ nil)

Returns a tuple {left_child, right_child} with the indexes of this elements children. If this element does not have any children is returns nil.

count(index, depth \\ nil)

Returns how many nodes (including parent nodes) a tree contains.

depth(index, depth \\ 0)

Returns the depth of an element.

full_roots(index, result \\ [])

Returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) < index. For example full_roots(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.

index(depth, offset)

Returns an array index for the tree element at the given depth and offset.

left_child(index, depth \\ nil)

Returns the index of the left child of this element. If this element does not have a left child it returns -1.

left_span(index, depth \\ nil)

Returns the left spanning in index in the tree index spans.

offset(index, depth \\ nil)

Returns the relative offset of an element.

parent(index, depth \\ nil)

Returns the index of the parent element in tree.

right_child(index, depth \\ nil)

Returns the index of the right child of this element. If this element does not have a right child it returns -1.

right_span(index, depth \\ nil)

Returns the right spanning in index in the tree index spans.

sibling(index, depth \\ nil)

Return the index of this elements sibling.

spans(index, depth \\ nil)

Returns the range (inclusive) the tree root at index spans.

Link to this section Functions

children(index, depth \\ nil)

Specs

children(index :: integer(), depth :: integer() | nil) :: {integer(), integer()}

Returns a tuple {left_child, right_child} with the indexes of this elements children. If this element does not have any children is returns nil.

Examples

iex> FlatTree.children(0)
nil

iex> FlatTree.children(3)
{1, 5}

count(index, depth \\ nil)

Specs

count(index :: integer(), depth :: integer() | nil) :: integer()

Returns how many nodes (including parent nodes) a tree contains.

Examples

iex> FlatTree.count(1)
3

depth(index, depth \\ 0)

Specs

depth(index :: integer(), depth :: integer()) :: integer()

Returns the depth of an element.

Examples

iex> FlatTree.depth(0)
0

iex> FlatTree.depth(3)
2

full_roots(index, result \\ [])

Specs

full_roots(index :: integer(), result :: [integer()]) :: [integer()]

Examples

iex> FlatTree.full_roots(0)
[]

iex> FlatTree.full_roots(18)
[7, 16]

index(depth, offset)

Specs

index(depth :: integer(), offset :: integer()) :: integer()

Returns an array index for the tree element at the given depth and offset.

Examples

iex> FlatTree.index(0, 0)
0

iex> FlatTree.index(0, 2)
4

left_child(index, depth \\ nil)

Specs

left_child(index :: integer(), depth :: integer() | nil) :: integer()

Returns the index of the left child of this element. If this element does not have a left child it returns -1.

Examples

iex> FlatTree.left_child(0)
-1

iex> FlatTree.left_child(3)
1

left_span(index, depth \\ nil)

Specs

left_span(index :: integer(), depth :: integer() | nil) :: integer()

Returns the left spanning in index in the tree index spans.

Examples

iex> FlatTree.left_span(0)
0

iex> FlatTree.left_span(23)
16

offset(index, depth \\ nil)

Specs

offset(index :: integer(), depth :: integer() | nil) :: integer()

Returns the relative offset of an element.

Examples

iex> FlatTree.offset(1)
0

iex> FlatTree.offset(4)
2

parent(index, depth \\ nil)

Specs

parent(index :: integer(), depth :: integer() | nil) :: integer()

Returns the index of the parent element in tree.

Examples

iex> FlatTree.parent(0)
1

iex> FlatTree.parent(1)
3

right_child(index, depth \\ nil)

Specs

right_child(index :: integer(), depth :: integer() | nil) :: integer()

Returns the index of the right child of this element. If this element does not have a right child it returns -1.

Examples

iex> FlatTree.right_child(0)
-1

iex> FlatTree.right_child(3)
5

right_span(index, depth \\ nil)

Specs

right_span(index :: integer(), depth :: integer() | nil) :: integer()

Returns the right spanning in index in the tree index spans.

Examples

iex> FlatTree.right_span(0)
0

iex> FlatTree.right_span(23)
30

sibling(index, depth \\ nil)

Specs

sibling(index :: integer(), depth :: integer() | nil) :: integer()

Return the index of this elements sibling.

Examples

iex> FlatTree.sibling(0)
2

iex> FlatTree.sibling(2)
0

spans(index, depth \\ nil)

Specs

spans(index :: integer(), depth :: integer() | nil) :: {integer(), integer()}

Returns the range (inclusive) the tree root at index spans.

Examples

iex> FlatTree.spans(0)
{0, 0}

iex> FlatTree.spans(3)
{0, 6}