FlatTree

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

      3
  1       5
0   2   4   6  ...

Flat Trees are the core data structure that power Hypercore feeds. This Elixir implementation is adapted from mafintosh/flat-tree. More details can be found here.

Installation

The package can be installed by adding flat_tree to your list of dependencies in mix.exs:

def deps do
  [
    {:flat_tree, "~> 0.1.0"}
  ]
end

Usage

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

import FlatTree

list = []
i = FlatTree.index(0, 0) # get array index for depth: 0, offset: 0
j = FlatTree.index(1, 0) # get array index for depth: 1, offset: 0

# use these indexes to store some data
list = List.insert_at(list, i, "a")
list = List.insert_at(list, j, "b")
list = List.insert_at(list, FlatTree.parent(i), "parent of a and b")