Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time?
I recently implemented a rope data structure in Lua as an AVL tree.
However, I realized a since the ropes are not interned, they can't be used efficiently as keys in a dictionary. (Lua walks over all new strings made by concatenation or slicing in order to intern them, making these $\Theta(n)$ operations, but guarantees fast dictionary lookup by only comparing addresses)
Can AVL tree ropes (or another type of balanced tree) be interned in a similar fashion in better than $O(n)$ time? Can fast interning be proved impossible?
Below is what I have thought of so far. I haven't found any resources about interning non-string data structures.
Hashing: You can efficiently determine the hash value of a concatenation or a slice with extra bookkeeping for some hash schemes (like Java's). However, you can't guarantee there are no collisions in these hashes (and actually their slicability/concateability can make them very easy to attack).
Normalizing: There are many different shapes that AVL trees with identical contents can take on. I could try to pick one special form for each size and designate it as the "canonical" form. When new trees are made when concatenating or slicing, in addition to balancing the tree, we reshape it to its canonical form. Naively this should not be efficient, because the vast majority of forms for a given size are $O(n)$ edits away from any particular canonical form. However, maybe if all subtrees are given some particular form, canonicalizing can be made efficient.
I tried the obvious perfectly-balanced tree as the canonical shape, but I couldn't make an efficient way to concatenate these. Another version I considered was "as left leaning as possible" but this had the same result.