Looking for / building a generic tree data structure library

[al2o3cr]

@sschuldenzucker

I could use a digraph from Erlang but it’s actually too flexible for my use case and would require a wrapper around it to make sure nobody’s creating a loop.

Not sure I’m following the problem here - you can pass :acyclic to :digraph.new/1 and the library will handle enforcing that restriction.

@sschuldenzucker

In particular 5. seems hard to satisfy with the libraries I found.

I only see 4 numbered bullet points, did something get lost in editing?

@sschuldenzucker

The whole thing should be “generic”

“Generic” is hard. Different implementations are going to have seriously different performance (both time and space) for specific operations.

For instance, a tree implemented as a closure table can answer queries like “what are all the descendants of this node” very efficiently. But moving a subtree in that implementation is very slow, because it needs to touch many rows for each element of the subtree.

An adjacency-list representation (aka “put a parent_id column on the record”) has the opposite properties: moving an entire subtree only needs to update the parent_id on the subtree’s root, but checking for descendants requires recursive CTEs or other SQL trickery.