三項探索木

コンピュータサイエンスにおいて、三分探索木はトライ木の一種（プレフィックス木と呼ばれることもある）であり、ノードは二分探索木に似た方法で配置されますが、二分木の2つという制限ではなく、最大3つの子を持つことができます。他のプレフィックス木と同様に、三分探索木は増分文字列検索機能を備えた連想マップ構造として使用できます。ただし、三分探索木は標準のプレフィックス木と比較して、速度は犠牲になりますが、スペース効率は高くなります。三分探索木の一般的な用途には、スペルチェックや自動補完などがあります。

三項探索木の各ノードには、1 つの文字、オブジェクト(実装によってはオブジェクトへのポインタ)、および慣例的にequal kid、lo kid、hi kidと呼ばれる 3 つの子へのポインタが格納されます。これらの子は、それぞれmiddle (child)、lower (child)、higher (child)とも呼ばれます。^[1]ノードには、親ノードへのポインタと、ノードが単語の終わりを示すかどうかを示すインジケータが含まれる場合もあります。^[2] lo kidポインタは、文字値が現在のノードより小さいノードを指す必要があります。hi kidポインタは、文字値が現在のノードより大きいノードを指す必要があります。^[1] equal kid は、単語の次の文字を指します。次の図は、文字列 "cute"、"cup"、"at"、"as"、"he"、"us"、"i" を含む三項探索木を示しています。

          ｃ
        / | \
       ああ
       | | | \
       テウ
     / / | / |
    スパイス

他のトライデータ構造と同様に、三分探索木の各ノードは格納されている文字列のプレフィックスを表します。ノードの中間のサブツリーにあるすべての文字列は、そのプレフィックスで始まります。

三項検索への値の挿入は、ルックアップが定義されるのと同じように、再帰的または反復的に定義できます。この再帰メソッドは、キーの先頭の文字を削除することで徐々に短くなるキーが与えられたツリーのノードに対して継続的に呼び出されます。このメソッドがまだ作成されていないノードに到達すると、ノードを作成し、キーの最初の文字の文字値を割り当てます。新しいノードが作成されるかどうかに関係なく、メソッドは文字列の最初の文字がノードの文字値より大きいか小さいかを確認し、ルックアップ操作の場合と同様に適切なノードに対して再帰呼び出しを行います。ただし、キーの最初の文字がノードの値と等しい場合は、等しいキッドに対して挿入プロシージャが呼び出され、キーの最初の文字が削除されます。^[1]バイナリ検索ツリーやその他のデータ構造 と同様に、三項検索ツリーはキーの順序に応じて退化する可能性があります。^{[3] [自費出版ソース?アルファベット順にキーを挿入することは}、最悪の退化したツリーを作成する一つの方法です。^[1]キーをランダムな順序で挿入すると、バランスの取れたツリーが作成されることがよくあります。^[1]

function inserting ( string key ) is node p := root //ルートがnullの場合に等しくなるように初期化node last := root int idx := 0 while pがnullでない場合do //適切なサブツリーを再帰するif key [ idx ] < p . splitchar then last := p p := p . left else if key [ idx ] > p . splitchar then last := p p := p . right else : //キーはすでにツリー内に存在しますif idx == length ( key ) then return //キーから文字をトリムするidx := idx + 1 last := p p := p . mid p := node () //最後のnullでないノード（ルートがnullの場合はルート）の子としてpを追加するif root == null then root := p else if last . splitchar < key [ idx ] then last . right := p else if last . splitchar > key [ idx ] then last . left := p else last . mid := p p . splitchar := key [ idx ] idx := idx + 1 // キーの残りを挿入while idx < length ( key ) do p . mid := node () p . mid . splitchar := key [   
	    
    
	   
	   
	     
        
		    
			  
			  
		     
			  
			  
		
            
			    
				 
            
			  
			  
			  
	  
    
        
          
	     
		  
	     
		  
	 
		  
	  
	  
    
	    
		  
          idx ] 
idx += 1		  

特定のノードまたはノードに関連付けられたデータを検索するには、文字列キーが必要です。検索手順は、ツリーのルート ノードをチェックし、次の条件のどれが発生したかを判断することから始まります。文字列の最初の文字がルート ノードの文字より小さい場合、現在のルートの lo キッドをルートとするツリーで再帰検索を呼び出すことができます。同様に、最初の文字がツリーの現在のノードより大きい場合、現在のノードの hi キッドをルートとするツリーに対して再帰呼び出しを行うことができます。^[1] 最後のケースとして、文字列の最初の文字が現在のノードの文字に等しい場合、キーにそれ以上の文字がなければ関数はノードを返します。キーにそれ以上の文字がある場合は、キーの最初の文字を削除し、等しいキッド ノードと変更されたキーを指定して再帰呼び出しを行う必要があります。^[1] これは、現在のノードへのポインタとキーの現在の文字へのポインタを使用して非再帰的に記述することもできます。^[1]

 関数search ( string query )は、is_empty ( query )の場合falseを返します。ノードp := root int idx := 0ですが、p はnullではありません。query [ idx ] < p . splitcharの場合p := p . leftです。そうでない場合、query [ idx ] > p . splitcharの場合p := p . rightです。そうでない場合、 idx = length ( query )の場合trueを返します。idx := idx + 1 p := p . mid falseを返します。   
       
          
 
        
        
 
          
             
               
              
               
         
                 
                  
                 
               
 
      

削除操作は、検索ツリーでキー文字列を検索し、firstMid の中央の子からキー文字列の検索パスの終わりまでのパスに左または右の子が存在しないノード (以下の疑似コードでは firstMid と呼ばれる) を見つけることから構成されます。これは、キー文字列に対応する 3 進ツリー内の一意のサフィックスを表します。このようなパスがない場合は、キー文字列が別の文字列のプレフィックスとして完全に含まれているか、検索ツリーに含まれていないことを意味します。多くの実装では、文字列の終了文字を使用して、後者のケースのみが発生するようにします。次に、firstMid.mid から検索パスの終わりまでのパスが削除されます。firstMid がルートの場合、キー文字列はツリーの最後の文字列である必要があるため、削除後にルートは null に設定されます。

 関数delete (文字列キー)は、is_empty (キー)の場合、ノードp :=ルートintidx := 0を返します。   
       
          
 
        
        

 	 node firstMid := null while pがnullでない場合do if key [ idx ] < p . splitchar then firstMid := null p := p . left else if key [ idx ] > p . splitchar then firstMid := null p := p . right else firstMid := p while pがnullでなくkey [ idx ] == p . splitchar do idx := idx + 1 p := p . mid if firstMid == null then return // 一意の文字列サフィックスはありません   
          
             
               
               
              
               
               
         
               
                      
             	    
             	  
             
         
           

     // この時点で、firstMid は文字列の一意のサフィックスが発生する前のノードを指します。
ノードq := firstMid . midノードp := q firstMid . mid := null // qがnullでない場合はツリーからサフィックスを切断します。do // サフィックス パスをたどってノードを削除します。p := q q := q . mid delete ( p ) // ノード p に関連付けられたメモリを解放します。if firstMid == root then delete ( root ) //ツリー全体を削除します。root := null         
        
        
           
           
            
         			
          
                
           

^{[説明が必要] [例が必要]}

^{[説明が必要] [例が必要]}

^{[説明が必要] [例が必要]}

三元探索木の実行時間は入力によって大きく異なります。三元探索木は、いくつかの類似した文字列、特にそれらの文字列が共通のプレフィックスを共有している場合に最もよく実行されます。また、三元探索木は、比較的短い文字列(辞書内の単語など)を大量に保存する場合に効果的です。 ^[1]三 元探索木の実行時間は、通常は対数時間で実行されるという点で二分探索木に似ていますが、退化した (最悪の) ケースでは線形時間で実行されることもあります。さらに、実行時間を考慮する際には文字列のサイズも考慮する必要があります。たとえば、長さkの文字列の検索パスでは、ツリーの中央の子をk 回トラバーサルするとともに、ツリーの左と右の子を対数回数トラバーサルします。したがって、少数の非常に大きな文字列に対する三元探索木では、文字列の長さが実行時間を支配する可能性があります。^[4]

三分探索木演算の時間計算量: ^[1]

他のプレフィックスツリーよりも遅いですが、三分探索木はスペース効率が良いため、大規模なデータセットに適しています。^[1]

ハッシュテーブルは、文字列を値にマッピングするための三分探索木の代わりに使用することもできます。ただし、ハッシュマップは三分探索木よりも多くのメモリを使用することがよくあります (トライほどではありませんが)。さらに、ハッシュマップは、最初の数文字だけでなく文字列全体を比較する必要があるため、同じデータ構造にない文字列を報告するのに通常は時間がかかります。三分探索木がハッシュマップよりも高速に実行されることを示す証拠がいくつかあります。^{[1]さらに、ハッシュマップでは、}近傍検索など、三分探索木の多くの用途が使用できません。

辞書の単語を保存することだけが必要な場合 (つまり、各単語に付随する情報の保存が必要ない場合)、最小決定性非巡回有限状態オートマトン (DAFSA) はトライまたは三分探索木よりも少ないスペースを使用します。これは、DAFSA が、保存されている異なる単語の同じ接尾辞 (または部分) に対応するトライからの同一のブランチを圧縮できるためです。

三項検索木は、大量の文字列を任意の順序で保存および取得する必要がある多くの問題を解決するために使用できます。これらのうち最も一般的または最も有用なもののいくつかを以下に示します。

• トライはいつでも使用できますが、メモリ消費量の少ない構造が好まれます。^[1]
• 文字列を他のデータにマッピングするための高速で省スペースなデータ構造。^[3]
• 自動補完を実装するため。^{[2] [自費出版ソース? ]}
• スペルチェックとして。^[5]
• 近傍検索（スペルチェックは特別なケースです）。^[1]
• 特に複数の非キーフィールドによるインデックス作成が望ましいデータベースの場合。 ^[5]
• ハッシュテーブルの代わりに^[5]

• 3元基数クイックソート
• トライ
• 二分探索木
• ハッシュテーブル

• 三元探索木と「文字列のソートと検索」アルゴリズムに関する論文 (Jon Bentley と Robert Sedgewick による) が掲載された三元探索木ページ
• 三値探索の試み – ロバート・セジウィックによるビデオ
• TST.java.html Robert Sedgewick と Kevin Wayne による TST の Java 実装