データ構造におけるスプレー木の最適性
動的最適性予想
スプレー木の証明された性能保証に加えて、大きな関心を持った証明されていない推測があります。動的最適性予想はこの予想を示します。 Bなどの任意の二分探索木アルゴリズムがd（y）+1のコストでルートからyへのパスをトラバースすることによって要素yにアクセスし、アクセス間で1回のコストでツリー内の任意の回転を行うことができます。回転。 Bがアクセスのシーケンスを実行するためのコストをB（s）とします。その場合、スプレーツリーが同じアクセスを実行するためのコストはO [n + B（s）]です。
証明されていない動的最適性予想の結果は非常にたくさんあります
トラバーサル予想 同じ要素が2つのスプレーツリーt1とt2に含まれています。事前順序（つまり、深さ優先探索順序）でt2の要素にアクセスすることによって取得されたシーケンスは、sと見なされます。 t1で一連のアクセスを実行するための全コストはO（n）です。
Deque予想 et p個の両端キュー操作（プッシュ、ポップ、インジェクト、イジェクト）のシーケンスが定義されています。その場合、スプレーツリーでシーケンスを実行するコストはO（p + n）です。
分割予想 et sは、スプレーツリーの要素の任意の順列です。その場合、順序sの要素を削除するためのコストはO（n）です。
-
データ構造内の高さが制限されたハフマンツリー
高さ制限または深さ制限のハフマンツリーの図を以下に示します ツリーの深さの制限は、ほとんどの実際のハフマンの実装が対処しなければならない重要な問題です。 ハフマン構造は高さや深さを制限しません。もしそうなら、それが「最適」である可能性はありません。確かに、ハフマンツリーの最大の深さはフィボナッチ数列によって制限されますが、それは必要以上の深さのための十分な余地を残します。 ハフマンツリーの深さを制限する理由は何ですか？高速ハフマンデコーダーはルックアップテーブルを実装します。メモリコストを軽減するために複数のテーブルレベルを実装することは可能ですが、Huff0などの非常に高速なデコ
-
データ構造の仮想ツリーでのスプレー
仮想ツリーでは、一部のエッジは実線として扱われ、一部は破線として扱われます。通常のスプレイは、堅い木でのみ実行されます。仮想ツリーのノードyで表示するには、次の方法を実装します。 アルゴリズムは、パスごとに1回ずつ、ツリーを3回調べ、それを変更します。最初のパスでは、ノードyから開始して、ソリッドツリーのみでスプレイすることにより、yからツリー全体のルートへのパスが破線になります。このパスは、スプライシングによって確実に作成されます。ノードyでの最後のスプレイにより、yがツリーのルートになります。非公式ではありませんが、アルゴリズムは次のように説明されています Splay（y）のアルゴリズ