# Best way to store a sparse, unbalanced, and not complete binary tree

**URL:** <https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902>\
**Category:** General Usage\
**Tags:** mutable-structure, tree\
**Created:** [January 20, 2022, 4:49am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902 "2022-01-20T04:49:03Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![AlessioLapolla](https://avatars.discourse-cdn.com/v4/letter/a/e9bcb4/32.png) [@AlessioLapolla](https://discourse.julialang.org/u/AlessioLapolla)\
**Post date:** [January 20, 2022, 4:49am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/1 "2022-01-20T04:49:03Z")

</div>

I am implementing a binary tree where given the key of the root and a function the left and right children are defined up to a given depth that is an other parameter of the constructing function: `create_tree!(tree, key, func, depth)` . The most straightforward way in my opinion is to define tree as a `Vector{Union{Int,Nothing}` . This solution is clear, in my opinion. However in my case `func` is such that if `depth=15` around 97% of the nodes in `tree` happen to be `nothing` . Since I would like to avoid wasting memory and I need even deeper trees I am asking: is there a good way to implement such a binary tree in Julia? To give more context I can also add that `func` is such that is more probable that the left child of a given node is `nothing` with respect to the right child. In a language like C or C++ I would use pointer based construction of a tree. I suppose I could define a Julia type that acts like a pointer but I am wondering if there is a easier and more straightforward solution.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 20, 2022, 5:11am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/2 "2022-01-20T05:11:27Z")

</div>

I’d probably use

```julia
mutable struct Node{T}
    value::T
    left::Union{Nothing, Node{T}}
    right::Union{Nothing, Node{T}}
end
const Tree{T} = Union{Nothing, Node{T}}

```

---

<div class="post-metadata">

**Author:** ![guoyongzhi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/guoyongzhi/32/28306_2.png) [@guoyongzhi](https://discourse.julialang.org/u/guoyongzhi)\
**Post date:** [January 21, 2022, 3:13am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/3 "2022-01-21T03:13:25Z")

</div>

Agree with [@goerch](https://discourse.julialang.org/u/goerch)’ answer, and we can do away with `Union{Nothing, Node{T}}` by [incomplete initialization](https://docs.julialang.org/en/v1/manual/constructors/#Incomplete-Initialization), which makes it acts more like a pointer thing.

```julia
mutable struct TreeNode{T}
    value::T
    parent::TreeNode{T}
    left::TreeNode{T}
    right::TreeNode{T}
    function TreeNode{T}() where T
        n = new{T}()
        n.parent = n
        n.left = n
        n.right = n
        n
    end
    TreeNode{T}(v, p, l, r) where T = new{T}(v, p, l, r)
end

```

With this definition, some basic functions of the linked-binary-tree need to be redefined, such as `isroot(n::TreeNode) = n === n.parent`. I implemented a [linked-quadtree type](https://github.com/guo-yong-zhi/Stuffing.jl/blob/c11ab4bf81e80f2c53b64601b08fd85b9e4880e6/src/qtrees.jl#L339) in my project. Things are similar. I hope it will help you.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 21, 2022, 10:40am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/4 "2022-01-21T10:40:09Z")

</div>

Interesting. On one hand I can imagine that using `undef` that way could simplify type inference. OTOH you need to use `isassigned(p)` instead of `p !== nothing` and worse to reset `p` to `undef` you’d need something like `unsafe_store!` as @jakobnissen pointed out recently on slack.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [January 21, 2022, 11:45am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/5 "2022-01-21T11:45:05Z")

</div>

Depends on the application, as always.

If you don’t need to modify the tree structure after construction, I’m a big fan of the following layout. It is optimized for the case that you need to traverse left more often than right (following left typically hits the same cache-line that you already have loaded), so you may need to internally rename left-right. Only existing nodes are stored (no `nothing` stuff). There is no depth-bound, you simply have a bunch of nodes.

The structure is

```julia
struct Tree{T}
keys::Vector{T}
child_right::Vector{Int} #or Int32 or UInt32...
end

```

The order is:

```julia
[root, L, LL, ...., LR, LRL, LRLL, ..., R, RL, ...]

```

(in other words, attach to each node the ‘L’/‘R’ string corresponding to the path in the tree to reach the node; then sort lexicographically; for each node, store as metadata the offset to (or position of, depending on what you find more convenient) `string_label(node) * "R"` if that node exists in the tree and 0 otherwise)

Subtrees are always sequential in memory and their size is known without further searching. Searching for keys is always accessing memory in sequential ascending order, unless you’re e.g. searching for a best-match. When the remaining subtree is small enough, you can seamlessly switch to linear search.

It is quite useful in practice to also include parent pointers for convenience.

Structure is also good for easily parallelized in-place construction or computing and storing tree-stuff for every node (spawn a task for the right subtree if size above threshold; due to the memory layout you very rarely have slowdowns due to different cores writing to the same cacheline).

PS. You must identify subtrees by the pair `(subtree_root_index, subtree_upper_bound)`. The upper bound is computed during traversal from root. Otherwise you cannot distinguish the situations where a node has no children at all, or no right child but a nonempty left subtree.

If you include extra metadata (e.g. parent pointers, subtree\_upper\_bound, domain-specific info) then it is advisable to use something like

```julia
struct NodeMetadata
child_right::Int
#e.g. parent::Int
...
end

struct Tree{T}
data::Vector{T}
metadata::Vector{NodeMetadata}
end

```

for the sake of better memory access.

I advise against attempting to mix data and metadata – that opens a big can of structure padding worms, makes SIMD harder and makes it harder to use domain-specific implementation for linear search on small subtrees.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 21, 2022, 1:50pm UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/6 "2022-01-21T13:50:49Z")

</div>

> [@foobar\_lv2](#):
>
> `[root, L, LL, ...., LR, LRL, LRLL, ..., R, RL, ...]`

Is this the [vine](https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm) data structure representing a tree traversal?

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [January 21, 2022, 2:19pm UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/7 "2022-01-21T14:19:01Z")

</div>

> [@goerch](#):
>
> Is this the [vine](https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm) data structure representing a tree traversal?

It’s original (in the sense that I once needed something like this and came up with it), but almost certainly not novel. It’s the kind of stuff that is easier to reinvent or ask discourse / stackoverflow / “oral communications” about than doing a literature search for.

If you happen to know a famous name for this layout, please share! A wiki link could save me some source code comments and/or pages of explanations in papers that use this.

The vine stuff you linked to looks different? The wiki talks about “rebalancing”, while I only gave a memory layout and metadata style for a given tree. How do build it depends on your domain – there are very good domain-specific reasons for unbalanced trees. E.g. if your datapoints have probability mass then you want your tree to be balanced with respect to mass, not with respect to number-of-points. If your datapoints live in a metric space, you may want to balance your tree by diameter, not number-of-points (that was my domain). Either way you end up with a tree that is horribly unbalanced for good reasons and that must not be rebalanced according to naive “number of points”.

Hence the above layout takes some pains to not be worse than a flat array (no linked-list heap-vomit with large overheads in case of completely degenerate tree, modest metadata overhead, etc).

---

<div class="post-metadata">

**Author:** ![guoyongzhi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/guoyongzhi/32/28306_2.png) [@guoyongzhi](https://discourse.julialang.org/u/guoyongzhi)\
**Post date:** [January 22, 2022, 3:47am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/8 "2022-01-22T03:47:40Z")

</div>

Can you provide a link to `@jakobnissen`’s proposal?  
In fact, I initialized the node’s field with itself instead of leaving them `undef`ined. I wonder if there is any performance difference in accessing uninitialized fields. Or is there always a protective check, whether it is initialized or not?

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 22, 2022, 10:19am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/9 "2022-01-22T10:19:43Z")

</div>

Here is @jakobnissen 's example

```julia
julia> A = ["hello"]
1-element Vector{String}:
 "hello"

julia> unsafe_store!(Ptr{UInt}(pointer(A, 1)), zero(UInt));

julia> A
1-element Vector{String}:
 #undef

```

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [January 22, 2022, 10:47am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/10 "2022-01-22T10:47:37Z")

</div>

I almost feel bad unleasing such shady code into the world! 😅  
You should make sure `Union{String, Nothing}` isn’t good enough first.

If you store it in a struct:

```julia
julia> struct Foo
           x::Union{String, Nothing}
       end

julia> sizeof(Foo)
8

```

Then the union type takes no extra memory. It’s simply stored as a pointer either to the `Nothing` type (I think), or to the actual string.  
If you use an array of the kind `Vector{Union{String, Nothing}}`, then the memory layout will be two dense arrays, one with pointers, and another byte array with `0x00` for `Nothing` and `0x01` for `String`, for a total of only 9 bytes per object, which is only 13% more than the 8 bytes a pure `String` array would take.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 22, 2022, 10:55am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/11 "2022-01-22T10:55:53Z")

</div>

> [@jakobnissen](#):
>
> I almost feel bad unleasing such shady code into the world!

No need to! The code looked terrible enough for me to try to find another solution…

Here we discuss if using uninitialized or partially initialized `struct`s could provide any benefits. Does your technique apply to `struct`s also? I’m nearly tempted to write a micro benchmark.

Thanks for your help!

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [January 22, 2022, 11:07am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/12 "2022-01-22T11:07:40Z")

</div>

Yes, you can use `pointer_from_objref` to get a pointer to a mutable type, and for immutable types, you can put (probably?) them in a `Ref`, then take a pointer to the `Ref`. Again, 💣

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 22, 2022, 12:13pm UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/13 "2022-01-22T12:13:57Z")

</div>

> [@jakobnissen](#):
>
> Yes, you can use `pointer_from_objref` to get a pointer to a mutable type.

Edit: I obviously have to use mutables…

I tried this

```julia
mutable struct Example
    el::String
    Example() = new()
    Example(el) = new(el)
end

B = Example("hello")
unsafe_store!(Ptr{UInt}(pointer_from_objref(B)), zero(UInt), 1);
println(B)

```

yielding

```julia
Example(#undef)

```

Thanks!

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 22, 2022, 12:43pm UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/14 "2022-01-22T12:43:23Z")

</div>

Interesting. IMHO the micro benchmark exactly shows the tradeoffs:

```julia
using BenchmarkTools

mutable struct Node1{T}
    value::T
    next::Union{Nothing, Node1{T}}
end
const List1{T} = Union{Nothing, Node1{T}}

function test1()
    list = nothing
    for i in 1:1000
        list = Node1(i, list)
    end
    nodes = []
    s = 0
    while list !== nothing
        s += list.value
        push!(nodes, list)
        list = list.next
    end
    for node in nodes
        node.next = nothing
        @assert node.next === nothing
    end
    s
end
      
mutable struct Node2{T}
    value::T
    next::Node2{T}
    Node2{T}(value) where T = new{T}(value)
    Node2{T}(value, next) where T = new{T}(value, next)
end
const List2{T} = Union{Nothing, Node2{T}}

function test2()
    list = Node2{Int}(1)
    for i in 2:1000
        list = Node2{Int}(i, list)
    end
    nodes = []
    s = 0
    while list !== nothing
        s += list.value
        push!(nodes, list)
        list = isdefined(list, :next) ? list.next : nothing
    end
    for node in nodes
        ptr = convert(Ptr{UInt}, Base.pointer_from_objref(node))
        unsafe_store!(ptr, zero(UInt), 2)
        @assert !isdefined(node, :next)
    end
    s
end

res1 = test1()
res2 = test2()
@assert res1 == res2

@btime test1()
@btime test2()

```

yielding

```julia
  104.300 μs (1006 allocations: 53.09 KiB)
  24.600 μs (1006 allocations: 53.09 KiB)

```

Which type annotations are needed to eliminate dynamic dispatch in the first test case?

---

<div class="post-metadata">

**Author:** ![guoyongzhi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/guoyongzhi/32/28306_2.png) [@guoyongzhi](https://discourse.julialang.org/u/guoyongzhi)\
**Post date:** [January 23, 2022, 4:58am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/15 "2022-01-23T04:58:44Z")

</div>

Maybe it would be better to have a new function like `setasundef!` in julia `Base`.

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [January 23, 2022, 11:46am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/16 "2022-01-23T11:46:47Z")

</div>

I don’t get the benchmarking - what two, different, functions are you benchmarking?

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 23, 2022, 11:53am UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/17 "2022-01-23T11:53:29Z")

</div>

Inserting into a list, sum the list entries and set all next pointers to nothing or undefined respectively. First data structure uses `Union{Nothing, Node1{T}}` as pointer to next element, second one uses `Node2{T}` with `undef` as null indicator.

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [January 23, 2022, 12:04pm UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/18 "2022-01-23T12:04:24Z")

</div>

Whoops, I didn’t see the code box could scroll down 🙂  
Anyway, if you solve the type instability by specifying the type of the array, the union type is faster for me:

```julia
julia> include("foo.jl")
WARNING: replacing module Foo.
  11.524 μs (1006 allocations: 53.09 KiB)
  18.020 μs (1006 allocations: 53.09 KiB)

```

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 23, 2022, 12:09pm UTC](https://discourse.julialang.org/t/best-way-to-store-a-sparse-unbalanced-and-not-complete-binary-tree/74902/19 "2022-01-23T12:09:43Z")

</div>

> [@jakobnissen](#):
>
> Anyway, if you solve the type instability by specifying the type of the array, the union type is faster for me

Yes, but this is partly the point: with `Union{Nothing,T}` you sometimes have to care about type instabilities, see [https://github.com/JuliaCollections/DataStructures.jl/pull/766](https://github.com/JuliaCollections/DataStructures.jl/pull/766) for more examples.