In this post, we will discuss C++ implementation of Trie Data Structure which supports insertion, deletion and search operations.
We know that Trie is a tree-based data structure, which can be used for efficient retrieval of a key in a huge set of strings. In the previous post, we have discussed about Trie data structure in detail and also covered its implementation in C. In this post, C++ implementation of Trie data structure is discussed which is way more cleaner than the C implementation.
Below is C++ implementation of Trie data structure which supports insertion, deletion and search operations.
|
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 |
#include <iostream> // define character size #define CHAR_SIZE 128 // A Class representing a Trie node class Trie { public: bool isLeaf; Trie* character[CHAR_SIZE]; // Constructor Trie() { this->isLeaf = false; for (int i = 0; i < CHAR_SIZE; i++) this->character[i] = nullptr; } void insert(std::string); bool deletion(Trie*&, std::string); bool search(std::string); bool haveChildren(Trie const*); }; // Iterative function to insert a key in the Trie void Trie::insert(std::string key) { // start from root node Trie* curr = this; for (int i = 0; i < key.length(); i++) { // create a new node if path doesn't exists if (curr->character[key[i]] == nullptr) curr->character[key[i]] = new Trie(); // go to next node curr = curr->character[key[i]]; } // mark current node as leaf curr->isLeaf = true; } // Iterative function to search a key in Trie. It returns true // if the key is found in the Trie, else it returns false bool Trie::search(std::string key) { // return false if Trie is empty if (this == nullptr) return false; Trie* curr = this; for (int i = 0; i < key.length(); i++) { // go to next node curr = curr->character[key[i]]; // if string is invalid (reached end of path in Trie) if (curr == nullptr) return false; } // if current node is a leaf and we have reached the // end of the string, return true return curr->isLeaf; } // returns true if given node has any children bool Trie::haveChildren(Trie const* curr) { for (int i = 0; i < CHAR_SIZE; i++) if (curr->character[i]) return true; // child found return false; } // Recursive function to delete a key in the Trie bool Trie::deletion(Trie*& curr, std::string key) { // return if Trie is empty if (curr == nullptr) return false; // if we have not reached the end of the key if (key.length()) { // recurse for the node corresponding to next character in the key // and if it returns true, delete current node (if it is non-leaf) 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 we have reached the end of the key if (key.length() == 0 && curr->isLeaf) { // if current node is a leaf node and don't have any children if (!haveChildren(curr)) { // delete current node delete curr; curr = nullptr; // delete non-leaf parent nodes return true; } // if current node is a leaf node and have children else { // mark current node as non-leaf node (DON'T DELETE IT) curr->isLeaf = false; // don't delete its parent nodes return false; } } return false; } // C++ implementation of Trie Data Structure int main() { Trie* head = new Trie(); head->insert("hello"); std::cout << head->search("hello") << " "; // print 1 head->insert("helloworld"); std::cout << head->search("helloworld") << " "; // print 1 std::cout << head->search("helll") << " "; // print 0 (Not found) head->insert("hell"); std::cout << head->search("hell") << " "; // print 1 head->insert("h"); std::cout << head->search("h"); // print 1 std::cout << std::endl; head->deletion(head, "hello"); std::cout << head->search("hello") << " "; // print 0 std::cout << head->search("helloworld") << " "; // print 1 std::cout << head->search("hell"); // print 1 std::cout << std::endl; head->deletion(head, "h"); std::cout << head->search("h") << " "; // print 0 std::cout << head->search("hell") << " "; // print 1 std::cout << head->search("helloworld"); // print 1 std::cout << std::endl; head->deletion(head, "helloworld"); std::cout << head->search("helloworld") << " "; // print 0 std::cout << head->search("hell") << " "; // print 1 head->deletion(head, "hell"); std::cout << head->search("hell"); // print 0 std::cout << std::endl; if (head == nullptr) std::cout << "Trie empty!!\n"; // Trie is empty now std::cout << head->search("hell"); // print 0 return 0; } |
Output:
1 1 0 1 1
0 1 1
0 1 1
0 1 0
Trie empty!!
0
The Time complexity of a Trie data structure for insertion, deletion and search operation is O(n) where n is key length.
The space complexity of a Trie data structure is O(N*M*C) where N is the number of strings and M is the highest length of the string and C is the size of the alphabet.
Also see:
1. Memory efficient Trie Implementation in C++ using Map (Insert, Search and Delete)
2. Java Implementation of Trie Data Structure
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply