Splay Tree¶

⏱ Time-Complexity¶

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

• n is the number of nodes currently in the splay tree.
• h is the splay tree’s height which approximatley equals to log(n).

☕️ API¶

Here are all of the public methods that can be used with SplayTree() objects:

class extra.trees.splay_tree.SplayTree(iterable=None)¶

A Splay Tree is a non-linear data structure that can be defined recursively using a collection of binary tree nodes, where each node contains a numeric value and it has either zero, one or two references to the children binary tree nodes. Any node that has been accessed is moved to the root directly to make it faster to be accessed again. This operation is called “splaying”. Hence the name of this data structure… Splay Tree.

__contains__(find_val)¶

Searches the SplayTree() for the given value and returns True if the value exists and False if not.

Parameters:	find_val (int or float) – The value to be searched for in the SplayTree() instance.
Returns:	Returns True if the value exists in the SplayTree() instance and False if not.
Return type:	bool

Example

>>> stree = SplayTree([[2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> 5 in stree
True
>>> stree
    __5
   /   \
  3     6
 / \
2   4
>> 50 in stree
False
>>> stree
        6
       /
    __5
   /
  3
 / \
2   4

Note

As you can see from the previous example, the SplayTree() instance changes its structure each time we search for a certain value. If the value if found, the found node will be moved to the root. If the value isn’t found, the last accessed node will be moved to the root. And that’s what happended when searching for 50, the last accessed value which is the greatest value (6) in the splay tree is moved to the root.

__init__(iterable=None)¶

Initializes a SplayTree() instance using an optional iterable object in time-complexity of O(n) where n is the number of elements inside the given iterable.

Parameters:	iterable (iterable, optional) – An iterable python object that implements the __iter__ method. For example, list and tuple are both iterables.
Raises:	TypeError: – It can be raised in two cases In case the given object isn’t iterable. If one of the elements in the iterable is an Extra object. If one of the elements in the iterable is NOT a number. ValueError: – If one of the iterable elements is None.

Examples

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6

Using an iterable object with None as one of its elements will raise ValueError

>>> SplayTree([2, None])
ValueError: Can't use `None` as an element within `extra.SplayTree()`!!

Using a non-iterable object will raise TypeError

>>> SplayTree(2)
TypeError: The given object isn't iterable!!

Using nested SplayTree() objects will raise TypeError as well

>>> stree_1 = SplayTree([1])
>>> stree_2 = SplayTree([1, stree_1])
TypeError: Can't create `extra.SplayTree()` using `extra.SplayTree()`!!

__iter__()¶

Iterates over the SplayTree() instance and returns a generator of the SplayTreeNode() values in breadth-first manner.

Yields:	int or float – The number stored at each node in the instance.

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> for value in stree:
...     print(value, end=',')
3,2,5,4,6,

__len__()¶

Gets the length of the SplayTree() instance in constant time.

Returns:	The length of the SplayTree() instance. Length is the number of tree nodes in the instance.
Return type:	int

Example

>>> stree = SplayTree([[2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> len(stree)
5

breadth_first_traverse()¶

Traverses the SplayTree() instance in breadth-first manner. Which means that the tree nodes will be visited level by level.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.breadth_first_traverse()
[3, 2, 5, 4, 6]

clear()¶

Removes all nodes within the SplayTree() instance in constant time.

Example

>>> stree = SplayTree([[2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.clear()
>>> stree
/ \
>>> stree.is_empty()
True

count_leaf_nodes()¶

Counts the number of leaf nodes in the SplayTree() instance. Leaf nodes are the tree nodes that have no children.

Returns:	A positive integer representing the number of leaf nodes in the SplayTree().
Return type:	int

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.count_leaf_nodes()
3
>>> 4 in stree
True
>>> stree.count_leaf_nodes()
2

Note

The number of leaf nodes inside the SplayTree() instance is changed after any operation such as insertion, removal or even searching as we saw in the previous example.

depth_first_traverse()¶

Traverses the SplayTree() instance in depth-first manner. Which means that the parent is visited first. Then, the left subtree (if found), then the right subtree (if found).

Note

It’s the same as preorder_traverse() method.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.depth_first_traverse()
[3, 2, 5, 4, 6]

get_depth()¶

Gets the depth of the SplayTree() instance.

Returns:	A positive integer representing the depth of the instance.
Return type:	int

Example

>>> stree = SplayTree([[2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.get_depth()
0

get_height()¶

Gets the height of the SplayTree() instance. The SplayTree’s height is the number of edges between the root and the furthest leaf node.

Returns:	A positive integer representing the height of the instance.
Return type:	int

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.get_height()
2
>>> 6 in stree
True
>>> stree.get_height()
3

Note

The height of the SplayTree() instance is changed after any operation such as insertion, removal or even searching as we saw in the previous example.

get_max()¶

Gets the maximum value in the SplayTree() isntance. The maximum value can be found at the right-most tree node in the SplayTree() instance.

Returns:	The maximum numeric value in the SplayTree() instance.
Return type:	int or float
Raises:	IndexError: – In case the SplayTree() instance is empty.

Example

>>> stree = SplayTree([[2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.get_max()
6

get_min()¶

Gets the minimum value in the SplayTree() isntance. The minimum value can be found at the left-most tree node in the SplayTree() instance.

Returns:	The maximum numeric value in the SplayTree() instance.
Return type:	int or float
Raises:	IndexError: – In case the SplayTree() instance is empty.

Example

>>> stree = SplayTree([[2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.get_min()
2

get_nodes_per_level()¶

Retrieves all tree nodes within the SplayTree() instance so that all tree nodes in a certain level will be concatenated into a separate list.

Returns:	A nested list where the first inner-list has all the tree nodes in the first level, the second inner-list has all the tree nodes in the second level, … so on.
Return type:	list

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.get_nodes_per_level()
[[3], [2, 5], [4, 6]]

inorder_traverse()¶

Traverses the SplayTree() instance in in-order manner. Which means that the left subtree (if found) is visited first. Then, the parent then the right subtree (if found).

Returns:	A list of all values of the in-order visited nodes.
Return type:	list

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.inorder_traverse()
[2, 3, 4, 5, 6]

insert(value)¶

Inserts a numeric value in the SplayTree()` instance according to the rules of binary search trees.

Parameters:	value (int or float) – The new numeric value that will be inserted.
Raises:	ValueError: – If the given value is None. TypeError: – If the given value is not a numeric value.

Example

>>> stree = SplayTree()
>>> stree.insert(10)
>>> stree
10
>>> stree.insert(5)
>>> stree
5
 \
  10
>>> stree.insert(15)
>>> stree
    _15
   /
  10
 /
5
>>> stree.insert(8)
>>> stree
  8___
 /    \
5     _15
     /
    10
>>> stree.insert("2")
TypeError: `extra.SplayTree()` accepts only numbers!!

is_balanced()¶

Checks if the SplayTree() instance is balanced. A SplayTree() instance is balanced if the difference between the depth of any two leaf nodes is less than or equal to one.

Returns:	True if the SplayTree() instance is balanced and False if it is not balanced.
Return type:	bool
Raises:	UserWarning: – If the SplayTree() is empty.

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.is_balanced()
True
>>> 2 in stree
True
>>> stree.is_balanced()
False

Note

The balance of the SplayTree() instance is changed after any operation such as insertion, removal or even searching as we saw in the previous example.

is_empty()¶

Checks if the SplayTree() instance is empty or not in constant time.

Returns:	A boolean flag showing if the SplayTree() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:	bool

Example

>>> stree = SplayTree()
>>> stree.is_empty()
True
>>> stree.insert(10)
>>> stree.is_empty()
False

is_perfect()¶

Checks if the SplayTree() instance is perfect. A SplayTree() instance is perfect if all its levels are completely filled.

Returns:	True if the SplayTree() instance is perfect and False if it is not perfect.
Return type:	bool
Raises:	UserWarning: – If the SplayTree() is empty.

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.is_perfect()
False

Note

The perfectness of the SplayTree() instance is changed after any operation such as insertion, removal or even searching.

is_strict()¶

Checks if the SplayTree() instance is strict. A SplayTree() instance is strict if all its non-leaf nodes have two children (left and right).

Returns:	True if the SplayTree() instance is strict and False if it is not strict.
Return type:	bool
Raises:	UserWarning: – If the SplayTree() is empty.

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.is_strict()
True
>>> 2 in stree
True
>>> stree.is_strict()
False

Note

The strictness of the SplayTree() instance is changed after any operation such as insertion, removal or even searching as we saw in the previous example

postorder_traverse()¶

Traverses the SplayTree() instance in post-order manner. Which means that the left subtree (if found) is visited first. Then, the right subtree (if found) then the parent.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.postorder_traverse()
[2, 4, 6, 5, 3]

preorder_traverse()¶

Traverses the SplayTree() instance in pre-order manner. Which means that the parent is visited first. Then, the left subtree (if found), then the right subtree (if found).

Note

It’s the same as depth_first_traverse() method.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.preorder_traverse()
[3, 2, 5, 4, 6]

remove(del_value)¶

Removes the del_value from the SplayTree() instance.

Parameters:	del_value (int or float) – The value to be deleted from the subtree.
Raises:	UserWarning: – If the SplayTree() instance is empty of if the value wasn’t found in the instance.

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.remove(5)
>>> stree
    __6
   /
  3
 / \
2   4
>>> stree.remove(50)
UserWarning: Couldn't find `50` in `extra.SplayTree()`!!

to_list()¶

Converts the SplayTree() instance to a list where values will be inserted in breadth-first manner.

Returns:	A list object containing the same elements as the SplayTree() instance.
Return type:	list

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.to_list()
[3, 2, 5, 4, 6]

traverse(method='inorder')¶

Traversal is the process to visit all nodes of a SplayTree starting from the root as we cannot randomly access any node in a binary tree. There are four ways which we use to traverse a SplayTree():

1. preorder - depth-first
2. inorder
3. posteorder
4. breadth-first

Parameters:	method (str (default="inorder")) – A lower-cased string describing the type of traversal that will be used. It could be one of these values: [“inorder”, “postorder”, “preorder”, “depth-first”, “breadth-first”]
Returns:	A list of all values of the visited nodes according to the specified traversal method.
Return type:	list
Raises:	ValueError: – If the given method isn’t known. TypeError: – If the given method isn’t a string.

Example

>>> stree = SplayTree([2, 5, 4, 6, 3])
>>> stree
  3__
 /   \
2     5
     / \
    4   6
>>> stree.traverse("preorder")
[3, 2, 5, 4, 6]
>>> stree.traverse("inorder")
[2, 3, 4, 5, 6]
>>> stree.traverse("postorder")
[2, 4, 6, 5, 3]
>>> stree.traverse("breadth-first")
[3, 2, 5, 4, 6]
>>> stree.traverse("extra")
ValueError: Given traverse method has to be one of these:
{'breadth-first', 'postorder', 'inorder', 'depth-first', 'preorder'}