Trieデータ構造のC++実装
この投稿では、挿入、削除、および検索操作をサポートするTrieデータ構造のC++実装について説明します。
Trieは、効率的な再構築に使用されるツリーベースのデータ構造であることを私たちは知っていますtrie文字列の巨大なセットのキーのval。の中に 前の投稿、Trieデータ構造について説明し、そのC実装について説明しました。この投稿では、Trieデータ構造のC++実装について説明します。これは、C実装よりもはるかにクリーンです。
以下は、挿入、削除、および検索操作をサポートするTrieデータ構造のC++実装です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 |
#include <iostream> using namespace std; //文字サイズを定義します #define CHAR_SIZE 128 //Trieノードを格納するクラス class Trie { public: bool isLeaf; Trie* character[CHAR_SIZE]; //コンストラクタ Trie() { this->isLeaf = false; for (int i = 0; i < CHAR_SIZE; i++) { this->character[i] = nullptr; } } void insert(string); bool deletion(Trie*&, string); bool search(string); bool haveChildren(Trie const*); }; //キーをTrieに挿入する反復関数 void Trie::insert(string key) { //ルートノードから開始します Trie* curr = this; for (int i = 0; i < key.length(); i++) { //パスが存在しない場合は、新しいノードを作成します if (curr->character[key[i]] == nullptr) { curr->character[key[i]] = new Trie(); } //次のノードに移動します curr = curr->character[key[i]]; } //現在のノードをリーフとしてマークします curr->isLeaf = true; } //Trie内のキーを検索するための反復関数。 trueを返します //キーがTrieで見つかった場合;それ以外の場合は、falseを返します bool Trie::search(string key) { // Trieが空の場合、falseを返します if (this == nullptr) { return false; } Trie* curr = this; for (int i = 0; i < key.length(); i++) { //次のノードに移動します curr = curr->character[key[i]]; //文字列が無効な場合(Trieのパスの終わりに到達) if (curr == nullptr) { return false; } } //現在のノードがリーフであり、 //文字列の終わりに到達しました return curr->isLeaf; } //指定されたノードに子がある場合はtrueを返します bool Trie::haveChildren(Trie const* curr) { for (int i = 0; i < CHAR_SIZE; i++) { if (curr->character[i]) { return true; //子が見つかりました } } return false; } //Trieのキーを削除する再帰的関数 bool Trie::deletion(Trie*& curr, string key) { //Trieが空の場合に戻る if (curr == nullptr) { return false; } //キーの終わりに達していない場合 if (key.length()) { //キーの次の文字に対応するノードに対して繰り返します // trueが返された場合は、現在のノードを削除します(リーフ以外の場合) if (curr != nullptr && curr->character[key[0]] != nullptr && deletion(curr->character[key[0]], key.substr(1)) && curr->isLeaf == false) { if (!haveChildren(curr)) { delete curr; curr = nullptr; return true; } else { return false; } } } //キーの終わりに達した場合 if (key.length() == 0 && curr->isLeaf) { //現在のノードがリーフノードであり、子がない場合 if (!haveChildren(curr)) { //現在のノードを削除します delete curr; curr = nullptr; //非リーフの親ノードを削除します return true; } //現在のノードがリーフノードであり、子がある場合 else { //現在のノードを非リーフノードとしてマークします(削除しないでください) curr->isLeaf = false; //親ノードを削除しない return false; } } return false; } //Trieデータ構造のC++実装 int main() { Trie* head = new Trie(); head->insert("hello"); cout << head->search("hello") << " "; //印刷1 head->insert("helloworld"); cout << head->search("helloworld") << " "; //印刷1 cout << head->search("helll") << " "; // 0を出力します(見つかりません) head->insert("hell"); cout << head->search("hell") << " "; //印刷1 head->insert("h"); cout << head->search("h"); //印刷1 cout << endl; head->deletion(head, "hello"); cout << head->search("hello") << " "; //0を出力します cout << head->search("helloworld") << " "; //印刷1 cout << head->search("hell"); //印刷1 cout << endl; head->deletion(head, "h"); cout << head->search("h") << " "; //0を出力します cout << head->search("hell") << " "; //印刷1 cout << head->search("helloworld"); //印刷1 cout << endl; head->deletion(head, "helloworld"); cout << head->search("helloworld") << " "; //0を出力します cout << head->search("hell") << " "; //印刷1 head->deletion(head, "hell"); cout << head->search("hell"); //0を出力します cout << endl; if (head == nullptr) { cout << "Trie empty!!\n"; //Trieは空になりました } cout << head->search("hell"); //0を出力します return 0; } |
出力:
1 1 0 1 1
0 1 1
0 1 1
0 1 0
Trie empty!!
0
挿入、削除、および検索操作のためのTrieデータ構造の時間計算量は次のとおりです。 O(n)、 どこ n キーの長さです。
Trieデータ構造のスペースの複雑さは O(N × M × C)、 どこ N 文字列の総数です。 M は文字列の最大長であり、 C アルファベットのサイズです。
以下も参照してください。