@pervognsen@mastodon.social
I'd be interesting if you could recommend a persistent data structure for a hierarchical string tree. By hierarchical string tree I mean a tree where every non-leaf node can contain an arbitrary number of children and the leaves are strings. The keys are also strings.Textually represented - something like this I mean.
{
"foo": "bar",
"baz": {
"a": {
"zz" : "xx",
"q" : {
"a" : "a"
}
}
},
"test" : "blah"
}
For a non-persistent data structure you can use Left-Child Right-Sibling trees but those seem inappropriate for persistent DS as you would be doing alot of node copying.
@blackeggs@infosec.exchange I would look at some kind of weight-balanced trees where you do amortized rebuilds of complete subtrees when they become too unbalanced. Are you familiar? You'd have to make sure you avoid the time-complexity trap when combining amortization and persistence a la Okasaki.
@pervognsen@mastodon.social Not familiar, I will have to check it out ! To clarify this isn't a search tree there is no ordering on the keys its just a hierarchy that stores string data.
@blackeggs@infosec.exchange Well, they're a very general technique and you'd have to adapt it. I'm assuming you don't want a flat key-value array per node since you want to support nodes with large/unbounded fanout?
@blackeggs@infosec.exchange The point is that you're dealing with a general tree-like structure just to represent a single node in a persistence-friendly way, i.e. you're essentially composing multiple persistent data structures and you should probably express your code in that way, and for that part you need balanced or radix trees or something like that.
@pervognsen@mastodon.social arbritrary children yeah, and where you can insert/delete/modify at any position of the children.
mistymntncop