概要
データ構造はコンピューター プログラミングにおいて重要な資産を表し、いつ、なぜそれを使うかを知ることは非常に重要です。
この記事はトライ データ構造、その実装および複雑さの解析について簡単に紹介するものです。
Trie
トライは離散データ構造で、通常のアルゴリズムコースではあまり知られておらず、広く言及されていませんが、それでも重要なものです。
トライ（デジタル木としても知られ、接頭辞で検索できるため）、トライは順序木構造で、格納するキー（通常は文字列）を利用するものです。
ツリー内のノードの位置は、そのノードが関連付けられるキーを定義し、ノードがそのノードにのみ対応するキーを格納するバイナリ検索ツリーと比較して、トライを異なるものにしています。
あるノードのすべての子孫は、そのノードに関連付けられた文字列の共通の接頭辞を持ちますが、ルートは空の文字列と関連付けられます。 二項探索木もトライも木であるが、二項探索木の各ノードは必ず2つの子を持つのに対し、トライのノードはそれ以上持つことができる。
トライでは、（ルートノードを除く）すべてのノードに1文字または1桁が格納される。 ルートノードから特定のノードnまでトライを縦断することにより、文字または数字の共通の接頭辞を形成することができ、それはトライの他の枝でも共有される。
リーフノードからルートノードまでトライを縦断することにより、文字列または数字の列を形成することができる。
以下はトライデータ構造の実装を表すTrieクラスです。
public class Trie { private TrieNode root; //...}共通操作
それでは、基本操作の実装を見ていきましょう。 要素の挿入
最初に説明する操作は、新しいノードを挿入することです。
実装を始める前に、アルゴリズムを理解することが重要です：
- Set a current node as a root node
- Set the current letter as the first letter of the word
- もし現在のノードがすでに現在の文字への既存の参照を持っているなら（「子供」フィールドの要素の一つを通じて）、その参照ノードに現在のノードを設定します。 そうでなければ、新しいノードを作成し、文字を現在の文字に等しく設定し、さらに現在のノードをこの新しいノードに初期化する
- キーがトラバースされるまでステップ3を繰り返す
この操作の複雑さはO（n）、ここでnはキーサイズを表します。
このアルゴリズムの実装を以下に示します。
public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}さて、この方法を使ってトライに新しい要素を挿入する方法を見てみましょう：
private Trie createExampleTrie() { Trie trie = new Trie(); trie.insert("Programming"); trie.insert("is"); trie.insert("a"); trie.insert("way"); trie.insert("of"); trie.insert("life"); return trie;}次のテストからトライに新しいノードがすでに投入されていることをテストできます：
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2.
- Get children of the root
- Iterate through each character of the String
- Check that character is already a part of sub-trie.Finding Elements
ここで、特定の要素がtrieにすでに存在しているかどうかをチェックするメソッドを追加しましょう。 トライのどこにも存在しない場合は、検索を中止して false を返す
このアルゴリズムの複雑さはO(n)で、nは鍵の長さを表す。
Java の実装は次のようになります：
public boolean find(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } current = node; } return current.isEndOfWord();}そして動作は：
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. 要素の削除
要素の挿入と検索は別として、要素を削除できるようにする必要があることは明らかです。
削除処理では、次のステップに従う必要があります。
- この要素がすでにトライの一部であるかどうかをチェックする
- その要素が見つかった場合、トライから削除する
このアルゴリズムの複雑さは O(n) で、n は鍵の長さを表します。
実装を簡単に見てみましょう。
public void delete(String word) { delete(root, word, 0);}private boolean delete(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord()) { return false; } current.setEndOfWord(false); return current.getChildren().isEmpty(); } char ch = word.charAt(index); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord(); if (shouldDeleteCurrentNode) { current.getChildren().remove(ch); return current.getChildren().isEmpty(); } return false;}そして動作中：
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}結論
この記事では、トライデータ構造とその最も一般的な操作およびその実装について簡単に紹介しました。