mistymntncop@blackeggs@infosec.exchange
@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.
Per Vognsen@pervognsen@mastodon.social
@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.