[データ構造] 三分探索木

三分探索木

三分探索木（さんぶんたんさくぎ、英: ternary search tree）は、トライ木の各ノードを二分探索木として表現したデータ構造である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

三分探索木は、トライ木に2分探索木を取り入れることでポインタを減らし、メモリ効率の改善を図るデータ構造です。

各ノードは、左の子、中の子、右の子と3つの子を持ちます。

左の子（左ノード）は親より小さな文字を、右の子（右ノード）は親より大きな文字を、中の子（中央ノード）は親から続く文字になります。

左ノード、右ノードへ続く場合は親の持つ文字は消され、中央ノードへ続く場合のみ親の持つ文字が残ります。

# "cute","cup","at","as","he","us" and "i" を示す。
          c
        / | \
       a  u  h
       |  |  | \
       t  t  e  u
     /  / |   / |
    s  p  e  i  s

文字列の挿入

文字列を挿入し上と同じ三分探索木を作ってみます。

まずは最初の文字列として ‘cute’ を挿入します。

# 'cute を挿入
          c
        　| 
          u  
          |
          t
          | 
          e

‘cup’ を挿入します。

‘c’ ‘u’ は一致しますが、’t’と’p’は一致しません。 ‘p’は’t’より前なので左の子になります。

# 'cup' を挿入
          c
        　| 
          u  
          |
          t
        / | 
       p  e

‘at’ を挿入します。

‘a’と’c’は一致しません。 ‘a’は’c’より前なので左の子になります。

# 'at' を挿入
          c
        / | 
       a  u  
       |  |
       t  t
        / | 
       p  e

以下、一致する場合は真ん中のノード、一致しない場合はアルファベット順に従い左か右のノードに進み挿入を行うことで上と同じ三分探索木となります。

# 'as' を挿入
          c
        / |
       a  u
       |  |
       t  t
     /  / |
    s  p  e

# 'he' を挿入
          c
        / | \
       a  u  h
       |  |  |
       t  t  e
     /  / |
    s  p  e

# 'us' を挿入
          c
        / | \
       a  u  h
       |  |  | \
       t  t  e  u
     /  / |     |
    s  p  e     s

# 'i' を挿入
          c
        / | \
       a  u  h
       |  |  | \
       t  t  e  u
     /  / |   / |
    s  p  e  i  s

文字列の取り出し

ハッシュテーブルと三分探索木を比べると、特にキーが存在しない場合は、ハッシュテーブルはキーとなる全ての文字を使いハッシュ値を生成しなければなりませんが、三分探索木ではキーとなる文字列の最初の数文字だけでその文字列の有無を判断することができる可能性があり、この点で三分探索木（トライ木）はハッシュテーブルより高速になります。

# 'cup' を取り出す。
          c
        / | \
       a  u  h
       |  |  | \
       t  t  e  u
     /  / |   / |
    s  p  e  i  s

‘cup’ を取り出してみます。

‘c’ ‘u’ は一致しますが、’t’と’p’は一致しません。’p’は’t’より前なので左に進むと’p’があるので’cup’が取り出せます。

# 'cg' を取り出す。
          c
        / | \
       a  u  h
       |  |  | \
       t  t  e  u
     /  / |   / |
    s  p  e  i  s

‘cg’ を取り出してみます。

‘c’は一致しますが、’u’と’g’は一致しません。’g’は’u’より前なので左に進みたいのですが左の子はないので、’cg’は木に存在しないことが分かります。

三分探索木とハッシュテーブルの比較

三分探索木とハッシュテーブルを比較します。

ハッシュ	三部探索木
キーには様々な型	キーは文字列
検索時、常に全てのキーを使う	検索時、前方から必要なだけのキーを使う
ハッシュ関数により計算量が大きく変わる
キーでソートはできない。	キーでソートできる。