Skip to content

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

Description

@SimonUnge

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions