On Wed, 23 May 2012 17:54:42 -0400, Roman D. Boiko <r...@d-coding.com> wrote:
On Wednesday, 23 May 2012 at 19:51:02 UTC, Steven Schveighoffer wrote:
If you need a sorted tree structure that supports sharing immutable
state, you likely have to find a different algorithm than redblack,
since adding nodes can modify the tree structure via rotates.
-Steve
I don't need to invent here, and it is definitely feasible. Okasaki
provided efficient algorithm for inserting nodes, and, IIRC, rotations
(not for deleting, though). But OCaml doesn't map to D easily (neither
does Haskel, I think).
I looked up how it could be done, the one thing I was not sure of was the
parent node. If you can have multiple references to the same subtree, how
do you keep track of the parents. But if you only are concerned about the
ancestry of a single node, you can dynamically determine the line in
O(lgn) time, and use that for the running of the redblack algorithm.
I'm not sure how efficient it would be.
-Steve
