data_structures.binary_tree.treap
=================================

.. py:module:: data_structures.binary_tree.treap


Classes
-------

.. autoapisummary::

   data_structures.binary_tree.treap.Node


Functions
---------

.. autoapisummary::

   data_structures.binary_tree.treap.erase
   data_structures.binary_tree.treap.inorder
   data_structures.binary_tree.treap.insert
   data_structures.binary_tree.treap.interact_treap
   data_structures.binary_tree.treap.main
   data_structures.binary_tree.treap.merge
   data_structures.binary_tree.treap.split


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

.. py:class:: Node(value: int | None = None)

   Treap's node
   Treap is a binary tree by value and heap by priority


   .. py:method:: __repr__() -> str


   .. py:method:: __str__() -> str


   .. py:attribute:: left
      :type:  Node | None
      :value: None



   .. py:attribute:: prior


   .. py:attribute:: right
      :type:  Node | None
      :value: None



   .. py:attribute:: value
      :value: None



.. py:function:: erase(root: Node | None, value: int) -> Node | None

   Erase element

   Split all nodes with values less into left,
   Split all nodes with values greater into right.
   Merge left, right


.. py:function:: inorder(root: Node | None) -> None

   Just recursive print of a tree


.. py:function:: insert(root: Node | None, value: int) -> Node | None

   Insert element

   Split current tree with a value into left, right,
   Insert new node into the middle
   Merge left, node, right into root


.. py:function:: interact_treap(root: Node | None, args: str) -> Node | None

   Commands:
   + value to add value into treap
   - value to erase all nodes with value

       >>> root = interact_treap(None, "+1")
       >>> inorder(root)
       1,
       >>> root = interact_treap(root, "+3 +5 +17 +19 +2 +16 +4 +0")
       >>> inorder(root)
       0,1,2,3,4,5,16,17,19,
       >>> root = interact_treap(root, "+4 +4 +4")
       >>> inorder(root)
       0,1,2,3,4,4,4,4,5,16,17,19,
       >>> root = interact_treap(root, "-0")
       >>> inorder(root)
       1,2,3,4,4,4,4,5,16,17,19,
       >>> root = interact_treap(root, "-4")
       >>> inorder(root)
       1,2,3,5,16,17,19,
       >>> root = interact_treap(root, "=0")
       Unknown command


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

   After each command, program prints treap


.. py:function:: merge(left: Node | None, right: Node | None) -> Node | None

   We merge 2 trees into one.
   Note: all left tree's values must be less than all right tree's


.. py:function:: split(root: Node | None, value: int) -> tuple[Node | None, Node | None]

   We split current tree into 2 trees with value:

   Left tree contains all values less than split value.
   Right tree contains all values greater or equal, than split value