Each position in the table contains an AVL tree. Now, insertion and deletion work fine, but the problem comes with the deletion. Suppose I have this:
[0]: a0 b0 c0
[1]: d0 e0 f0
[2]: g2 h0 i0
The number indicates that the associated elements have collided, so they have been moved to the other positions by the probing. Now, suppose I'd like to delete e0. The problem is that I have to keep the search working, so I'd have to move h0 and/or i0. This is how I'm thinking of doing it:
The search algorithm stops once it finds an empty AVL node. If it finds just a node marked as unused, it keeps going. The next time an insertion is performed in that AVL tree, if an unused node is found, it is deleted and a new node is inserted.
I can't find anything wrong with this, but I've already tried other ideas and they failed for one reason or the other, so tell me what you think of it. Any other ideas are welcome.
Also, I'm not doing this 'cause I want to or anything. It's an assignment, so I have to do it with these structures.