Map a binary tree to a vector.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
benches Criterion (#40) Nov 2, 2018
src count trailing ones (#38) Nov 2, 2018
tests
.gitignore first commit Mar 9, 2016
.travis.yml
CHANGELOG.md Update changelog Nov 2, 2018
Cargo.toml Criterion (#40) Nov 2, 2018
LICENSE-APACHE Relicense to MIT OR Apache-2.0 Mar 30, 2018
LICENSE-MIT
README.md Add a bit more terminology into README (#37) Oct 28, 2018
rustfmt.toml document nodes (#1) Feb 10, 2018

README.md

flat-tree

crates.io version build status downloads docs.rs docs

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

Usage

extern crate flat_tree;

let parent = flat_tree::parent(0);
println!("parent of 0 is {}", parent);

Why?

You can represent a binary tree in a simple flat list using the following structure:

      3
  1       5
0   2   4   6  ...

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    10   12    14    15

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

License

MIT OR Apache-2.0