I expect it is—I haven’t looked. But AIUI the usual way of making this sort of structure persistent amounts to remembering a log of everything you did, so the requirement for more rotations means that a persistent AVL tree ends up less space-efficient than a persistent red-black tree. Something like that, anyway, I haven’t attempted to build either.
In Haskell, or any GC language really, you don’t need a log to make a tree data structure persistent. Just always allocate new nodes instead of changing old ones, so all operations will return a new version of the whole tree. That’s O(log n) allocations per operation, because most subtrees can be shared between the old and new versions, only the nodes along one path down the tree need to be new. Anyone who kept a reference to an old version’s root can keep accessing the entire old version, because nodes never change. And if nobody kept a reference, GC picks it up. That way it’s also easy to have branching history, which seems impossible with a log.
Hm, my implementation of AVL trees seems persistent enough?
I expect it is—I haven’t looked. But AIUI the usual way of making this sort of structure persistent amounts to remembering a log of everything you did, so the requirement for more rotations means that a persistent AVL tree ends up less space-efficient than a persistent red-black tree. Something like that, anyway, I haven’t attempted to build either.
In Haskell, or any GC language really, you don’t need a log to make a tree data structure persistent. Just always allocate new nodes instead of changing old ones, so all operations will return a new version of the whole tree. That’s O(log n) allocations per operation, because most subtrees can be shared between the old and new versions, only the nodes along one path down the tree need to be new. Anyone who kept a reference to an old version’s root can keep accessing the entire old version, because nodes never change. And if nobody kept a reference, GC picks it up. That way it’s also easy to have branching history, which seems impossible with a log.