Crate flat_tree

Crate flat_tree 

Source
Expand description

§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.