data_structures.trie.radix_tree
===============================

.. py:module:: data_structures.trie.radix_tree

.. autoapi-nested-parse::

   A Radix Tree is a data structure that represents a space-optimized
   trie (prefix tree) in whicheach node that is the only child is merged
   with its parent [https://en.wikipedia.org/wiki/Radix_tree]



Classes
-------

.. autoapisummary::

   data_structures.trie.radix_tree.RadixNode


Functions
---------

.. autoapisummary::

   data_structures.trie.radix_tree.main
   data_structures.trie.radix_tree.pytests
   data_structures.trie.radix_tree.test_trie


Module Contents
---------------

.. py:class:: RadixNode(prefix: str = '', is_leaf: bool = False)

   .. py:method:: delete(word: str) -> bool

      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



   .. py:method:: find(word: str) -> bool

      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



   .. py:method:: insert(word: str) -> None

      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)



   .. py:method:: insert_many(words: list[str]) -> None

      Insert many words in the tree

      Args:
          words (list[str]): list of words

      >>> RadixNode("myprefix").insert_many(["mystring", "hello"])



   .. py:method:: match(word: str) -> tuple[str, str, str]

      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')



   .. py:method:: print_tree(height: int = 0) -> None

      Print the tree

      Args:
          height (int, optional): Height of the printed node



   .. py:attribute:: is_leaf
      :value: False



   .. py:attribute:: nodes
      :type:  dict[str, RadixNode]


   .. py:attribute:: prefix
      :value: ''



.. py:function:: main() -> None

   >>> pytests()


.. py:function:: pytests() -> None

.. py:function:: test_trie() -> bool