Crate flat_tree

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:

                                    15
              7                                             23
      3                 11                      19                      27
  1       5        9          13          17          21          25          29
0   2   4   6   8    10    12    14    16    18    20    22    24    26    28    30...

Each number represents an index in a flat list. So a tree:

      A
  B       C
D   E   F   G  ...

would be represented as a list: [D B E A F C G]

Furthermore, indexes 0, 2, 4, 6 are on depth 0. 1, 5, 9 on depth 1. And so forth.

depth = 2  ^        3
depth = 1  |    1       5
depth = 0  |  0   2   4   6  ...

In some cases it is also useful to calculate an offset. Indexes 0, 1, 3, 7 have an offset 0:

                (7)
       (3)
  (1)       5
(0)   2   4   6      ...

2, 5, 11, 23 offset 1:

                 7
       3                  (11)
  1        (5)        9          13
0   (2)   4   6    8    10    12    14

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

Structs

Iterator

Iterator over a flat-tree.

Functions

children

Returns both children of a node.

count

Returns how many nodes are in the tree that the node spans.

count_leaves

Returns how many leaves are in the tree that the node spans.

depth

Returns the depth of a node.

full_roots

Returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) < index.

index

Returns the flat-tree of the tree node at the specified depth and offset.

left_child

Returns only the left child of a node.

left_span

Returns the left most node in the tree that it spans.

offset

Returns the offset of a node.

parent

Returns the parent of a node with a depth.

right_child

Returns only the left child of a node.

right_span

Returns the right most node in the tree that the node spans.

sibling

Returns the sibling of a node.

spans

Returns the left and right most nodes in the tree that the node spans.

uncle

Returns the parent’s sibling, of a node.