TrieNodeクラス：挿入と検索
children dictとis_endフラグを持つTrieNodeを構築し、insertと完全一致検索を実装して、単語の長さをmとした各操作の計算量O(m)を分析します。
「TrieNodeクラス：挿入と検索」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
Trieとは何ですか
Trie（プレフィックス木）は、各ノードが1つの文字を表す木構造のデータ構造です。ルートからリーフまで文字を連結することで単語を格納します。ルートは空文字列を表します。ルートからis_end = Trueのノードまでの各経路が、格納された単語を表します。Trieは、オートコンプリート、スペルチェック、IPルーティングなどのプレフィックスベースのクエリに適しており、これらの用途ではハッシュマップを上回ります。
TrieNodeクラスの設計
TrieNodeには2つのフィールドがあります。childrenは文字から子TrieNodeへの対応付けを行う辞書で、is_endはそのノードが格納された単語の終端かどうかを示すブール値です。固定長の26文字配列ではなく辞書を使用すると、任意の文字集合に対応でき、疎なTrieでメモリを節約できます。Trie内の各ノードは、そのノード以下の単語における1つの文字位置を正確に表します。
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)挿入操作
単語を挿入するには、ルートから走査し、現在のノードのchildrenにまだ存在しない各文字について、新しいTrieNodeを作成します。すべての文字を処理したら、最後のノードでis_end = Trueを設定します。'apple'と'app'を挿入すると、a→p→p→l→eの連鎖が作られます（'apple'に対してis_end=True）。また、3文字目のpにも' app'に対するis_end=Trueが設定されます。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)検索操作
完全一致する単語を検索するには、各文字に従ってTrieを走査します。現在のノードのchildrenに存在しない文字が1つでもあれば、Falseを返します。すべての文字が見つかった場合はnode.is_endを返します。これは、単なるプレフィックスではなく、そこで単語がちょうど終わる場合にのみTrueになります。「プレフィックスが存在する」と「完全な単語が存在する」の区別は重要で、問題でもよく問われます。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end # must be a complete word
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False (app not inserted)
print(t.search('orange')) # FalseStarts-With（プレフィックス検索）
starts_withメソッドは、挿入された単語のいずれかが指定されたプレフィックスで始まるかを確認します。searchと同じように走査しますが、is_endを確認する代わりに、プレフィックスのすべての文字を正常にたどれた時点でTrueを返します。これは、プレフィックスの経路がTrieに存在することを意味します。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True # prefix path exists
t = Trie()
t.insert('apple')
print(t.starts_with('app')) # True
print(t.starts_with('ape')) # False
print(t.search('app')) # False (not inserted)時間計算量と空間計算量
Trieの各操作（insert、search、starts_with）は、単語の長さをmとするとO(m)時間で実行できます。最大でm個のノードを走査するためです。空間計算量はO(ALPHABET_SIZE × N × M)で、Nは単語数、Mは単語の平均長です。実際には、共有されるプレフィックスによって空間使用量は大幅に削減されます。ハッシュマップベースのchildren辞書は、疎なTrieでは固定長の26文字配列よりも少ない空間で済みますが、検索ごとの定数オーバーヘッドはやや大きくなります。
Dictの代わりに配列を使用する
小文字の英字だけを扱う場合は、固定長配列children = [None] * 26を使用し、インデックスにはord(c) - ord('a')を使います。これは、子ノードの検索がハッシュマップより高速（O(1)）で、メモリ配置も予測しやすい方法です。文字集合が大きい、または不明な場合（Unicodeなど）は辞書版を使用し、小文字だけを扱う競技プログラミング形式の問題では配列版を使用します。
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class TrieArray:
def __init__(self):
self.root = TrieNodeArray()
def insert(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = TrieNodeArray()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None: return False
node = node.children[idx]
return node.is_end
t = TrieArray()
t.insert('cat')
print(t.search('cat')) # True
print(t.search('car')) # False削除操作
Trieからの削除では、3つのケースに対応する必要があります。(1) 単語が存在しない — 何もしません。(2) 単語は存在するが、別の単語のプレフィックスになっている — is_endの設定を解除するだけです。(3) 単語が存在し、別の単語のプレフィックスでもない — 下から上へノードを削除し、あるノードに他の子があるか、そのノードが別の単語の終端になるところで停止します。削除が面接で問われることはまれですが、概念として知っておくとよいでしょう。
プレフィックスで単語を数える
各ノードにcountフィールドを追加し、挿入時にそのノードを通過するたびにインクリメントします。指定されたプレフィックスを持つ単語の数を数えるには、プレフィックスの終端ノードまで走査して、そのcountを返します。これにより、すべての子ノードを走査せずにO(m)のオートコンプリートクエリを実行できます。実際のオートコンプリートシステムに役立つ拡張です。
class TrieNodeCount:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # words passing through this node
class TrieCount:
def __init__(self):
self.root = TrieNodeCount()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNodeCount()
node = node.children[c]
node.count += 1 # increment on each level
node.is_end = True
def count_with_prefix(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return 0
node = node.children[c]
return node.count
t = TrieCount()
for w in ['apple','app','application','apply']:
t.insert(w)
print(t.count_with_prefix('app')) # 4
print(t.count_with_prefix('appl')) # 3Trieとハッシュマップの比較
ハッシュマップは平均O(m)時間で完全一致検索を実行できますが、プレフィックスクエリには効率よく答えられません（すべてのキーを走査する必要があります）。Trieは、プレフィックスの長さをpとするとO(p)でプレフィックスクエリに答えられ、共有プレフィックスごとに単語を自然にグループ化でき、ハッシュも必要ありません。頻繁なプレフィックスクエリ、オートコンプリート、スペルチェックにはTrieを使用します。完全一致検索だけが必要な場合はハッシュマップを使用します。
実世界のシステムにおけるTrie
実世界でのTrieの用途には、オートコンプリート（Googleの検索候補）、スペルチェッカー（最も近い単語の検索）、IPルーティング（ルーターでの最長プレフィックスマッチング）、T9予測入力（文字の曖昧性解消）、DNSリゾルバー（階層的なドメイン名検索）があります。いずれの場合も、1操作あたりO(m)の計算量とO(ALPHABET × nodes)の空間計算量というTrieのトレードオフにより、大規模な環境で高速かつプレフィックスを考慮した検索を行う適切な手段になります。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、TrieNodeにはchildren辞書とis_endブール値があること、insertは文字ごとに走査し、必要に応じてノードを作成して最後にis_endを設定すること、そしてsearchはis_endを確認する一方、starts_withはプレフィックスの経路が存在するかだけを確認することを学びました。次は、プレフィックスベースのオートコンプリートとstarts_withメソッドについて、さらに詳しく扱います。
よくある質問
「TrieNodeクラス：挿入と検索」レッスンは無料ですか？
はい。「TrieNodeクラス：挿入と検索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「TrieNodeクラス：挿入と検索」で何を学びますか？
children dictとis_endフラグを持つTrieNodeを構築し、insertと完全一致検索を実装して、単語の長さをmとした各操作の計算量O(m)を分析します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「TrieNodeクラス：挿入と検索」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。