flat-tree

Series of functions to map a binary tree to a list

18 stable releases(5 major)

 6.0.0 Apr 12, 2023 Mar 3, 2020 Apr 23, 2019 Mar 6, 2019 Mar 9, 2016

#5 in #binary-tree

Used in 8 crates (5 directly)

MIT/Apache

26KB
377 lines

flat-tree

Map a binary tree to a list. Adapted from mafintosh/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.