I'm working on an implementation of a data structure that needs a tree-like data structure for accelerating look-ups.
The interesting part about this data structure is that the only operations on the AVL Tree are inserting and removing sequential integers in a stack-like fashion,
Insert 0, 1, 2 Delete 2, 1 Insert 1, 2, 3 etc.
I have been using this site to gain some intuition about the problem.
AVL Trees seem to behave wonderfully for this situation, and I'd like to see how far I can take it. Specifically, I have the following conjectures that I would like proven/disproven:
- Inserting sequential keys results in zero or one left rotations.
- Deleting sequential keys results in zero or one right rotations.
- Given only the number of nodes in the tree and the next operation (insert or delete), we can determine whether a rotation needs to be performed, either a single-left or single-right, along with the key of the node that needs to be rotated in O(1) time with O(1) extra space.
If these turn out to be true, height information doesn't have to be stored/updated for such a tree, making AVL Trees optimal for this particular application. I'm pretty sure that #1 and #2 are true, but #3 is the one I'm stumped on.
Note that this intended to solve the same problem as building and maintaining an optimal search tree given sorted inputs. If a simpler solution exists than thinking about the problem in terms of AVL Trees, I would be interested in that, as well. However, the implementations I have seen so far seem more limited and cumbersome, since they rely on a finalization step.
Also note that for #3, knowing how many levels up a rotation needs to happen is equally (perhaps even more) valuable.