Trie-Datenstruktur in C/C++
Eine Trie-Datenstruktur fungiert als Container für ein dynamisches Array. In diesem Artikel werden wir uns ansehen, wie wir ein Trie in C/C++ implementieren können.
Dieses basiert auf der Baumdatenstruktur, speichert aber nicht unbedingt Schlüssel. Hier hat jeder Node nur einen Wert, der anhand der Position definiert wird.
Der Wert eines jeden Nodes bezeichnet also das Präfix, denn es ist der Punkt vom Wurzel-Node aus nach einer Reihe von Übereinstimmungen.
Wir bezeichnen solche Übereinstimmungen als Präfix-Übereinstimmungen. Daher können wir Tries verwenden, um Wörter eines Wörterbuchs zu speichern!
Aus all diesen Gründen werden die Versuche als Präfixbäume bezeichnet. Lassen Sie uns nun verstehen, wie wir diese Datenstruktur aus der Sicht eines Programmierers implementieren können.
Implementierung einer Trie-Datenstruktur in C/C++
Lassen Sie uns zunächst die Trie-Struktur aufschreiben. Ein Trie-Node hat vor allem zwei Komponenten:
- Es sind Kinder
- Eine Markierung zur Kennzeichnung eines Leaf Nodes.
Da wir das Trie aber auch ausdrucken werden, wird es einfacher sein, wenn wir ein weiteres Attribut im Datenteil speichern können.
// The number of children for each node
// We will construct a N-ary tree and make it
// a Trie
// Since we have 26 english letters, we need
// 26 children per node
#define N 26
typedef struct TrieNode TrieNode;
struct TrieNode {
// The Trie Node Structure
// Each node has N children, starting from the root
// and a flag to check if it's a leaf node
char data; // Storing for printing purposes only
TrieNode* children[N];
int is_leaf;
};
Nachdem wir nun unsere Struktur definiert haben, wollen wir Funktionen schreiben, um einen TrieNode im Speicher zu initialisieren und seinen Zeiger wieder freizugeben.
TrieNode* make_trienode(char data) {
// Allocate memory for a TrieNode
TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
for (int i=0; i<N; i++) node->children[i] = NULL;
node->is_leaf = 0;
node->data = data;
return node;
}
void free_trienode(TrieNode* node) {
// Free the trienode sequence
for(int i=0; i<N; i++) { if (node->children[i] != NULL) {
free_trienode(node->children[i]);
}
}
free(node);
}
Einfügen eines Wortes in die Trie
Wir werden nun die Funktion insert_trie() schreiben, die einen Zeiger auf den Wurzel Node (oberster Node) nimmt und ein Wort in das Trie einfügt.
Der Einfügevorgang ist einfach. Sie durchläuft das Wort Zeichen für Zeichen und wertet die relative Position aus.
Zum Beispiel hat ein Zeichen b die Position 1, ist also das zweite Kind.
for (int i=0; word[i] != '\0'; i++) {
// Get the relative position in the alphabet list
int idx = (int) word[i] - 'a';
if (temp->children[idx] == NULL) {
// If the corresponding child doesn't exist,
// simply create that child!
temp->children[idx] = make_trienode(word[i]);
}
else {
// Do nothing. The node already exists
}
Wir werden das Präfix Zeichen für Zeichen abgleichen und einfach einen Node initialisieren, wenn er nicht vorhanden ist.
Ansonsten bewegen wir uns einfach weiter die Kette hinunter, bis wir alle Zeichen abgeglichen haben.
temp = temp->children[idx];
Schließlich haben wir alle nicht übereinstimmenden Zeichen eingefügt und erhalten das aktualisierte Trie zurück.
TrieNode* insert_trie(TrieNode* root, char* word) {
// Inserts the word onto the Trie
// ASSUMPTION: The word only has lower case characters
TrieNode* temp = root;
for (int i=0; word[i] != '\0'; i++) {
// Get the relative position in the alphabet list
int idx = (int) word[i] - 'a';
if (temp->children[idx] == NULL) {
// If the corresponding child doesn't exist,
// simply create that child!
temp->children[idx] = make_trienode(word[i]);
}
else {
// Do nothing. The node already exists
}
// Go down a level, to the child referenced by idx
// since we have a prefix match
temp = temp->children[idx];
}
// At the end of the word, mark this node as the leaf node
temp->is_leaf = 1;
return root;
}
Suche nach einem Wort im Trie
Nachdem wir nun das Einfügen in ein Trie implementiert haben, wollen wir uns die Suche nach einem bestimmten Muster ansehen.
Wir versuchen, die Zeichenkette Zeichen für Zeichen abzugleichen, wobei wir die gleiche Strategie wie oben anwenden.
Wenn wir das Ende der Kette erreicht haben und noch keine Übereinstimmung gefunden haben, bedeutet dies, dass die Zeichenfolge nicht existiert, da keine vollständige Präfixübereinstimmung durchgeführt wurde.
Damit das Ergebnis korrekt ist, muss unser Muster genau übereinstimmen, und nachdem wir den Abgleich beendet haben, müssen wir einen BlattNode erreichen.
int search_trie(TrieNode* root, char* word)
{
// Searches for word in the Trie
TrieNode* temp = root;
for(int i=0; word[i]!='\0'; i++)
{
int position = word[i] - 'a';
if (temp->children[position] == NULL)
return 0;
temp = temp->children[position];
}
if (temp != NULL && temp->is_leaf == 1)
return 1;
return 0;
}
Okay, wir haben also die Einfüge- und Suchprozeduren fertiggestellt.
Um das zu testen, schreiben wir zunächst eine print_tree()-Funktion, die die Daten jedes Nodes ausgibt.
void print_trie(TrieNode* root) {
// Prints the nodes of the trie
if (!root)
return;
TrieNode* temp = root;
printf("%c -> ", temp->data);
for (int i=0; i<N; i++) { print_trie(temp->children[i]);
}
}
Nun, da wir das getan haben, lassen wir einfach das komplette Programm bis jetzt laufen, um zu überprüfen, ob es richtig funktioniert.
#include
#include
#include
// The number of children for each node
// We will construct a N-ary tree and make it
// a Trie
// Since we have 26 english letters, we need
// 26 children per node
#define N 26
typedef struct TrieNode TrieNode;
struct TrieNode {
// The Trie Node Structure
// Each node has N children, starting from the root
// and a flag to check if it's a leaf node
char data; // Storing for printing purposes only
TrieNode* children[N];
int is_leaf;
};
TrieNode* make_trienode(char data) {
// Allocate memory for a TrieNode
TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
for (int i=0; i<N; i++) node->children[i] = NULL;
node->is_leaf = 0;
node->data = data;
return node;
}
void free_trienode(TrieNode* node) {
// Free the trienode sequence
for(int i=0; i<N; i++) { if (node->children[i] != NULL) {
free_trienode(node->children[i]);
}
else {
continue;
}
}
free(node);
}
TrieNode* insert_trie(TrieNode* root, char* word) {
// Inserts the word onto the Trie
// ASSUMPTION: The word only has lower case characters
TrieNode* temp = root;
for (int i=0; word[i] != '\0'; i++) {
// Get the relative position in the alphabet list
int idx = (int) word[i] - 'a';
if (temp->children[idx] == NULL) {
// If the corresponding child doesn't exist,
// simply create that child!
temp->children[idx] = make_trienode(word[i]);
}
else {
// Do nothing. The node already exists
}
// Go down a level, to the child referenced by idx
// since we have a prefix match
temp = temp->children[idx];
}
// At the end of the word, mark this node as the leaf node
temp->is_leaf = 1;
return root;
}
int search_trie(TrieNode* root, char* word)
{
// Searches for word in the Trie
TrieNode* temp = root;
for(int i=0; word[i]!='\0'; i++)
{
int position = word[i] - 'a';
if (temp->children[position] == NULL)
return 0;
temp = temp->children[position];
}
if (temp != NULL && temp->is_leaf == 1)
return 1;
return 0;
}
void print_trie(TrieNode* root) {
// Prints the nodes of the trie
if (!root)
return;
TrieNode* temp = root;
printf("%c -> ", temp->data);
for (int i=0; i<N; i++) { print_trie(temp->children[i]);
}
}
void print_search(TrieNode* root, char* word) {
printf("Searching for %s: ", word);
if (search_trie(root, word) == 0)
printf("Not Found\n");
else
printf("Found!\n");
}
int main() {
// Driver program for the Trie Data Structure Operations
TrieNode* root = make_trienode('\0');
root = insert_trie(root, "hello");
root = insert_trie(root, "hi");
root = insert_trie(root, "teabag");
root = insert_trie(root, "teacan");
print_search(root, "tea");
print_search(root, "teabag");
print_search(root, "teacan");
print_search(root, "hi");
print_search(root, "hey");
print_search(root, "hello");
print_trie(root);
free_trienode(root);
return 0;
}
Nach dem Kompilieren mit dem gcc-Compiler erhalten Sie die folgende Ausgabe.
Searching for tea: Not Found
Searching for teabag: Found!
Searching for teacan: Found!
Searching for hi: Found!
Searching for hey: Not Found
Searching for hello: Found!
-> h -> e -> l -> l -> o -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n ->
Es mag zwar offensichtlich sein, wie es gedruckt wird, aber der Hinweis ist, sich die print_tree()-Methode anzusehen. Da diese den aktuellen Node und dann alle seine Kinder ausgibt, zeigt die Reihenfolge dies an.
So, jetzt implementieren wir die delete Methode!
Löschen eines Wortes aus einem Trie
Diese Methode ist etwas kniffliger als die anderen beiden Methoden.
Es gibt keine Art von Formatierungsalgorithmus, da es keine explizite Art und Weise gibt, in der wir die Schlüssel und Werte speichern.
Für die Zwecke dieses Artikels werde ich jedoch nur Löschungen behandeln, wenn das zu löschende Wort ein BlattNode ist. Das heißt, es muss bis zu einem BlattNode mit dem Präfix übereinstimmen.
Fangen wir also an. Unsere Signatur für die delete-Funktion wird sein:
TrieNode* delete_trie(TrieNode* root, char* word);
Wie bereits erwähnt, wird nur gelöscht, wenn der Präfixabgleich bis zu einem BlattNode durchgeführt wird. Schreiben wir also eine weitere Funktion is_leaf_node(), die dies für uns erledigt.
int is_leaf_node(TrieNode* root, char* word) {
// Checks if the prefix match of word and root
// is a leaf node
TrieNode* temp = root;
for (int i=0; word[i]; i++) {
int position = (int) word[i] - 'a';
if (temp->children[position]) {
temp = temp->children[position];
}
}
return temp->is_leaf;
}
Okay, so with that completed, let’s look at the draft of our delete_trie() method.
TrieNode* delete_trie(TrieNode* root, char* word) {
// Will try to delete the word sequence from the Trie only it
// ends up in a leaf node
if (!root)
return NULL;
if (!word || word[0] == '\0')
return root;
// If the node corresponding to the match is not a leaf node,
// we stop
if (!is_leaf_node(root, word)) {
return root;
}
// TODO
}
Nach dieser Prüfung wissen wir nun, dass unser Wort in einem BlattNode enden wird.
Aber es gibt noch eine andere Situation, die wir behandeln müssen. Was ist, wenn es ein anderes Wort gibt, das eine partielle Präfixübereinstimmung mit der aktuellen Zeichenfolge hat?
Zum Beispiel haben die Wörter tea und ted eine teilweise gemeinsame Übereinstimmung bis te.
Wenn das passiert, können wir nicht einfach die gesamte Sequenz von t bis a löschen, da dann beide Ketten gelöscht werden, da sie miteinander verbunden sind!
Deshalb müssen wir den tiefsten Punkt finden, bis zu dem solche Übereinstimmungen auftreten. Erst danach können wir die verbleibende Kette löschen.
Dazu muss die längste Präfixkette gefunden werden, also schreiben wir eine weitere Funktion.
char* longest_prefix(TrieNode* root, char* word);
Damit wird die längste Übereinstimmung im Trie zurückgegeben, die nicht das aktuelle Wort (word) ist. Der folgende Code erklärt jeden Zwischenschritt in den Kommentaren.
char* find_longest_prefix(TrieNode* root, char* word) {
// Finds the longest common prefix substring of word
// in the Trie
if (!word || word[0] == '\0')
return NULL;
// Length of the longest prefix
int len = strlen(word);
// We initially set the longest prefix as the word itself,
// and try to back-track from the deepest position to
// a point of divergence, if it exists
char* longest_prefix = (char*) calloc (len + 1, sizeof(char));
for (int i=0; word[i] != '\0'; i++)
longest_prefix[i] = word[i];
longest_prefix[len] = '\0';
// If there is no branching from the root, this
// means that we're matching the original string!
// This is not what we want!
int branch_idx = check_divergence(root, longest_prefix) - 1;
if (branch_idx >= 0) {
// There is branching, We must update the position
// to the longest match and update the longest prefix
// by the branch index length
longest_prefix[branch_idx] = '\0';
longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char));
}
return longest_prefix;
}
Es gibt hier noch eine weitere Wendung! Da wir versuchen, die längste Übereinstimmung zu finden, wird der Algorithmus tatsächlich gierig die ursprüngliche Zeichenfolge selbst abgleichen! Das ist nicht das, was wir wollen.
Wir wollen die längste Übereinstimmung, die NICHT die Eingabezeichenkette ist. Daher müssen wir eine weitere Methode check_divergence() verwenden.
Diese prüft, ob es eine Verzweigung von der Wurzel zur aktuellen Position gibt, und gibt die Länge der besten Übereinstimmung zurück, die NICHT die Eingabe ist.
Wenn wir uns in der schlechten Kette befinden, die der ursprünglichen Zeichenkette entspricht, dann gibt es keine Verzweigung von diesem Punkt aus! Dies ist also eine gute Möglichkeit, diesen unangenehmen Punkt zu vermeiden, indem man check_divergence() verwendet.
int check_divergence(TrieNode* root, char* word) {
// Checks if there is branching at the last character of word
//and returns the largest position in the word where branching occurs
TrieNode* temp = root;
int len = strlen(word);
if (len == 0)
return 0;
// We will return the largest index where branching occurs
int last_index = 0;
for (int i=0; i < len; i++) { int position = word[i] - 'a'; if (temp->children[position]) {
// If a child exists at that position
// we will check if there exists any other child
// so that branching occurs
for (int j=0; j<N; j++) { if (j != position && temp->children[j]) {
// We've found another child! This is a branch.
// Update the branch position
last_index = i + 1;
break;
}
}
// Go to the next child in the sequence
temp = temp->children[position];
}
}
return last_index;
}
Schließlich haben wir sichergestellt, dass wir nicht einfach blindlings die gesamte Kette löschen. Fahren wir also mit unserer Löschmethode fort.
TrieNode* delete_trie(TrieNode* root, char* word) {
// Will try to delete the word sequence from the Trie only it
// ends up in a leaf node
if (!root)
return NULL;
if (!word || word[0] == '\0')
return root;
// If the node corresponding to the match is not a leaf node,
// we stop
if (!is_leaf_node(root, word)) {
return root;
}
TrieNode* temp = root;
// Find the longest prefix string that is not the current word
char* longest_prefix = find_longest_prefix(root, word);
//printf("Longest Prefix = %s\n", longest_prefix);
if (longest_prefix[0] == '\0') {
free(longest_prefix);
return root;
}
// Keep track of position in the Trie
int i;
for (i=0; longest_prefix[i] != '\0'; i++) {
int position = (int) longest_prefix[i] - 'a';
if (temp->children[position] != NULL) {
// Keep moving to the deepest node in the common prefix
temp = temp->children[position];
}
else {
// There is no such node. Simply return.
free(longest_prefix);
return root;
}
}
// Now, we have reached the deepest common node between
// the two strings. We need to delete the sequence
// corresponding to word
int len = strlen(word);
for (; i < len; i++) { int position = (int) word[i] - 'a'; if (temp->children[position]) {
// Delete the remaining sequence
TrieNode* rm_node = temp->children[position];
temp->children[position] = NULL;
free_trienode(rm_node);
}
}
free(longest_prefix);
return root;
}
Der obige Code findet einfach den tiefsten Node für die Präfixübereinstimmung und löscht das verbleibende sequenzübereinstimmende Wort aus dem Trie, da dies unabhängig von jeder anderen Übereinstimmung ist.
Zeitkomplexität für die obigen Verfahren
Die Zeitkomplexität der Verfahren ist im Folgenden aufgeführt.
| Prozedur | Zeitkomplexität der Implementierung |
|---|---|
| search_trie() | O(n) -> n ist die Länge der Eingabezeichenkette |
| einfügen_trie() | O(n) -> n ist die Länge der Eingabezeichenkette |
| Löschen_trie() | O(C*n) -> C ist die Anzahl der Alphabete, n ist die Länge des Eingabewortes |
Für fast alle Fälle ist die Anzahl der Alphabete eine Konstante, so dass auch die Komplexität von delete_trie() auf O(n) reduziert ist.
Das vollständige C/C++-Programm für die Trie-Datenstruktur
Zuletzt haben wir (hoffentlich) unsere delete_trie()-Funktion fertiggestellt. Prüfen wir mit unserem Treiberprogramm, ob das, was wir geschrieben haben, richtig war.
#include
#include
#include
// The number of children for each node
// We will construct a N-ary tree and make it
// a Trie
// Since we have 26 english letters, we need
// 26 children per node
#define N 26
typedef struct TrieNode TrieNode;
struct TrieNode {
// The Trie Node Structure
// Each node has N children, starting from the root
// and a flag to check if it's a leaf node
char data; // Storing for printing purposes only
TrieNode* children[N];
int is_leaf;
};
TrieNode* make_trienode(char data) {
// Allocate memory for a TrieNode
TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
for (int i=0; i<N; i++) node->children[i] = NULL;
node->is_leaf = 0;
node->data = data;
return node;
}
void free_trienode(TrieNode* node) {
// Free the trienode sequence
for(int i=0; i<N; i++) { if (node->children[i] != NULL) {
free_trienode(node->children[i]);
}
else {
continue;
}
}
free(node);
}
TrieNode* insert_trie(TrieNode* root, char* word) {
// Inserts the word onto the Trie
// ASSUMPTION: The word only has lower case characters
TrieNode* temp = root;
for (int i=0; word[i] != '\0'; i++) {
// Get the relative position in the alphabet list
int idx = (int) word[i] - 'a';
if (temp->children[idx] == NULL) {
// If the corresponding child doesn't exist,
// simply create that child!
temp->children[idx] = make_trienode(word[i]);
}
else {
// Do nothing. The node already exists
}
// Go down a level, to the child referenced by idx
// since we have a prefix match
temp = temp->children[idx];
}
// At the end of the word, mark this node as the leaf node
temp->is_leaf = 1;
return root;
}
int search_trie(TrieNode* root, char* word)
{
// Searches for word in the Trie
TrieNode* temp = root;
for(int i=0; word[i]!='\0'; i++)
{
int position = word[i] - 'a';
if (temp->children[position] == NULL)
return 0;
temp = temp->children[position];
}
if (temp != NULL && temp->is_leaf == 1)
return 1;
return 0;
}
int check_divergence(TrieNode* root, char* word) {
// Checks if there is branching at the last character of word
// and returns the largest position in the word where branching occurs
TrieNode* temp = root;
int len = strlen(word);
if (len == 0)
return 0;
// We will return the largest index where branching occurs
int last_index = 0;
for (int i=0; i < len; i++) { int position = word[i] - 'a'; if (temp->children[position]) {
// If a child exists at that position
// we will check if there exists any other child
// so that branching occurs
for (int j=0; j<N; j++) { if (j != position && temp->children[j]) {
// We've found another child! This is a branch.
// Update the branch position
last_index = i + 1;
break;
}
}
// Go to the next child in the sequence
temp = temp->children[position];
}
}
return last_index;
}
char* find_longest_prefix(TrieNode* root, char* word) {
// Finds the longest common prefix substring of word
// in the Trie
if (!word || word[0] == '\0')
return NULL;
// Length of the longest prefix
int len = strlen(word);
// We initially set the longest prefix as the word itself,
// and try to back-tracking from the deepst position to
// a point of divergence, if it exists
char* longest_prefix = (char*) calloc (len + 1, sizeof(char));
for (int i=0; word[i] != '\0'; i++)
longest_prefix[i] = word[i];
longest_prefix[len] = '\0';
// If there is no branching from the root, this
// means that we're matching the original string!
// This is not what we want!
int branch_idx = check_divergence(root, longest_prefix) - 1;
if (branch_idx >= 0) {
// There is branching, We must update the position
// to the longest match and update the longest prefix
// by the branch index length
longest_prefix[branch_idx] = '\0';
longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char));
}
return longest_prefix;
}
int is_leaf_node(TrieNode* root, char* word) {
// Checks if the prefix match of word and root
// is a leaf node
TrieNode* temp = root;
for (int i=0; word[i]; i++) {
int position = (int) word[i] - 'a';
if (temp->children[position]) {
temp = temp->children[position];
}
}
return temp->is_leaf;
}
TrieNode* delete_trie(TrieNode* root, char* word) {
// Will try to delete the word sequence from the Trie only it
// ends up in a leaf node
if (!root)
return NULL;
if (!word || word[0] == '\0')
return root;
// If the node corresponding to the match is not a leaf node,
// we stop
if (!is_leaf_node(root, word)) {
return root;
}
TrieNode* temp = root;
// Find the longest prefix string that is not the current word
char* longest_prefix = find_longest_prefix(root, word);
//printf("Longest Prefix = %s\n", longest_prefix);
if (longest_prefix[0] == '\0') {
free(longest_prefix);
return root;
}
// Keep track of position in the Trie
int i;
for (i=0; longest_prefix[i] != '\0'; i++) {
int position = (int) longest_prefix[i] - 'a';
if (temp->children[position] != NULL) {
// Keep moving to the deepest node in the common prefix
temp = temp->children[position];
}
else {
// There is no such node. Simply return.
free(longest_prefix);
return root;
}
}
// Now, we have reached the deepest common node between
// the two strings. We need to delete the sequence
// corresponding to word
int len = strlen(word);
for (; i < len; i++) { int position = (int) word[i] - 'a'; if (temp->children[position]) {
// Delete the remaining sequence
TrieNode* rm_node = temp->children[position];
temp->children[position] = NULL;
free_trienode(rm_node);
}
}
free(longest_prefix);
return root;
}
void print_trie(TrieNode* root) {
// Prints the nodes of the trie
if (!root)
return;
TrieNode* temp = root;
printf("%c -> ", temp->data);
for (int i=0; i<N; i++) { print_trie(temp->children[i]);
}
}
void print_search(TrieNode* root, char* word) {
printf("Searching for %s: ", word);
if (search_trie(root, word) == 0)
printf("Not Found\n");
else
printf("Found!\n");
}
int main() {
// Driver program for the Trie Data Structure Operations
TrieNode* root = make_trienode('\0');
root = insert_trie(root, "hello");
root = insert_trie(root, "hi");
root = insert_trie(root, "teabag");
root = insert_trie(root, "teacan");
print_search(root, "tea");
print_search(root, "teabag");
print_search(root, "teacan");
print_search(root, "hi");
print_search(root, "hey");
print_search(root, "hello");
print_trie(root);
printf("\n");
root = delete_trie(root, "hello");
printf("After deleting 'hello'...\n");
print_trie(root);
printf("\n");
root = delete_trie(root, "teacan");
printf("After deleting 'teacan'...\n");
print_trie(root);
printf("\n");
free_trienode(root);
return 0;
}
Output
Searching for tea: Not Found
Searching for teabag: Found!
Searching for teacan: Found!
Searching for hi: Found!
Searching for hey: Not Found
Searching for hello: Found!
-> h -> e -> l -> l -> o -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n ->
After deleting 'hello'...
-> h -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n ->
After deleting 'teacan'...
-> h -> i -> t -> e -> a -> b -> a -> g ->
Damit sind wir am Ende unserer Implementierung der Trie-Datenstruktur in C/C++ angelangt. Ich weiß, dass dies eine lange Lektüre ist, aber ich hoffe, Sie haben verstanden, wie Sie diese Methoden richtig anwenden können!
