#flat #tree #binary

flat-tree

Series of functions to map a binary tree to a list

18 stable releases (5 major)

6.0.0 Apr 12, 2023
5.0.0 Mar 3, 2020
4.1.0 Apr 23, 2019
4.0.1 Mar 6, 2019
1.0.0 Mar 9, 2016

#5 in #binary-tree

Download history 185/week @ 2023-11-02 80/week @ 2023-11-09 104/week @ 2023-11-16 91/week @ 2023-11-23 367/week @ 2023-11-30 509/week @ 2023-12-07 102/week @ 2023-12-14 102/week @ 2023-12-21 101/week @ 2023-12-28 222/week @ 2024-01-04 638/week @ 2024-01-11 112/week @ 2024-01-18 102/week @ 2024-01-25 85/week @ 2024-02-01 174/week @ 2024-02-08 320/week @ 2024-02-15

688 downloads per month
Used in 8 crates (5 directly)

MIT/Apache

26KB
377 lines

flat-tree

crates.io version build status downloads docs.rs docs

Map a binary tree to a list. Adapted from mafintosh/flat-tree.

License

MIT OR Apache-2.0


lib.rs:

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.

No runtime deps