試行（プレフィックスツリー）

1. 概要

このチュートリアルでは、プレフィックスツリーとも呼ばれるトライデータ構造について説明します。基本を簡単に説明してから、挿入、検索、プレフィックス検索などの最も重要な機能を実装する方法を説明します。

トライまたはプレフィックスツリーは特定の種類の検索ツリーであり、ノードは通常文字列によってキー設定されます。

試行は、セットや連想配列などのデータ構造を実装するために使用できますが、順序付けられたトラバーサルを実行したり、特定のプレフィックスで始まるキーを効率的に検索したりする必要がある場合に非常に役立ちます。

このため、オートコンプリートなどの機能を実装するときによく使用されます。

トライの基本的な実装では、各ノードに1つの文字とその子ノードへのポインターのリストが含まれます。ノードのキーは明示的に保存されません。代わりに、ルートからノードへのパスを計算することでキーを導出できます。

トライは次のようになります。

ツリー内のどのノードが有効なキーを表すかを区別するために、ブールフラグが使用されます。さらに、連想配列データ構造を実装するためにトライを使用している場合、ノードには任意のデータへのポインターを含めることができます。

この図は、キー「geek」、「genius」、「gene」、および「genetic」を格納するトライを示しています。ここで、強調表示されたノードは有効なキーを表しています。構造上、すべてのリーフノードは有効なキーですが、リーフノードでない場合は、ブールフラグをtrueに設定する必要があります。

要素をトライに挿入するには、ルートノードから開始してツリーを下にトラバースし、ノードが欠落している場合にのみノードを作成する必要があります。必要なノードをすべて作成したら、次のように設定します。最後のtrueへのブールフラグ。

たとえば、「gene」という単語がすでにツリーに含まれていて、「genetic」という単語を挿入している場合は、次のようにします。

逆に、「genetic」という単語がすでにツリーにあり、「gene」という単語を挿入している場合は、ツリーに新しいノードを追加する必要はありません。

実行する唯一のアクションは、エンドノードを有効なキーとしてマークすることです。

ルックアップは、特定のキーがツリーに含まれているかどうかを確認するために使用され、連想配列を実装している場合は、キーに関連付けられたデータを返すために使用されます。

ルックアップアルゴリズムを見てみましょう。

これは挿入アルゴリズムと非常に似ていますが、今回は欠落しているノードが見つかると、探している値が存在しないことがわかります。反復が完了した場合は、ルートからノードへの一致するパスが見つかったことを意味し、それが有効なキーであるかどうかを確認する必要があります。

挿入アルゴリズムとルックアップアルゴリズムの両方で、たとえば、深さ優先検索または幅優先検索を使用して、ツリー自体をトラバースする必要がなかったことに注意してください。たどる必要のあるパスは入力自体で提供されるため、トラバーサルは必要ありませんでした。

プレフィックスツリーの基本的な操作を見てきました。そして、今度は、それらがどこで優れているかを確認します。つまり、語彙から特定の接頭辞を持つすべての単語を取得します。

これを行うには、次のようにします。

これが実際にどのように見えるかを次に示します。

この記事では、プレフィックスツリーのデータ構造を実装する方法を見てきました。具体的には、基本的な挿入操作と検索操作、およびプレフィックス検索機能を実装する方法を学びました。