Insert a word into the tree Args: word (str): word to insert >>> RadixNode("myprefix").insert("mystring") >>> root = RadixNode() >>> root.insert_many(['myprefix', 'myprefixA', 'myprefixAA']) >>> root.print_tree() - myprefix (leaf)
(self, word: str)
| 48 | self.insert(word) |
| 49 | |
| 50 | def insert(self, word: str) -> None: |
| 51 | """Insert a word into the tree |
| 52 | |
| 53 | Args: |
| 54 | word (str): word to insert |
| 55 | |
| 56 | >>> RadixNode("myprefix").insert("mystring") |
| 57 | |
| 58 | >>> root = RadixNode() |
| 59 | >>> root.insert_many(['myprefix', 'myprefixA', 'myprefixAA']) |
| 60 | >>> root.print_tree() |
| 61 | - myprefix (leaf) |
| 62 | -- A (leaf) |
| 63 | --- A (leaf) |
| 64 | """ |
| 65 | # Case 1: If the word is the prefix of the node |
| 66 | # Solution: We set the current node as leaf |
| 67 | if self.prefix == word and not self.is_leaf: |
| 68 | self.is_leaf = True |
| 69 | |
| 70 | # Case 2: The node has no edges that have a prefix to the word |
| 71 | # Solution: We create an edge from the current node to a new one |
| 72 | # containing the word |
| 73 | elif word[0] not in self.nodes: |
| 74 | self.nodes[word[0]] = RadixNode(prefix=word, is_leaf=True) |
| 75 | |
| 76 | else: |
| 77 | incoming_node = self.nodes[word[0]] |
| 78 | matching_string, remaining_prefix, remaining_word = incoming_node.match( |
| 79 | word |
| 80 | ) |
| 81 | |
| 82 | # Case 3: The node prefix is equal to the matching |
| 83 | # Solution: We insert remaining word on the next node |
| 84 | if remaining_prefix == "": |
| 85 | self.nodes[matching_string[0]].insert(remaining_word) |
| 86 | |
| 87 | # Case 4: The word is greater equal to the matching |
| 88 | # Solution: Create a node in between both nodes, change |
| 89 | # prefixes and add the new node for the remaining word |
| 90 | else: |
| 91 | incoming_node.prefix = remaining_prefix |
| 92 | |
| 93 | aux_node = self.nodes[matching_string[0]] |
| 94 | self.nodes[matching_string[0]] = RadixNode(matching_string, False) |
| 95 | self.nodes[matching_string[0]].nodes[remaining_prefix[0]] = aux_node |
| 96 | |
| 97 | if remaining_word == "": |
| 98 | self.nodes[matching_string[0]].is_leaf = True |
| 99 | else: |
| 100 | self.nodes[matching_string[0]].insert(remaining_word) |
| 101 | |
| 102 | def find(self, word: str) -> bool: |
| 103 | """Returns if the word is on the tree |
no test coverage detected