#flat #tree #binary

flat-tree

Rust module for encoding/decoding varints that doesn’t do any IO. Inspired by the Node.js varint module

17 stable releases (4 major)

Uses old Rust 2015

5.0.0 Mar 3, 2020
4.1.0 Apr 23, 2019
4.0.1 Mar 6, 2019
3.7.0 Nov 2, 2018
1.0.0 Mar 9, 2016

#636 in Data structures

Download history 38/week @ 2021-08-15 26/week @ 2021-08-22 8/week @ 2021-08-29 13/week @ 2021-09-05 11/week @ 2021-09-12 20/week @ 2021-09-19 39/week @ 2021-09-26 30/week @ 2021-10-03 30/week @ 2021-10-10 16/week @ 2021-10-17 37/week @ 2021-10-24 32/week @ 2021-10-31 29/week @ 2021-11-07 13/week @ 2021-11-14 30/week @ 2021-11-21 42/week @ 2021-11-28

117 downloads per month
Used in 5 crates

MIT license

19KB
320 lines

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

No runtime deps

]^