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 which each 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
   data_structures.trie.radix_tree.TestRadixNode


Functions
---------

.. autoapisummary::

   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 whether 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:class:: TestRadixNode(methodName='runTest')

   Bases: :py:obj:`unittest.TestCase`


   A class whose instances are single test cases.

   By default, the test code itself should be placed in a method named
   'runTest'.

   If the fixture may be used for many test cases, create as
   many test methods as are needed. When instantiating such a TestCase
   subclass, specify in the constructor arguments the name of the test method
   that the instance is to execute.

   Test authors should subclass TestCase for their own tests. Construction
   and deconstruction of the test's environment ('fixture') can be
   implemented by overriding the 'setUp' and 'tearDown' methods respectively.

   If it is necessary to override the __init__ method, the base class
   __init__ method must always be called. It is important that subclasses
   should not change the signature of their __init__ method, since instances
   of the classes are instantiated automatically by parts of the framework
   in order to be run.

   When subclassing TestCase, you can set these attributes:
   * failureException: determines which exception will be raised when
       the instance's assertion methods fail; test methods raising this
       exception will be deemed to have 'failed' rather than 'errored'.
   * longMessage: determines whether long messages (including repr of
       objects used in assert methods) will be printed on failure in *addition*
       to any explicit message passed.
   * maxDiff: sets the maximum length of a diff in failure messages
       by assert methods using difflib. It is looked up as an instance
       attribute so can be configured by individual tests if required.


   .. py:method:: test_trie() -> None


   .. py:method:: test_trie_2() -> None

      Now add a new test case that inserts
      foobbb, fooaaa, foo in the given order and checks
      for different assertions



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