1

AVL についていくつか質問があります。整数の avl ツリーを作成したと仮定しましょう。最長の数列を取り出すために、ツリーへの挿入をどのように管理する必要がありますか (挿入は複雑さ 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（区間の長さ）だった場合、o（logn）で取得できます。また、AVL実装のmax \ minが速い場合は、より高速になります。

大変申し訳ありませんが、もっと助けてもらいたいと思っていましたが、AVLツリーを使わなければならないという事実は少し厄介です。サブツリーを含むトリックを引っ張ることができるかどうか疑問に思っていますが、冗談になるほど多くの前処理を行わずに、そのようなアプローチをo（1）にする良い方法はありません。ブルームフィルター付きのものが機能する可能性がありますか？

*いくつかの合計順序は、同様の実行を作成できますが、すべてがそれらの...まあ...位相空間での即時隣接の意味のある概念を持っているわけではありませんか？**

**私のつまらない正式な教育は、今のところ本当に私を悩ませています。

于 2010-11-24T22:52:36.143 に答える
1

AVL ツリーの基本的な挿入と回転により、O(logn) に近いパフォーマンスが保証されます。

質問の2番目の部分に来て、シーケンスの「複雑さ」を見つけるには、最初にAVLツリーの「低い」要素を見つける（またはトラバースする）必要があります.AT MOST O（logn） .

したがって、O(1) sequence() の複雑さは窓の外にあります... O(1) が必須である場合、おそらく AVL ツリーはここのデータ構造ではありません。

于 2010-11-24T14:01:46.237 に答える