1概要

データ構造は、コンピュータプログラミングにおける重要な資産であり、いつ、なぜ使用するのかを知ることは非常に重要です。

この記事では、トライ(try)と呼ばれるデータ構造、その実装、および複雑さの分析について簡単に紹介します。


2トライ

トライとは、典型的なアルゴリズムコースではあまり知られていない、または広く言及されているわけではありませんが、それでも重要なものです。

トライ(デジタルツリーとしても知られています)、時には基数ツリーや接頭辞ツリー(接頭辞で検索できるため)も、順序付けされたツリー構造です。

ツリー内のノードの位置は、そのノードが関連付けられているキーを定義します。これは、ノードがそのノードにのみ対応するキーを格納するバイナリ検索ツリーとは異なります。

ノードのすべての子孫は、そのノードに関連付けられた

String

という共通の接頭辞を持ち、ルートは空の__Stringに関連付けられます

ここでは、

Trieの実装で使用する

TrieNode__のプレビューを示します。

public class TrieNode {
    private HashMap<Character, TrieNode> children;
    private String content;
    private boolean isWord;

  //...
}

トライが二分探索木である場合があるかもしれませんが、一般に、これらは異なります。二分探索木と試行はどちらも木ですが、二分探索木の各ノードには常に2つの子があります。

トライでは、すべてのノード(ルートノードを除く)に1文字または数字が格納されます。トライをルートノードから特定のノードnまでトラバースすることにより、トライの他の枝によっても共有される文字または数字の共通の接頭辞を形成することができる。

リーフノードからルートノードまでトライをたどることによって、

String

または一連の数字を形成できます。

これは、トライデータ構造の実装を表す

Trie

クラスです。

public class Trie {
    private TrieNode root;
   //...
}


3共通の操作

それでは、基本的な操作を実装する方法を見てみましょう。


3.1. 要素を挿入する

最初に説明する操作は、新しいノードの挿入です。

実装を始める前に、アルゴリズムを理解することが重要です。

  1. 現在のノードをルートノードとして設定する

  2. 現在の文字を単語の最初の文字として設定

  3. 現在のノードに現在のノードへの参照がすでに存在する場合

(「children」フィールドの要素の1つを介して)文字を入力してから、
現在のノードからその参照ノードそれ以外の場合は、新しいノードを作成して設定します。
現在の文字と等しい文字、そして現在のノードも初期化します。
この新しいノードへ
。キーが移動するまで手順3を繰り返します。

  • この操作の複雑さは

    O(n)

    です。ここで、

    n

    はキーサイズを表します。

これがこのアルゴリズムの実装です。

public void insert(String word) {
    TrieNode current = root;

    for (int i = 0; i < word.length(); i++) {
        current = current.getChildren()
          .computeIfAbsent(word.charAt(i), 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;
}

次のテストから、トライに新しいノードがすでに追加されていることをテストできます。

@Test
public void givenATrie__WhenAddingElements__ThenTrieNotEmpty() {
    Trie trie = createTrie();

    assertFalse(trie.isEmpty());
}


3.2. 要素を探す

特定の要素がトライに既に存在するかどうかをチェックするメソッドを追加しましょう。

  1. ルートの子を取得する


  2. String

    の各文字を繰り返します

  3. そのキャラクターがすでにサブトライの一部であるかどうかを確認してください. それであれば

トライのどこにも存在しない場合は、検索を中止して戻り

虚偽

。文字がなくなるまで、2番目と3番目の手順を繰り返します


String

の終わりに達した場合は、

true

を返します。

  • このアルゴリズムの複雑さは

    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();
}

そして実際には:

@Test
public void givenATrie__WhenAddingElements__ThenTrieContainsThoseElements() {
    Trie trie = createExampleTrie();

    assertFalse(trie.containsNode("3"));
    assertFalse(trie.containsNode("vida"));
    assertTrue(trie.containsNode("life"));
}


3.3. 要素を削除する

要素を挿入して見つけること以外に、要素を削除できるようにする必要があることは明らかです。

削除プロセスのために、私達はステップに従う必要があります。

  1. この要素がすでにトライの一部であるかどうかを確認してください

  2. 要素が見つかった場合は、トライからそれを削除します

このアルゴリズムの複雑さは

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;
}

そして実際には:

@Test
void whenDeletingElements__ThenTreeDoesNotContainThoseElements() {
    Trie trie = createTrie();

    assertTrue(trie.containsNode("Programming"));

    trie.delete("Programming");
    assertFalse(trie.containsNode("Programming"));
}


4結論

この記事では、データ構造とその最も一般的な操作およびそれらの実装について簡単に紹介しました。

この記事に示されている例の完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/data-structures[GitHubに載っています]。