2
$\begingroup$

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,

e.g.

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:

  1. Inserting sequential keys results in zero or one left rotations.
  2. Deleting sequential keys results in zero or one right rotations.
  3. 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.

$\endgroup$
  • $\begingroup$ Why not use a stack + a hash table for lookups? When you push on the stack, you add it to the hash table; when you pop from the stack, you remove it from the hash table. That will be a simpler data structure and might well be faster too. $\endgroup$ – D.W. May 1 at 11:06
  • $\begingroup$ Maybe it's also looking into a splay tree? $\endgroup$ – BearAqua May 1 at 13:43
  • $\begingroup$ @D.W. That's actually significantly more complicated. Also, the primary purpose of the data structure is to avoid array doubling. For this particular use case, an AVL Tree with predictable rotations will be significantly faster and take less memory. I would also add that this is a very practical data structure that cares about constant factors. $\endgroup$ – rationalcoder May 1 at 16:55
  • $\begingroup$ @bearaqua I have investigated splay trees, and the worst case is unacceptable for my use case. $\endgroup$ – rationalcoder May 1 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.