1

我有一些关于 AVL 的问题，假设我创建了一些整数的 avl-tree，我需要如何管理插入到我的树中才能取出最长的数字序列，（插入必须具有复杂度 O(logn ））， 例如：

          _   10   _
   _  7 _                _  12  _
6          8

在这种情况下，最长的序列将是 6,7,8 所以在我的函数中void sequence(int* low, int* high)我会做 * low = 6, *high = 8...

函数（序列）的复杂性必须是 O(1)

提前感谢您的任何想法

4

2 回答 2

2

实际上，如果您构建一个区间列表或类似的东西，然后将它的组件存储在 AVL 树中，您可能会做得很好。问题是您不仅想要给定的序列，还想要最长的序列。更准确地说，最长的词法紧邻键*。奇怪的是，如果不使用自定义指标来构建您的 AVL 树，我认为这很难。我猜如果您在区间列表上构建的 AVL 树的比较器是 f(length-of-interval)，那么您可以在 o(logn) 中获得它，或者如果您的 AVL 实现具有快速的 max\min，则可能更快。

非常抱歉，我希望能得到更多帮助，但我们必须使用 AVL 树这一事实有点令人不安。我想知道是否有一个可以涉及子树的技巧，但我只是看到没有好的方法可以在没有太多预处理的情况下制作这种方法 o(1) 以至于成为一个笑话。带有布隆过滤器的东西可能有用吗？

* 一些总排序可以创建类似的运行，但并非所有排序都在它们的......嗯......相空间中具有有意义的直接邻接概念？我猜？**

**我乏善可陈的正规教育现在真的让我很痛苦。

于 2010-11-24T22:52:36.143 回答
1

AVL 树中的基本插入和旋转保证了接近 O(logn) 的性能。

来到问题的第二部分，要找到序列的“复杂性”，首先需要找到（或遍历）AVL 树中的“低”元素，它本身将带你最多 O(logn) .

所以 O(1) sequence() 复杂性超出了窗口......如果 O(1) 是必须的，那么 AVL 树可能不是你的数据结构。

于 2010-11-24T14:01:46.237 回答