基本概念
トライ木（Trie木）は文字列に関連するデータ構造で、辞書木または接頭辞木とも呼ばれます。その主な思想は「空間で時間を換える」ことです。大量の文字列を統計、ソート、または保存するために使用できます。検索する文字列をsとすると、トライ木の単一クエリの複雑度はO(|s|)です。
01トライ木は、XOR関連問題を扱うデータ構造のバリエーションです。複数の数値のペアごとのXOR和の中で、特定の値より大きい/小さいすべての値の合計を高速に求めることができます。
アルゴリズム思想
基本思想
トライ木の主な思想は、同じ接頭辞を保存するために空間を最適化し、暴力的な時間空間複雑度を改善することです。トライ木は重み付き木で、各エッジの重みは文字です。トライ木の根ノードを空文字列と見なし、ノードuに対して、根ノードからノードuへのパスがノードuに対応する接頭辞または文字列です。
例えば、Ling、Lion、Yue、Zheng、YYUTという5つの単語があるとします。構築されたトライ木は以下のようになります：
トライ木にはいくつかの基本的な性質があります：
- トライ木の根ノードは空文字列で、通常は0と番号が付けられます
- 各ノードは文字列を保存します
- 根ノードからノードuへのパス上の文字を連結したものが、ノードuが保存する文字列です
- 同じ接頭辞に対応するノードは結合され、重複したノードの構築を避けます
- 各ノードuの後継は同じ接頭辞を持つ文字列に対応します
上図の単語LingとLionは同じ接頭辞Liを持っているため、Liを保存するノードとその祖先を一緒に結合し、同じ接頭辞を保存するために2つのノードしか使用しません。単語Yueと単語YYUTは同じ接頭辞Yを持っているため、Yを保存するノードは同じノードに結合されます。単語Zhengは他の単語と共通の接頭辞がないため、個別に保存されます。
トライ木の性質を理解したら、トライ木を構築してみましょう。トライ木は主に挿入と検索をサポートし、一部のトライ木は削除もサポートしますが、この記事ではこれらの特殊なトライ木は議論しません。問題は通常、特定の条件の値を求める必要があるため、各ノードは必要に応じて追加の重み値を維持するかもしれません。
文字列sを挿入するとします。文字列の先頭から考慮を開始し、根ノードrに子ノードuが存在し、wr,u = s0である場合、sは他の単語と共通の接頭辞s0を持っているため、既に構築されたノードを共有して、再帰的に下に進みます。そうでない場合、sの後の部分は他の単語と共通の接頭辞がないことを示しており、新しいノードuを構築し、エッジの重みs0を割り当てます。挿入を再帰的に続行し、文字列sのすべての文字が挿入されるまで続けます。最終的に得られたトライ木は、上記のすべての性質を満たします。
上図のトライ木に単語Lilyを挿入するプロセスをいくつかの図でシミュレートしてみましょう：
まず、根ノードの最大26個の子ノードを走査します。s0 = Lであり、トライ木にすでにLの接頭辞を持つ後継ノードが存在することがわかります。したがって、Lilyを保存するノードをそのノードの後継に設定し、そのノードの子ツリーに入って再帰的に挿入を続けます。
上記の手順と同様に、現在のノードの最大26個の子ノードを走査します。s1 = iであり、トライ木にすでにLiの接頭辞を持つ後継ノードが存在することがわかります。したがって、Lilyを保存するノードをそのノードの後継に設定し、そのノードの子ツリーに入って再帰的に挿入を続けます。
現在のノードのすべての子ノードを走査し、lのエッジの重みを持つ子ノードが見つからないことがわかります。したがって、トライ木にLilの接頭辞を持つ後継ノードが存在しないことを示しています。新しいノードを構築する必要があります。したがって、新しいノードを構築し、そのノードの子ツリーに入って再帰的に挿入します。
現在のノードの子ツリーが空であるため、上記と同様に、yのエッジの重みを持つ親子ノードを新しく構築します。文字列Lilyはトライ木に正常に挿入され、再帰が終了します。長さlの文字列をトライ木に挿入する時間複雑度はO(l)です。
トライ木で特定の接頭辞sが出现过かどうかを検索することも非常に簡単です。根ノードから始めて、s0のエッジの重みを持つ子ノードが存在するかどうかを確認し、再帰的に検索します。現在のノードの子ノードの中で、s1のエッジの重みを持つ子ノードが存在するかどうかを確認し、再帰的に検索します……ある時点で条件を満たす子ノードが見つからない場合、この接頭辞はトライ木に挿入されていません。逆に、各検索で条件を満たす子ノードが見つかる場合、この接頭辞はトライ木に存在します。
文字列sが出现过かどうかを検索する場合、トライ木のノードにマークを付ける必要があります。なぜなら、ある文字列が挿入されていると仮定し、上記の方法でその文字列の接頭辞を検索すると、その接頭辞に対応するノードがトライ木に存在することがわかります。この接頭辞をトライ木に挿入したことがない場合、アルゴリズムは誤った結果を出力します。したがって、各ノードにマークを付けて、現在のノードが保存する接頭辞が挿入された文字列であるかどうかを示す必要があります。最終的に見つかったノードにマークが付けられている場合、その文字列がトライ木に挿入されたと見なします。そうでない場合、検索したのは単なる文字列の接頭辞に過ぎません。
具体的な実装は、文字列を挿入するプロセスで実現できます。文字列sを挿入した場合、sを保存するノードにマークを付けます。上図に具体的に適用すると、単語Lingを挿入する場合、左下のノードにマークを付けます。
例題解説
n個の文字列とm個のクエリが与えられ、各クエリで文字列sが与えられます。sが与えられていない場合は「WRONG」を出力し、sが与えられていて初めてクエリされた場合は「OK」を出力し、sが与えられていて初めてでない場合は「REPEAT」を出力します。
この問題はトライ木のテンプレート問題ですが、各文字列がクエリされた回数も維持する必要があります。この場合、与えられた文字列を保存する各ノードに追加の重み値を追加し、この文字列がクエリされたかどうかを示す必要があります。出力「WRONG」の場合は、文字列がトライ木に挿入されていないことを示します；出力「OK」の場合は、文字列がトライ木に挿入され、追加の重み値がfalseであることを示し、出力「OK」後に追加の重み値をtrueに設定します；出力「REPEAT」の場合は、文字列がトライ木に挿入され、追加の重み値がtrueであることを示します。
参考コード
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int ALPHABET_SIZE = 26;
class TrieNode {
public:
TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
int queryCount;
TrieNode() {
for (int i = 0; i < ALPHABET_SIZE; i++) {
children[i] = nullptr;
}
isEndOfWord = false;
queryCount = 0;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEndOfWord = true;
}
string search(const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
return "WRONG";
}
node = node->children[index];
}
if (!node->isEndOfWord) {
return "WRONG";
}
if (node->queryCount == 0) {
node->queryCount = 1;
return "OK";
} else {
node->queryCount++;
return "REPEAT";
}
}
};
int main() {
int n, m;
cin >> n;
Trie trie;
string word;
for (int i = 0; i < n; i++) {
cin >> word;
trie.insert(word);
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> word;
cout << trie.search(word) << endl;
}
return 0;
}
01トライ木
基本思想
01トライ木はトライ木から派生したデータ構造で、XOR関連の問題を扱うために使用できます。01トライ木はトライ木の変更が非常に簡単で、複数の数値を2進数表現（つまり複数の01列）に変換し、これらの01列をトライ木に挿入して得られたトライ木を01トライ木と呼びます。
注意：01トライ木は、保存する2進数のビット数を統一する必要があります。これは⌈log₂max(ai)⌉です。このビット数より高いビット位置は0で、XOR和の維持にとって意味がありません。コード実装では、(x >> i) & 1を使用して10進数xの第iビットが1かどうかを判断できます。
例えば、4つの10進数1、2、4、5があり、ビット数の最大値は3です。対応する2進数表現はそれぞれ001、010、100、101です。構築された01トライ木は以下のようになります：
例題選講
n個の数値が与えられ、n個の数値から2つの数値を選んでXOR演算を行ったときの最大の結果を求めます。1 ≤ n ≤ 10⁵, 0 ≤ Ai ≤ 2³¹
これは01トライ木のテンプレート問題で、貪欲な思想も必要です。n個の数値に対して01トライ木を構築し、そのうちの一つの数値を列挙すると、問題はある数値を与えて、n個の数値の中でそれと最大のXOR和を求める問題に変わります。
XOR和を最大にするためには、上位のビットが異なるように保証する必要があります。理由は、左から数えて第xビットが異なるようにすると、後続のすべてのビットの数字が異なっても、損失は最大でΣi=0x-12i < 2xです。第xビットを反対の値に取ると、後続の可能な貢献の合計も第xビットの損失より小さくなります。
したがって、貪欲な戦略を考え出すことができます。与えられた数値xに対して、2進数の左から右への第31ビットに対応する深さ2から走査を開始します。現在、左から右への第iビットに到達したと仮定します。深さiのノードにxの第iビットと反対のエッジの重みを持つ子ノードが存在する場合、そのノードに入って再帰的に進みます。そうでない場合は、もう一つの唯一のノードに入って再帰的に進みます。
参考コード
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_BITS = 31;
class BinaryTrie {
private:
struct TrieNode {
TrieNode* children[2];
TrieNode() {
children[0] = nullptr;
children[1] = nullptr;
}
};
TrieNode* root;
public:
BinaryTrie() {
root = new TrieNode();
}
void insert(int num) {
TrieNode* node = root;
for (int i = MAX_BITS; i >= 0; i--) {
int bit = (num >> i) & 1;
if (!node->children[bit]) {
node->children[bit] = new TrieNode();
}
node = node->children[bit];
}
}
int queryMaxXor(int num) {
TrieNode* node = root;
int maxXor = 0;
for (int i = MAX_BITS; i >= 0; i--) {
int bit = (num >> i) & 1;
int oppositeBit = 1 - bit;
if (node->children[oppositeBit]) {
maxXor |= (1 << i);
node = node->children[oppositeBit];
} else {
node = node->children[bit];
}
}
return maxXor;
}
};
int main() {
int n;
cin >> n;
BinaryTrie trie;
vector<int> numbers(n);
for (int i = 0; i < n; i++) {
cin >> numbers[i];
trie.insert(numbers[i]);
}
int maxResult = 0;
for (int num : numbers) {
maxResult = max(maxResult, trie.queryMaxXor(num));
}
cout << maxResult << endl;
return 0;
}