AVL tree management

I have some question about AVL, lets assume I created some avl-tree of integers, how do I need to manage insertion into my tree to be able to take out the longest sequence of numbers, (insertion have to be with complexity O(logn)), for example:

          _   10   _
   _  7 _                _  12  _
6          8

in this case the longest sequence will be 6,7,8 so in my function void sequence(int* low, 开发者_如何学JAVAint* high) I'll do *low = 6, *high = 8...

comlexity of the function(sequence) have to be O(1)

thanks in advance for any idea

Actually, if you build an interval list or something very-like-it, then store the components of it in an AVL tree, you could probably do okay. The thing is that you don't just want a given sequence, you want longest sequence. Longest run of lexically immediately adjacent keys*, to be more exact. Which, curiously, is quite hard I think without bashing up a custom metric to build your AVL tree on. I guess if your comparator for the AVL tree built on the interval list was f(length-of-interval), you could get it in o(logn) or maybe faster if your AVL implementation has fast max\min.

I'm terribly sorry, I was hoping to be more help, but the fact that we have to use an AVL tree is a little troubling. I'm wondering if there's a trick that one could pull involving sub-trees, but I'm simply seeing no good way to make such an approach o(1) without so much preprocessing as to be a joke. Something with bloom filters might work?

* Some total orderings can create similar runs, but not all have a meaningful concept of immediate adjacency in their... well... phase space I guess?**

**My lackluster formal education is really biting me right about now.

The basic insertion & rotation in AVL Trees guarantees close to O(logn) performance.

Coming to the 2nd part of your question, to find the "complexity" of your sequence, you first need to find (or traverse to) the "low" element in your AVL Tree, that itself will take you AT MOST O(logn).

So O(1) sequence() complexity is out of the window... If O(1) is a must then maybe AVL tree is not your data structure here.