Trie tree
A Trie tree is a search tree, also known as a dictionary tree or word lookup tree. It is also called a prefix tree because the descendants of a node have a common prefix. Its key is a string, can achieve efficient query and insert. The time complexity is O(k), where k is the length of a string. The disadvantage is that large numbers of strings without a common prefix consume memory. Its core idea is to reduce unnecessary character comparison and make the query efficient. Use space for time and use common prefixes to improve query efficiency.
Trie tree characteristics
- The root node contains no characters, and the other nodes contain only one character per node.
- The characters in the path from the root node to a node are the string corresponding to that node.
- All children of each node have different characters.
The insert
Insert he, him, his, she, her, hers. Start inserting he string with h as the first character. The tree is empty, so create an empty root node first.
Then, starting from the root node, there are no h children, so create a child node H.
Insert the second character e from the h node.
Node h does not have child node E. Create child node E. The node is marked as a word flag to complete the he string insertion.
Then insert the him string, starting at the root node, and find that h child nodes already exist.
Let’s go to the h child.
Continue with the second character I, because h does not have child I, so create child I.
Process the third character m, because there is no child m for node I, and create child M. And marks the node as a word flag to complete the HIM insert.
Then insert his string, starting at the root node, and find that h child node already exists.
Let’s go to the h child.
Continuing with the second character I, node H already has a child node I, so move on to node I.
The third character s is processed, because there is no child s for node I, so child S is created. And mark the node as a word flag to complete his insertion.
Continue inserting the she string, starting at the root node. The first character s is processed and the child s node is found to be nonexistent, so the s node is created.
Then process the second character h, s node does not have h child node, create h node.
Continue with the third character e, which is created because there are no e children on node H. And marks the node as a word flag, thus completing the she string insertion.
Similarly, insert her and HERS strings into the tree, resulting in the following.
Query operation
Find the HI string, starting at the root node.
The root node has h child nodes. Move to H node.
Go ahead and look for the I child node, it exists, but I doesn’t have a word flag, so the hi string doesn’t exist.
Look for his string, starting at the root node.
The root node has h child nodes. Move to H node.
Node H has child node I. Move to node I.
Continue to look for the s child node, exists, and the S node is a word flag, so find his string.
If you look for the hist string, the final t is not found, so the string does not exist.
Delete operation
Is a
Delete the she string and look for the first character S starting at the root node.
Locate the s child node, move down to the S node, and continue looking for the character H.
Locate the h child node, move down to the H node, and continue looking for the character E.
Find e. The she string has been found. Remove the word mark from e.
Node E is found to be a leaf node and deleted.
After deletion, it was found that node H was a leaf node and not a word symbol, so it was deleted.
After the deletion, it was found that the S node was a leaf node and it was not a word flag, so it was deleted to complete the deletion of the SHE string.
Case 2
Delete her string and look for the first character H starting at the root node.
Locate the h child node, move down to the H node, and continue looking for the character E.
Find e child node, move down to e node, continue to look for the character r.
Find the r child node, then complete the string search, because it is not a leaf node, just remove its word flag.
Is three
Delete his and look for the first character H from the root node.
Find h child node, move down to h node, continue to look for character I.
Locate the I child node, move down to the I node, and continue looking for the character S.
The s child node is found, at which point the entire string lookup is completed.
After the deletion, node S is found to be a leaf node, and then it is deleted.
After deletion, node I was found to be a non-leaf node, so the deletion was stopped and the deletion of his string was completed.
If you like this kind of explanation, then recommend a book on Data structure Algorithms, buy the author’s book!
Author profile: Seaboat, good at artificial intelligence, computer science, mathematical principles, basic algorithms. Books: Anatomy of Tomcat kernel Design, Graphic Data Structure and Algorithm, Popular Science of Artificial Intelligence principles, Graphic Java Concurrency Principles.
Focus on artificial Intelligence, reading and feeling, talk about mathematics, computer Science, distributed, machine learning, deep learning, natural language processing, Algorithms and Data Structures, Java depth, Tomcat kernel, etc.