スプレーツリー

スプレー木は、最近アクセスした要素にすぐに再度アクセスできるという特性を持つ二分探索木です。自己バランス二分探索木と同様に、スプレー木は挿入、検索、削除などの基本操作をO (log n )の償却時間で実行します。不均一なランダム分布から抽出されたランダム アクセス パターンの場合、償却時間はアクセス パターンのエントロピーに比例して対数よりも速くなります。また、多くの非ランダム操作パターンの場合、スプレー木はパターンの事前知識を必要とせずに、対数よりも短い時間で実行できます。証明されていない動的最適性仮説によると、すべてのアクセス パターンでのスプレー木のパフォーマンスは、他の自己調整二分探索木 (そのパターンに適合するように選択されたものも含む) で達成できる最高のパフォーマンスの定数倍以内です。スプレー木は、1985 年にDaniel SleatorとRobert Tarjanによって発明されました。 ^[1]

バイナリ検索ツリーのすべての通常の操作は、スプレイングと呼ばれる 1 つの基本操作と組み合わされています。特定の要素のツリーをスプレイングすると、その要素がツリーのルートに配置されるようにツリーが再配置されます。基本的な検索操作でこれを行う 1 つの方法は、まず問題の要素に対して標準的なバイナリ ツリー検索を実行し、次に特定の方法でツリーを回転させて要素を最上部に移動することです。または、トップダウン アルゴリズムを使用して、検索とツリーの再編成を 1 つのフェーズに組み合わせることもできます。

スプレー ツリーの優れたパフォーマンスは、頻繁にアクセスされるノードがより速くアクセスできるルートに近づくという点で自己最適化されるという事実に依存します。最悪のケースの高さは、可能性は低いですが O( n ) で、平均は O(log n ) です。頻繁に使用されるノードをルートの近くに置くことは、多くの実用的なアプリケーションで利点となり (参照の局所性も参照)、特にキャッシュやガベージ コレクションアルゴリズムを実装する場合に役立ちます。

利点は次のとおりです:

• 同等のパフォーマンス：平均的なケースのパフォーマンスは他のツリーと同等に効率的です。^[3]
• メモリフットプリントが小さい: スプレーツリーは簿記データを保存する必要はありません。

スプレイツリーの最も重大な欠点は、スプレイツリーの高さが線形になる可能性があることです。^{[2] : 1}たとえば、 n個の要素 すべてに非減少順でアクセスした後は、このようになります。ツリーの高さは最悪の場合のアクセス時間に対応するため、1 回の操作の実際のコストが高くなる場合があります。ただし、この最悪の場合の償却アクセスコストは対数で、O(log n ) です。また、ランダム化バリアントを使用することで、予想されるアクセスコストを O(log n )に削減できます。^[4]

スプレイ ツリーの表現は、読み取り専用でアクセスされた場合 (つまり、検索操作によってアクセスされた場合) でも変更される可能性があります。このため、マルチスレッド環境でのこのようなスプレイ ツリーの使用は複雑になります。特に、複数のスレッドが検索操作を同時に実行できる場合は、追加の管理が必要になります。このため、純粋に関数型のプログラミングでの一般的な使用には適していませんが、優先順位キューを実装するために限定的に使用することはできます。

最後に、アクセス パターンがランダムな場合、追加の拡散オーバーヘッドにより、それほど動的でない代替手段と比較して、コストに大きな定数要因が追加されます。

ノードxにアクセスすると、xに対してスプレー操作が実行され、 x がルートに移動します。スプレー操作は、 x をルートに近づけるスプレー ステップのシーケンスです。アクセスのたびに対象のノードに対してスプレー操作を実行すると、最近アクセスされたノードがルートの近くに保持され、ツリーはほぼバランスが保たれるため、必要な償却時間境界が提供されます。

それぞれのステップは、次の 3 つの要素に依存します。

• x が親ノードpの左の子か右の子か
• pが根であるかどうか、そうでない場合は
• pがその親g ( xの祖父母)の左の子か右の子か。

スプレイ ステップには 3 つのタイプがあり、それぞれに左利きと右利きの 2 つの対称的なバリエーションがあります。簡潔にするために、各タイプについてこれら 2 つのうちの 1 つだけを示します。(次の図では、円は対象のノードを示し、三角形は任意のサイズのサブツリーを示します。) スプレイ ステップには次の 3 つのタイプがあります。

ジグ ステップ:このステップは、 p がルートのときに実行されます。ツリーは、 xとp の間のエッジで回転します。ジグ ステップはパリティの問題に対処するために存在し、スプレイ操作の最後のステップとしてのみ実行され、操作の開始時にx の深さが奇数である場合にのみ実行されます。

ジグジグステップ:このステップは、p がルートではなく、xとp が両方とも右の子であるか、両方とも左の子である場合に実行されます。下の図は、xとp が両方とも左の子である場合を示しています。ツリーは、pとその親gを結ぶエッジで回転され、次にxとpを結ぶエッジで回転されます。ジグジグステップは、スプレイツリーが導入される前にアレンとマンロー^{[5]によって導入された}ルートへの回転方法とスプレイツリーを区別する唯一のものです。

ジグザグ ステップ:このステップは、p がルートではなく、xが右の子でp が左の子であるか、その逆 ( xが左、pが右) の場合に実行されます。ツリーはpとx の間のエッジで回転し、次にxとgの間の結果のエッジで回転します。

S のすべての要素が T の要素よりも小さい 2 つのツリー S と T が与えられた場合、次の手順を使用してそれらを 1 つのツリーに結合できます。

• S 内の最大のアイテムを広げます。これで、このアイテムは S のルートにあり、右の子は null になります。
• 新しいルートの右の子を T に設定します。

ツリーと要素xが与えられた場合、 2 つの新しいツリーを返します。1 つはx以下のすべての要素を含み、もう 1 つはxより大きいすべての要素を含みます。これは次のように実行できます。

• x を広げます。これでルートになったので、左側のツリーにはxより小さいすべての要素が含まれ、右側のツリーにはxより大きいすべての要素が含まれます。
• 右側のサブツリーをツリーの残りの部分から分割します。

スプレーツリーに 値x を挿入するには:

• 通常の二分探索木と同様にx を挿入します。
• xに対してスプレイを実行します。

その結果、新しく挿入されたノードx がツリーのルートになります。

あるいは:

• 分割操作を使用して、ツリーをxの値で2 つのサブツリー (S と T) に分割します。
• xがルート、S がその左のサブツリー、T がその右のサブツリーである新しいツリーを作成します。

ノードx を削除するには、バイナリ検索ツリーと同じ方法を使用します。

• x に2 人の子供がいる場合:
  • その値を、左側のサブツリーの右端のノード (順序どおりの先行ノード) または右側のサブツリーの左端のノード (順序どおりの後続ノード) の値と交換します。
  • 代わりにそのノードを削除してください。

このようにして、削除は、0 個または 1 個の子を持つノードを削除する問題に縮小されます。バイナリ検索ツリーとは異なり、削除後のスプレー ツリーでは、削除されたノードの親をツリーの最上部にスプレーします。

あるいは:

• 削除するノードは最初に広げられ、つまりツリーのルートに移動されてから削除されます。ツリーには 2 つのサブツリーが残ります。
• 次に、2 つのサブツリーは「結合」操作を使用して結合されます。

前述のように、スプレイングは、ノードのアクセス パスを 2 回目にボトムアップでパスするときに実行されます。最初のパスでアクセス パスを記録しておき、2 回目のパスで使用することもできますが、アクセス操作中に余分なスペースが必要になります。別の方法としては、すべてのノードに親ポインターを保持する方法があります。これにより、アクセス操作中に余分なスペースが不要になりますが、それらのポインターを更新する必要があるため、全体的な時間効率が低下する可能性があります。^[1]

使用できるもう 1 つの方法は、2 回目のパスを作成する代わりに、アクセス パスを下る途中でツリーを再構築できるという議論に基づいています。このトップダウンのスプレイ ルーチンでは、左ツリー、右ツリー、中央ツリーの 3 つのノード セットを使用します。最初の 2 つには、それぞれ現在のアイテムより小さいか大きいことがわかっている元のツリーのすべてのアイテムが含まれます。中央ツリーは、現在のノードをルートとするサブツリーで構成されます。これらの 3 つのセットは、スプレイ操作を抑制しながらアクセス パスを下って更新されます。もう 1 つの方法であるセミスプレイは、ジグジグ ケースを変更して、すべての操作で実行される再構築の量を減らします。^{[1] [6]}

以下は、C++ でのスプレー ツリーの実装です。この実装では、ツリーの各ノードを表すためにポインターを使用します。この実装は、ボトムアップ スプレー バージョンに基づいており、スプレー ツリーで 2 番目の削除方法を使用します。また、上記の定義とは異なり、この C++ バージョンでは、検索時にツリーをスプレーしません。挿入と削除時にのみスプレーするため、検索操作には線形の時間計算量があります。

#include <機能> 

#ifndef SPLAY_TREE 
#SPLAY_TREE を定義します

テンプレート< typename T 、typename Comp = std :: less < T >>クラスsplay_tree { private : Comp comp ; unsigned long p_size ;構造体node { node * left 、* right ; node * parent ; T key ; node ( const T & init = T ()) : left ( nullptr )、right ( nullptr )、parent ( nullptr )、key ( init ) { } ~ node () {     
  

   
    
  
    
      
     
     
               
     

    } 
} * root ; void left_rotate ( node * x ) { node * y = x -> right ; if ( y ) { x -> right = y -> left ; if ( y -> left ) y -> left -> parent = x ; y -> parent = x -> parent ; } if ( ! x -> parent ) root = y ; else if ( x == x -> parent -> left ) x -> parent -> left = y ; else x -> parent -> right = y ; if ( y ) y -> left = x ; x -> parent = y ; } void right_rotate ( node * x ) { node * y = x -> left ; if ( y ) { x -> left = y -> right ; if ( y -> right ) y -> right -> parent = x ; y -> parent = x -> parent ; } if ( ! x -> parent ) root = y ; else if ( x == x -> parent -> left ) x -> parent -> left = y ; else x ->   
  
     
       
      
        
          
        
    
    
        
           
       
        
      
  
  
     
       
      
        
          
        
    
        
           
     parent -> right = y ; if ( y ) y -> right = x ; x -> parent = y ; } void splay ( node * x ) { while ( x -> parent ) { if ( !x -> parent -> parent ) { if ( x -> parent -> left == x ) right_rotate ( x -> parent ); else left_rotate ( x -> parent ); } else if ( x -> parent -> left == x && x -> parent -> parent -> left == x -> parent ) { right_rotate ( x -> parent -> parent ); right_rotate ( x -> parent ); } else if ( x -> parent -> right == x && x -> parent -> parent -> right == x -> parent ) { left_rotate ( x -> parent -> parent ); left_rotate ( x -> parent ); } else if ( x -> parent -> left == x && x -> parent -> parent -> right == x -> parent ) { right_rotate ( x -> parent ); left_rotate ( x -> parent ); } else {  
        
      
  
  
     
      
        
            
         
                
        
        
                
        
        
                
        
        
        
        left_rotate ( x -> parent ); 
right_rotate ( x -> parent ); } } } void replace ( node * u , node * v ) { if ( ! u -> parent ) root = v ; else if ( u == u -> parent -> left ) u -> parent -> left = v ; else u -> parent -> right = v ; if ( v ) v -> parent = u -> parent ; } node * subtree_minimum ( node * u ) { while ( u -> left ) u = u -> left ; return u ; } node * subtree_maximum ( node * u ) { while ( u -> right ) u = u -> right ; return u ; } public : splay_tree () : root ( nullptr ), p_size ( 0 ) { } void insert ( const T & key ) { node * z = root ; node * p = nullptr ; while ( z ) { p = z ; if ( comp ( z -> key , key )) z = z -> right ; else z = z ->        
      
    
  
  
       
        
           
       
        
  
  
     
        
     
  
  
     
        
     
  

       
  
      
       
       
    
      
        
           
         left ; 
} z = new node ( key ); z -> parent = p ; if ( ! p ) root = z ; else if ( comp ( p -> key , z -> key )) p -> right = z ; else p -> left = z ; splay ( z ); p_size ++ ; } node * find ( const T & key ) { node * z = root ; while ( z ) { if ( comp ( z -> key , key )) z = z -> right ; else if ( comp ( key , z -> key )) z = z -> left ; else return z ; } return nullptr ; } void erase ( const T & key ) { node * z = find ( key ); if ( ! z ) return ; splay ( z ); if ( ! z -> left ) replace ( z , z -> right );そうでない場合、( ! z- > right ) replace ( z , z- > left );そうでない場合、node * y = subtree_minimum ( z- > right ); if ( y- >    
    
       
      
    
        
          
       
    
    
    
  
  
      
       
      
           
            
        
    
     
  
        
      
       
      
    
    
    
       
        
     
         
       parent != z ) { replace ( y , y -> right ); y -> right = z -> right ; y -> right -> parent = y ; } replace ( z , y ); y -> left = z -> left ; y -> left -> parent = y ; } delete z ; p_size -- ; }   
         
          
          
      
       
        
        
    
    
     
    
  

/* //代替実装
    void erasing(const T &key) { 
        node *z = find(key); 
        if (!z) return; 
        splay(z);         node *s = z->left;         node *t = z->right;         delete z;         node *sMax = NULL;         if (s) {             s->parent = NULL;             sMax = subtree_maximum(s);             splay(sMax);             root = sMax;         }         if (t) {             if (s)                 sMax->right = t;             else                 root = t;             t->parent = sMax;         }         p_size--;     } */ const T & minimum () { return subtree_minimum ( root ) -> key ; } const T & maximum () { return subtree_maximum ( root ) -> key ; } bool empty () const { return root == nullptr ; } unsigned long size () const { return p_size ; } };        

        



        














        



  
        
        
  
          
         


#endif // SPLAY_TREE

静的スプレーツリーの単純な償却解析は、ポテンシャル法を使用して実行できます。定義:

• size( r ) = ノードrをルートとするサブツリー内のノードの数( rを含む)。
• ランク( r ) = log ₂ (サイズ( r ))。
• Φ = ツリー内のすべてのノードのランクの合計。

バランスの悪い木では Φ が高くなり、バランスの良い木では Φ が低くなる傾向があります。

ポテンシャル法を適用するには、まず ΔΦ (スプレイ操作によって生じるポテンシャルの変化) を計算します。各ケースを個別に確認します。操作後のランク関数を rank' で表します。x、p、g は回転操作の影響を受けるノードです (上の図を参照)。

あらゆる操作の償却コストは、ΔΦ と実際のコストの和です。ジグジグ操作やジグザグ操作の実際のコストは、2 回の回転が必要なので 2 です。したがって、

スプレー操作全体を合計すると、1 + 3(rank(root)−rank( x ))、つまり O(log n ) になります。これは、Zig 操作を最大で 1 回使用し、zig の償却コストが最大で 1+3(rank'( x )−rank( x ))であるためです。

したがって、 m 個の操作 のシーケンスの合計償却時間は次のようになります。

${\displaystyle T_{\mathrm {償却} }(m)=O(m\log n)}$

償却時間から実際の時間に移行するには、操作が行われる前の初期状態 (Φ _i ) からすべての操作が完了した後の最終状態 (Φ _f ) までの電位の減少を追加する必要があります。

${\displaystyle \Phi _{i}-\Phi _{f}=\sum _{x}{\mathrm {rank} _{i}(x)-\mathrm {rank} _{f}(x)} =O(n\log n)}$

ここで、ビッグO表記は、すべてのノードxに対して最小ランクが0であり、最大ランクがlog( n )であるという事実によって正当化されます。

これで、実際の時間を制限できるようになりました。

${\displaystyle T_{\mathrm {actual} }(m)=O(m\log n+n\log n)}$

上記の分析は次のように一般化できます。

• 各ノードrに重みw ( r )を割り当てます。
• size( r ) = ノードrをルートとするサブツリー内のノードの重みの合計( rを含む) と定義します。
• ランク( r )とΦを上記とまったく同じように定義します。

同じ分析が適用され、スプレー操作の償却コストは次のようになります。

${\displaystyle 1+3(\mathrm {ランク} (ルート)-\mathrm {ランク} (x))}$

ここで、W はすべての重みの合計です。

初期電位から最終電位までの減少は次のように制限されます。

${\displaystyle \Phi _{i}-\Phi _{f}\leq \sum _{x\in tree}{\log {\frac {W}{w(x)}}}}$

単一ノードの最大サイズはWで、最小サイズはw(x)であるためです。

したがって、実際の時間は次のように制限されます。

${\displaystyle O\left(\sum _{x\in sequence}{\left(1+3\log {\frac {W}{w(x)}}\right)}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)=O\left(m+\sum _{x\in sequence}{\log {\frac {W}{w(x)}}}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)}$

n個の要素を含むスプレイ ツリーでm 回のアクセスのシーケンスS を実行する場合の最悪ケースの実行時間に関する定理と推測がいくつかあります。

スプレイ ツリーの実証済みのパフォーマンス保証に加えて、Sleator と Tarjan のオリジナルの論文から、非常に興味深い未証明の推測が提示されています。この推測は動的最適性推測として知られており、基本的に、スプレイ ツリーは定数倍まで他のバイナリ検索ツリー アルゴリズムと同様に機能すると主張しています。

動的最適性予想: ^{[1] は}、ルートから へのパスをのコストでトラバースして要素にアクセスする任意のバイナリ検索木アルゴリズムであり、アクセス間では、1 回転あたり 1 のコストで木内の任意の回転を行うことができます。 がアクセスのシーケンスを実行するためのコストを とします。この場合、スプレー木が同じアクセスを実行するためのコストは です。${\displaystyle A}$${\displaystyle x}$${\displaystyle x}$${\displaystyle d(x)+1}$${\displaystyle A(S)}$${\displaystyle A}$${\displaystyle S}$${\displaystyle O[n+A(S)]}$

動的最適性仮説には、証明されていない帰結がいくつかあります。

トラバーサル予想: ^[1]と が同じ要素を含む 2 つのスプレイ木であるとします。 は の要素を事前順序 (つまり深さ優先探索順序) で訪問することによって得られるシーケンスであるとします。に対するアクセスシーケンスを実行するための総コストはです。${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle S}$${\displaystyle T_{2}}$${\displaystyle S}$${\displaystyle T_{1}}$${\displaystyle O(n)}$

デキュー予想: ^{[11] [13] [14]}両端キュー操作のシーケンス(push、pop、inject、eject)があるとします。このとき、スプレイ木での実行コストはです。${\displaystyle S}$${\displaystyle m}$ ${\displaystyle S}$${\displaystyle O(m+n)}$

スプリット予想: ^[6]をスプレイ木の要素の任意の順列とします。このとき、順序に従って要素を削除するコストはです。${\displaystyle S}$${\displaystyle S}$${\displaystyle O(n)}$

再構築操作の回数を減らすために、要素をルートに向かって半分だけ広げるセミスプレッドに置き換えることも可能です。 ^{[1] [2]}

再構築を減らすもう一つの方法は、完全なスプレイングを行うことですが、アクセス操作の一部のみ、つまりアクセスパスがしきい値よりも長い場合のみ、または最初のm回のアクセス操作のみで行います。^[1]

CBTreeは、各ノードのアクセスカウントでスプレイツリーを拡張し、それを使用してまれに再構築します。CBTreeの変種であるLazyCBTreeは、各ルックアップで最大1回の回転を行います。これは、楽観的なハンドオーバーハンド検証スキームとともに使用され、並行して自己調整するツリーを作成します。^[15]

ポインタ圧縮技術^{[16]を使用すると、}簡潔なスプレーツリーを構築することが可能です。

• AVLツリー
• Bツリー
• フィンガーツリー
• 二分探索木の幾何学
• イアコノのワーキングセット構造
• リンク/カットツリー
• データ構造のリスト
• スケープゴートの木
• スプレイソート、スプレイ木を使ったソートアルゴリズム
• Tツリー
• トレップ
• 木の回転
• 木々
• ジッパー（データ構造）

• Afek, Yehuda; Kaplan, Haim; Korenfeld, Boris; Morrison, Adam; Tarjan, Robert E. (2014). 「CB ツリー: 実用的な同時自己調整検索ツリー」.分散コンピューティング. 27 (6): 393–417. doi :10.1007/s00446-014-0229-0.
• Albers, Susanne ; Karpinski, Marek (2002 年 2 月 28日)。「ランダム スプレイ ツリー: 理論と実験結果」(PDF)。情報処理レター。81 (4): 213–221。doi :10.1016/s0020-0190(01)00230-7。
•  Allen, Brian; Munro, Ian (1978 年 10 月) 。「自己組織化バイナリ検索ツリー」。Journal of the ACM。25 ( 4 ): 526–535。doi : 10.1145 /322092.322094。S2CID 15967344。
• Brinkmann, Gunnar; Degraer, Jan; De Loof, Karel (2009 年 1 月)。「愛されない子供の更生: 半スプレー」( PDF)。ソフトウェア: 実践と経験。39 (1): 33–45。CiteSeerX 10.1.1.84.790。doi :10.1002/spe.v39:1。hdl : 11382/102133。結果は、スプレーと同じ論文で紹介された半スプレーが、ほぼすべての状況でスプレーよりも優れたパフォーマンスを発揮することを示しています。これにより、半スプレーは、通常スプレーが適用されるすべてのアプリケーションに適した代替手段になります。スプレーがそれほど普及したのに対し、半スプレーは比較的知られておらず、研究もほとんど行われていない理由は理解しがたいものです。 
• Cole, Richard; Mishra, Bud; Schmidt, Jeanette ; Siegel, Alan (2000 年 1 月)。「スプレイ ツリーの動的フィンガー予想について。パート I: スプレイ ソート log n ブロック シーケンス」。SIAM Journal on Computing。30 ( 1 ): 1–43。CiteSeerX 10.1.1.36.4558。doi :10.1137/s0097539797326988。 
• Cole, Richard (2000年1 月)。「スプレイ ツリーの動的フィンガー予想について。パート II: 証明」。SIAM Journal on Computing。30 ( 1): 44–85。CiteSeerX 10.1.1.36.2713。doi : 10.1137 / S009753979732699X 。 
• Elmasry, Amr (2004年4 月)。「スプレー ツリーの順次アクセス定理と Deque 予想について」。理論計算機科学。314 (3): 459–466。doi :10.1016/ j.tcs.2004.01.019。
• Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael (2014)。『Java のデータ構造とアルゴリズム』（第 6 版）。Wiley。p. 506。ISBN 978-1-118-77133-4。
• Grinberg, Dennis、Rajagopalan, Sivaramakrishnan、Venkatesan, Ramarathnam、Wei, Victor K. (1995)。「データ圧縮のためのスプレイ ツリー」。Clarkson, Kenneth L. (編)。第 6 回 ACM-SIAM 離散アルゴリズム シンポジウム議事録、1995 年 1 月 22 ～ 24 日。米国カリフォルニア州サンフランシスコ。ACM /SIAM。pp. 522 ～ 530。スプレイ ツリーのアクセスの平均深さは、エントロピーに比例します。
• クヌース、ドナルド(1997)。『コンピュータプログラミングの芸術』第 3 巻: ソートと検索 (第 3 版)。Addison-Wesley。p. 478。ISBN 0-201-89685-0スプレーツリー内のデータにアクセスするために必要な時間は、一連の操作にわたって償却した場合、最大でも静的に最適化されたツリーのアクセス時間の小さな定数倍であることが知られています。
• Lucas, Joan M. (1991)。「スプレイ ツリーの競合性について: ユニオン検索問題との関係」。オンライン アルゴリズム: DIMACS ワークショップの議事録、1991 年 2 月 11 ～ 13 日。離散数学と理論計算機科学シリーズ。第 7 巻。離散数学と理論計算機科学センター。95 ～ 124 ページ。ISBN 0-8218-7111-0。
• Pettie, Seth (2008). スプレイ ツリー、ダベンポート-シンツェル シーケンス、およびデック予想(PDF) . Proc. 19th ACM-SIAM Symposium on Discrete Algorithms . Vol. 0707. pp. 1115–1124. arXiv : 0707.2160 . Bibcode :2007arXiv0707.2160P.
• Sleator, Daniel D. ; Tarjan, Robert E. (1985). 「自己調整型バイナリ検索ツリー」(PDF) . Journal of the ACM . 32 (3): 652–686. doi :10.1145/3828.3835. S2CID  1165848.
• Sundar, Rajamani (1992). 「スプレーアルゴリズムの Deque 予想について」. Combinatorica . 12 (1): 95–124. doi :10.1007/BF01191208. S2CID  27422556.
• Tarjan, Robert E. (1985). 「スプレーツリーのシーケンシャルアクセスには線形時間がかかる」. Combinatorica . 5 (4): 367–378. doi :10.1007/BF02579253. S2CID  34757821.
• Bender, Michael A.; Conway, Alex; Farach-Colton, Martin; Kuszmaul, William; Tagliavini, Guido (2023). 「Tiny Pointers」。2023年 ACM-SIAM 離散アルゴリズムシンポジウム (SODA) の議事録: 477–508。doi : 10.1137 /1.9781611977554.ch21。ISBN 978-1-61197-755-4. S2CID  244709005。

• NIST のアルゴリズムとデータ構造の辞書: スプレイ ツリー
• C および Java での実装 (Daniel Sleator 著)
• スプレイツリーの視覚化へのポインタ
• スプレイツリーの高速かつ効率的な実装
• トップダウン スプレー ツリー Java 実装
• ジッパーツリー