data_structures.binary_tree.splay_tree
======================================

.. py:module:: data_structures.binary_tree.splay_tree

.. autoapi-nested-parse::

   Splay Tree - a self-adjusting binary search tree.

   A splay tree is a binary search tree with the additional property that
   recently accessed elements are quick to access again.  Every access (search,
   insert or delete) moves the target node to the root through a sequence of
   rotations called "splaying".  This gives an amortized time complexity of
   O(log n) per operation and makes the tree very efficient when the access
   pattern has locality of reference (a small subset of keys is touched often).

   Reference: https://en.wikipedia.org/wiki/Splay_tree



Classes
-------

.. autoapisummary::

   data_structures.binary_tree.splay_tree.Node
   data_structures.binary_tree.splay_tree.SplayTree


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

.. py:class:: Node

   A single node of a splay tree.

   The ``left`` and ``right`` children are excluded from ``repr`` so that a
   node prints compactly instead of recursively dumping the whole subtree.

   >>> Node(10)
   Node(key=10)


   .. py:attribute:: key
      :type:  int


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



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



.. py:class:: SplayTree

   A self-adjusting binary search tree.

   >>> tree = SplayTree()
   >>> tree.insert(10)
   >>> tree.insert(20)
   >>> tree.insert(30)
   >>> tree.root.key  # last inserted key is splayed to the root
   30
   >>> tree.search(10)
   True
   >>> tree.root.key  # the searched key is now the root
   10
   >>> tree.search(99)
   False
   >>> list(tree)
   [10, 20, 30]


   .. py:method:: __iter__() -> collections.abc.Iterator[int]

      Yield the keys of the tree in ascending (in-order) order.

      >>> tree = SplayTree()
      >>> for key in (7, 2, 9, 4, 1):
      ...     tree.insert(key)
      >>> list(tree)
      [1, 2, 4, 7, 9]



   .. py:method:: _rotate_left(node: Node) -> Node

      Perform a left rotation around ``node`` and return the new subtree root.

         node                 right
        /    \               /     \
       a     right   -->    node     c
            /     \        /    \
           b       c       a      b



   .. py:method:: _rotate_right(node: Node) -> Node

       Perform a right rotation around ``node`` and return the new subtree root.

           node            left
          /    \          /    \
        left    c   -->   a     node
       /   \                   /    \
      a     b                 b      c
       



   .. py:method:: _splay(root: Node | None, key: int) -> Node | None

      Splay the node with ``key`` (or the last node on the search path if
      ``key`` is absent) to the root of the subtree and return the new root.
      This uses the classic bottom-up recursive formulation.



   .. py:method:: delete(key: int) -> None

      Remove ``key`` from the tree if it is present.

      >>> tree = SplayTree()
      >>> for key in (10, 20, 30, 40):
      ...     tree.insert(key)
      >>> tree.delete(20)
      >>> list(tree)
      [10, 30, 40]
      >>> tree.delete(99)  # deleting an absent key is a no-op
      >>> list(tree)
      [10, 30, 40]
      >>> for key in (10, 30, 40):
      ...     tree.delete(key)
      >>> list(tree)
      []



   .. py:method:: insert(key: int) -> None

      Insert ``key`` into the tree and splay it to the root.

      >>> tree = SplayTree()
      >>> for key in (5, 3, 8, 3):  # duplicate keys are ignored
      ...     tree.insert(key)
      >>> list(tree)
      [3, 5, 8]
      >>> tree.root.key  # the duplicate access splays 3 back to the root
      3



   .. py:method:: search(key: int) -> bool

      Return whether ``key`` is present and splay the last accessed node.

      >>> tree = SplayTree()
      >>> tree.search(1)
      False
      >>> for key in (40, 20, 60):
      ...     tree.insert(key)
      >>> tree.search(20)
      True
      >>> tree.root.key
      20



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