Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

data_structures/trie/radix_tree.py wont really end up in 'case 1' for insert #11316

Open
SimonUnge opened this issue Mar 7, 2024 · 1 comment · May be fixed by #11385
Open

data_structures/trie/radix_tree.py wont really end up in 'case 1' for insert #11316

SimonUnge opened this issue Mar 7, 2024 · 1 comment · May be fixed by #11385
Labels

Comments

@SimonUnge
Copy link

Repository commit

2e405f3

Python version (python --version)

Python 3.11.6

Dependencies version (pip freeze)

n/a

Expected behavior

root_node = RadixNode()
root_node.insert('fooaaa')
root_node.insert('foobbb')
root_node.insert('foo')

Should work., i.e should have a structure like this

root_node.print_tree()
- foo (leaf)
-- aaa   (leaf)
-- bbb   (leaf)

Actual behavior

root_node.insert("foo")
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[5], line 1
----> 1 root_node.insert("foo")

File ~/git/python/radix/radix.py:85, in RadixNode.insert(self, word)
     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 # Case 5: The word is greater equal to the matching
     87 # Solution: Create a node in between both nodes, change
     88 # prefixes and add the new node for the remaining word
     89 else:
     90     incoming_node.prefix = remaining_prefix

File ~/git/python/radix/radix.py:73, in RadixNode.insert(self, word)
     68     self.is_leaf = True
     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)
     76 else:

IndexError: string index out of range

@SimonUnge SimonUnge added the bug label Mar 7, 2024
@SimonUnge
Copy link
Author

something like this might fix it?

...
        else:
            incoming_node = self.nodes[word[0]]
            matching_string, remaining_prefix, remaining_word = incoming_node.match(
                word
            )
                                      
            if remaining_prefix == "" and not remaining_word == "": # <---- better check
                self.nodes[matching_string[0]].insert(remaining_word)
                                                                        
            elif remaining_prefix == "":  # <--- make sure we end in case 1 next lap 
                self.nodes[matching_string[0]].insert(matching_string)

covid-in pushed a commit to covid-in/TheAlgorithms-Python that referenced this issue Apr 25, 2024
@covid-in covid-in linked a pull request Apr 25, 2024 that will close this issue
15 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants
@SimonUnge and others