Splay ツリーで最悪のシーケンスを実行してみます。
しかし、Splay-tree で最悪の場合のシーケンスは何ですか? また、ツリーに挿入されたキーを指定して、このシーケンスを簡単に計算する方法はありますか?
これで私を助けることができますか？
1 に答える
0
誰かが私を訂正しない限り、私は「スプレー ツリー上で最悪の場合の一連の操作がどのようなものであるか、その場合の複雑さがどのようなものであるかを実際に知っている人は誰もいない」と言うことにします。
スプレー ツリーの効率に関する多くの結果はわかっていますが、スプレー ツリーの時間の複雑さを制限する方法については、実際にはあまりわかっていません。動的最適性予想と呼ばれる予想があります。これは、最悪の場合、スプレイ ツリーでの十分に長い一連の操作は、そのシリーズで可能な限り最良の自己調整二分探索ツリーよりも一定の時間以上かかることはないというものです。操作の。これを証明しようとしている課題の 1 つは、すべての入力に対して可能な限り最高の BST のコストを決定する方法を実際に誰も知らないことです。もう 1 つは、さまざまな入力の組み合わせの実行時間の上限をスプレイ ツリーで見つけるのが難しいことです。現時点では、スプレイ ツリーを両端キューとして扱うのに O(n) の時間がかかるかどうかは誰にもわかりません。
お役に立てれば！
于 2015-07-30T16:11:58.943 に答える