data_structures.binary_tree.splay_tree

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

Node	A single node of a splay tree.
SplayTree	A self-adjusting binary search tree.

Module Contents

class data_structures.binary_tree.splay_tree.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)

key: int

left: Node | None = None

right: Node | None = None

class data_structures.binary_tree.splay_tree.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]

__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]

_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

_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

_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.

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)
[]

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

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

root: Node | None = None