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 |
#739 in Data structures
304 downloads per month
Used in 10 crates
(5 directly)
26KB
377 lines
flat-tree
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.