Splay樹：最壞情況序列

Question

我想嘗試嘗試在Splay樹上執行最壞情況序列。

但是Splay-trees的最壞情況序列是什麼？ 有沒有什麼方法可以很容易地計算出這個序列給予插入樹中的鍵？

任何可以幫助我呢？

Answer 1

除非有人糾正我，否則我會繼續說：「沒有人真正知道最壞情況下的一系列操作是在展開樹上還是在這種情況下的複雜性。」

雖然我們知道許多關於斜張樹效率的結果，但我們實際上並不知道如何限制斜張樹的時間複雜度。有一種叫做的動態最優性猜想這個猜想說，在最糟糕的情況下，一個顯式樹上任何足夠長的一系列操作所花費的時間不會超過最佳可能的自我調整二叉搜索樹那一系列的行動。我們在試圖證明這一點時面臨的挑戰之一是，沒有人真正知道如何確定所有投入的最佳BST成本。另一個問題是，尋找各種輸入組合的運行時間來展示樹的上限是困難的 - 到目前爲止，沒有人知道是否需要花費時間O（n）將一棵樹展開爲一個deque！

希望這會有所幫助！