a radix tree is a data structure that represents a spaceoptimized trie prefix tree in whicheach node that is the only child is merged with its parent https en wikipedia orgwikiradixtree mapping from the first character of the prefix of the node a node will be a leaf if the tree contains its word compute the common substring of the prefix of the node and a word args word str word to compare returns str str str common substring remaining prefix remaining word radixnodemyprefix matchmystring my prefix string insert many words in the tree args words liststr list of words radixnodemyprefix insertmanymystring hello insert a word into the tree args word str word to insert radixnodemyprefix insertmystring root radixnode root insertmany myprefix myprefixa myprefixaa root printtree myprefix leaf a leaf a leaf case 1 if the word is the prefix of the node solution we set the current node as leaf case 2 the node has no edges that have a prefix to the word solution we create an edge from the current node to a new one containing the word case 3 the node prefix is equal to the matching solution we insert remaining word on the next node case 4 the word is greater equal to the matching solution create a node in between both nodes change prefixes and add the new node for the remaining word returns if the word is on the tree args word str word to check returns bool true if the word appears on the tree radixnodemyprefix findmystring false if there is remaining prefix the word can t be on the tree this applies when the word and the prefix are equal we have word remaining so we check the next node deletes a word from the tree if it exists args word str word to be deleted returns bool true if the word was found and deleted false if word is not found radixnodemyprefix deletemystring false if there is remaining prefix the word can t be on the tree we have word remaining so we check the next node if it is not a leaf we don t have to delete we delete the nodes if no edges go from it we merge the current node with its only child if there is more than 1 edge we just mark it as nonleaf if there is 1 edge we merge it with its child print the tree args height int optional height of the printed node pytests mapping from the first character of the prefix of the node a node will be a leaf if the tree contains its word compute the common substring of the prefix of the node and a word args word str word to compare returns str str str common substring remaining prefix remaining word radixnode myprefix match mystring my prefix string insert many words in the tree args words list str list of words radixnode myprefix insert_many mystring hello 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 a leaf a leaf case 1 if the word is the prefix of the node solution we set the current node as leaf case 2 the node has no edges that have a prefix to the word solution we create an edge from the current node to a new one containing the word case 3 the node prefix is equal to the matching solution we insert remaining word on the next node case 4 the word is greater equal to the matching solution create a node in between both nodes change prefixes and add the new node for the remaining word returns if the word is on the tree args word str word to check returns bool true if the word appears on the tree radixnode myprefix find mystring false if there is remaining prefix the word can t be on the tree this applies when the word and the prefix are equal we have word remaining so we check the next node deletes a word from the tree if it exists args word str word to be deleted returns bool true if the word was found and deleted false if word is not found radixnode myprefix delete mystring false if there is remaining prefix the word can t be on the tree we have word remaining so we check the next node if it is not a leaf we don t have to delete we delete the nodes if no edges go from it we merge the current node with its only child if there is more than 1 edge we just mark it as non leaf if there is 1 edge we merge it with its child print the tree args height int optional height of the printed node pytests
class RadixNode:
    def __init__(self, prefix: str = "", is_leaf: bool = False) -> None:
        
        self.nodes: dict[str, RadixNode] = {}

        
        self.is_leaf = is_leaf

        self.prefix = prefix

    def match(self, word: str) -> tuple[str, str, str]:
        
        x = 0
        for q, w in zip(self.prefix, word):
            if q != w:
                break

            x += 1

        return self.prefix[:x], self.prefix[x:], word[x:]

    def insert_many(self, words: list[str]) -> None:
        
        for word in words:
            self.insert(word)

    def insert(self, word: str) -> None:
        
        
        
        if self.prefix == word and not self.is_leaf:
            self.is_leaf = True

        
        
        
        elif word[0] not in self.nodes:
            self.nodes[word[0]] = RadixNode(prefix=word, is_leaf=True)

        else:
            incoming_node = self.nodes[word[0]]
            matching_string, remaining_prefix, remaining_word = incoming_node.match(
                word
            )

            
            
            if remaining_prefix == "":
                self.nodes[matching_string[0]].insert(remaining_word)

            
            
            
            else:
                incoming_node.prefix = remaining_prefix

                aux_node = self.nodes[matching_string[0]]
                self.nodes[matching_string[0]] = RadixNode(matching_string, False)
                self.nodes[matching_string[0]].nodes[remaining_prefix[0]] = aux_node

                if remaining_word == "":
                    self.nodes[matching_string[0]].is_leaf = True
                else:
                    self.nodes[matching_string[0]].insert(remaining_word)

    def find(self, word: str) -> bool:
        
        incoming_node = self.nodes.get(word[0], None)
        if not incoming_node:
            return False
        else:
            matching_string, remaining_prefix, remaining_word = incoming_node.match(
                word
            )
            
            if remaining_prefix != "":
                return False
            
            elif remaining_word == "":
                return incoming_node.is_leaf
            
            else:
                return incoming_node.find(remaining_word)

    def delete(self, word: str) -> bool:
        
        incoming_node = self.nodes.get(word[0], None)
        if not incoming_node:
            return False
        else:
            matching_string, remaining_prefix, remaining_word = incoming_node.match(
                word
            )
            
            if remaining_prefix != "":
                return False
            
            elif remaining_word != "":
                return incoming_node.delete(remaining_word)
            else:
                
                if not incoming_node.is_leaf:
                    return False
                else:
                    
                    if len(incoming_node.nodes) == 0:
                        del self.nodes[word[0]]
                        
                        if len(self.nodes) == 1 and not self.is_leaf:
                            merging_node = next(iter(self.nodes.values()))
                            self.is_leaf = merging_node.is_leaf
                            self.prefix += merging_node.prefix
                            self.nodes = merging_node.nodes
                    
                    elif len(incoming_node.nodes) > 1:
                        incoming_node.is_leaf = False
                    
                    else:
                        merging_node = next(iter(incoming_node.nodes.values()))
                        incoming_node.is_leaf = merging_node.is_leaf
                        incoming_node.prefix += merging_node.prefix
                        incoming_node.nodes = merging_node.nodes

                    return True

    def print_tree(self, height: int = 0) -> None:
        
        if self.prefix != "":
            print("-" * height, self.prefix, "  (leaf)" if self.is_leaf else "")

        for value in self.nodes.values():
            value.print_tree(height + 1)


def test_trie() -> bool:
    words = "banana bananas bandana band apple all beast".split()
    root = RadixNode()
    root.insert_many(words)

    assert all(root.find(word) for word in words)
    assert not root.find("bandanas")
    assert not root.find("apps")
    root.delete("all")
    assert not root.find("all")
    root.delete("banana")
    assert not root.find("banana")
    assert root.find("bananas")

    return True


def pytests() -> None:
    assert test_trie()


def main() -> None:
    
    root = RadixNode()
    words = "banana bananas bandanas bandana band apple all beast".split()
    root.insert_many(words)

    print("Words:", words)
    print("Tree:")
    root.print_tree()


if __name__ == "__main__":
    main()