AVL树管理
我有一些关于 AVL 的问题，假设我创建了一些整数的 avl 树，我需要如何管理插入到我的树中才能取出最长的数字序列，（插入的复杂度必须为 O(logn ))，例如：
_ 10 _
_ 7 _ _ 12 _
6 8
在这种情况下，最长的序列将为 6,7,8，因此在我的函数 void sequence(int* low, int* high) 中，我将执行 *low = 6，*high = 8...
函数（序列）的复杂性必须为 O(1)
提前感谢您的任何想法
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, int* high) I'll do *low = 6, *high = 8...
comlexity of the function(sequence) have to be O(1)
thanks in advance for any idea
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
实际上，如果您构建一个间隔列表或类似的东西，然后将其组件存储在 AVL 树中，您可能会做得很好。问题是你不仅仅想要一个给定的序列，你想要最长的序列。更准确地说，最长的词法上紧邻的键*。奇怪的是，我认为如果不使用自定义指标来构建 AVL 树，这是相当困难的。我想如果你的建立在间隔列表上的 AVL 树的比较器是 f(间隔长度)，你可以在 o(logn) 中得到它，或者如果你的 AVL 实现有快速的 max\min 的话可能会更快。
非常抱歉，我希望能提供更多帮助，但事实上我们必须使用 AVL 树，这有点令人不安。我想知道是否有一个可以涉及子树的技巧，但我只是看不出有什么好方法可以在不进行太多预处理的情况下实现这种方法 o(1) ，以至于成为一个笑话。带有布隆过滤器的东西可能有用吗？
*
一些总排序可以创建类似的运行，但并不是所有的排序都在它们的……嗯……相空间中具有有意义的直接邻接概念，我猜？**
**我平庸的正规教育现在真的让我很痛苦。
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.
基本的插入和插入AVL 树中的旋转保证了接近 O(logn) 的性能。
来到问题的第二部分，要找到序列的“复杂性”，您首先需要找到（或遍历到）AVL树中的“低”元素，它本身最多会花费您O(logn) 。
所以 O(1) sequence() 的复杂度是不可能的......如果 O(1) 是必须的，那么也许 AVL 树不是你的数据结构。
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.