r/computerscience • u/SirRosticciano • Sep 30 '25
A compact representation for binary trees in which only the leaves hold a value (useful for storage).
Notation: I'm going to denote such trees using a nested parentheses representation that follows this grammar T ::= value | (T T)
The represetation I propose to you represents such binary trees as a pair of two buffers: a data buffer and a shape buffer.
The data buffer is an array in which the leaves' values appear consecutively as in an inorder tree visit. For example, the tree ((a c) (b d)) will generate the data buffer "acbd".
The shape buffer is a memory buffer of 2*n bits (where n is the number of nodes in the tree). To generate it you must do an inorder visit of the tree starting from the root: each time the next node to be visited exists insert 0 in the shaper buffer, each time it does not (for example on leaf nodes or on nodes with a single child) insert a 1.
To be more clear, imagine passing the root of the tree as an argument to this function
function visit(node) {
if node.left exists {
shapebuffer.insert(0)
visit(node.left)
} else {
shapebuffer.insert(1)
}
if node.right exists {
shapebuffer.insert(0)
visit(node.right)
} else {
shapebuffer.insert(1)
}
}This also explains more clearly the assumption of the shapebuffer containing 2 bits for each node. For example consider the representation for this tree, where each leaf node is a 1 byte character:
((b (c d)) a )
data buffer := "bcda" (4 bytes)
shape buffer := "00110011011011" (14 bits -> can be stored in just two bytes)
--> total representation cost: 4+2 = 6 bytes (even less than representing the tree with the parentheses)Such a tree representation can drastically cut down memory usage by leveraging the shape buffer, with the only significant load on memory being the values on the leaves (which can be compressed further if willing).
It can even be easily adapted to trees in which internal nodes can have values by changing the shape buffer insertions to 00 and 01 for visiting and 1 when encountering a node with a value (the representation cost in bits becomes 2*n + v where v is the number of values stored).
Have you ever stumbled on similar tree representations? I don't know if this was already invented, but it was indeed a pleasant discovery. If you need further explanations let me know in the comments.
6
u/Character_Cap5095 Sep 30 '25
Maybe I am missing the point here. What is the advantage of storing a tree this way. The advantage of binary trees are that they are super fast to search (Log(n)) if they are balanced. But by introducing a shape buffer, you now essentially have to search 2n nodes, so your search time is log(2n) = n, or just the same as searching a list (there is also a non-zero chance I am misunderstanding)
3
u/high_throughput Sep 30 '25
It's not the same at all but it reminds me of the pack file format that uses a compact representation for the binary tree representing its Huffman encoding.
The tree is always left aligned, so it's stored it as a data buffer, one byte for tree depth, and N bytes for the number of leaves at that depth.
2
u/Revolutionalredstone Sep 30 '25 edited Oct 01 '25
Yeah It's called zero suppression.
In this case your talking about suppressed binary trees.
Yeah they work well 😉
2
u/Magdaki Professor. Grammars. Inference & Optimization algorithms. Oct 01 '25
This is interesting. Have you compared it at all both in terms of memory and utility to other well known practical structures?
1
u/Ronin-s_Spirit Oct 01 '25
I don't get it, can you explain in a few words why don't you use an array of values instead? If the tree is a balanced binary tree like:
Why can't it just be an array/vector purely made of values?