Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

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

Open
Labels
@SimonUnge

Description

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

    Projects

    No projects

    Milestone

    No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

        AltStyle によって変換されたページ (->オリジナル) /