Optimal datastructure for a sparse binary tree?

I have a large (deep) binary tree, but is it sparse: one in a thousands nodes are non nil. What datastructure should I use for it ?

Have you tried using a simple map instead?

I have too much data for a map (~1_000_000_000_000)

In that case, I think we need more information about the problem: What data are you storing in a trillion separate nodes? What are you doing with these nodes? Without that, I don’t really have any ideas other than maybe try implementing an m-ary tree to decrease the depth.

an m-ary tree is a cool, and a very powerfull datastructure. However, it is only efficient in a specific case of problems.

With my data, the lowest levels will be sparsely populated (thus it would be wasteful to store nil poitners there) while the upper levels would have all their children.

The data is numbers (complex numbers) and is randomly disributed. My hope is that I can figure out some sort of mathematical function (an overtrained neural net perhaps ?) that I build once then querry “does this new number X belong to my original set S ?”.

Any ideas on how I can store a sparse subset (several trillion) of all possible complex numbers (complex as in Golang’s complex datatype), but this sparse subset is too large itself for a map or slice ?

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.