Data structures and algorithms with Python is a great course to learn the fundamentals of data structures and algorithms. One of the data structures covered in this course is the splay tree. A splay tree is a self-balancing data structure that is an extension of the binary search tree. Splay trees are useful because they provide efficient access to elements while also supporting insertions and deletions. In this article, we will discuss the time and space complexity of splay trees when performing access, search, insertion, and deletion operations. We will also provide Python code to illustrate the concepts we discuss.
What are Splay Trees?
A splay tree is a binary search tree with a special property. Whenever an element is accessed (whether for searching, insertion, or deletion), the element is moved to the root of the tree. This property, known as the splay operation, is what makes splay trees self-balancing. While a regular binary search tree can become unbalanced if its elements are accessed in a certain order, a splay tree will remain balanced no matter what order the elements are accessed in.
How does Splay Trees Work?
Splay Trees, also known as self-adjusting search trees, are a type of binary search tree that rearranges recently accessed nodes to the root of the tree. The idea behind Splay Trees is to make recently accessed elements easier to access in the future. This is done by restructuring the tree after each node access.
The restructuring of the tree is done through a series of rotations. The type of rotation used depends on the location of the accessed node. After each rotation, the tree is balanced so that the distance from the root to any of its leaves is approximately equal.
There is a variety of operations that can be performed on Splay Trees, including insert, delete, search, min, max, and predecessor/successor. When an element is inserted into the tree, the tree is restructured to make the newly inserted element the root of the tree. When an element is deleted, the tree is restructured so that the node’s parent is the new root.
The search operation finds the node with the requested value and makes it the root of the tree. The min, max, predecessor and successor operations also find the requested node and make it the root.
Splay Trees provide efficient access to recently accessed elements, making them an ideal choice for applications that require fast access to recently used elements.
Time Complexity
The time complexity of splay trees is best discussed in terms of the operations we can perform on them. We will cover the average and worst-case time complexity for access, search, insertion, and deletion.
Access Time Complexity
The average time complexity for accessing an element in a splay tree is O(log n). This is the same as the average time complexity of a regular binary search tree. The worst-case time complexity for accessing an element in a splay tree, however, is O(n). This is because the element must be moved to the root of the tree, which can take up to n steps if the element is at the bottom of the tree.
Search Time Complexity
The average time complexity for searching an element in a splay tree is also O(log n). This is because the splay operation will move the element to the root of the tree, making it much easier to find. The worst-case time complexity for searching an element in a splay tree is also O(n), as the element must be moved to the root of the tree before it can be found.
Insertion Time Complexity
The time complexity for inserting an element into a splay tree is O(log n). This is because the insertion process is similar to that of a regular binary search tree, and the splay operation does not add additional time complexity. The worst-case time complexity for insertion is also O(log n).
Deletion Time Complexity
The time complexity for deleting an element from a splay tree is also O(log n). This is because the splay operation does not add any additional time complexity, and the deletion process is similar to that of a regular binary search tree. The worst-case time complexity for deletion is also O(log n).
Space Complexity
The space complexity of splay trees is O(n). This is the same as the space complexity of a regular binary search tree.
Example in Python
Now that we have discussed the time and space complexity of splay trees, let’s look at an example in Python. We will use the following code to create a splay tree and insert, search, and delete elements from it.
# Create a class for the Node object
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Create a class for the Splay Tree object
class SplayTree:
def __init__(self):
self.root = None
# Function to insert a node into the splay tree
def insert(self, data):
if self.root is None:
self.root = Node(data)
else:
self._insert(data, self.root)
# Helper function for insert
def _insert(self, data, cur_node):
if data < cur_node.data:
if cur_node.left is None:
cur_node.left = Node(data)
else:
self._insert(data, cur_node.left)
elif data > cur_node.data:
if cur_node.right is None:
cur_node.right = Node(data)
else:
self._insert(data, cur_node.right)
else:
print("Value already in tree!")
# Function to search for a node in the splay tree
def search(self, data):
if self.root:
return self._search(data, self.root)
else:
return False
# Helper function for search
def _search(self, data, cur_node):
if data > cur_node.data and cur_node.right:
return self._search(data, cur_node.right)
elif data < cur_node.data and cur_node.left:
return self._search(data, cur_node.left)
if data == cur_node.data:
return True
# Function to delete a node from the splay tree
def delete(self, data):
if self.root is not None:
self.root = self._delete(data, self.root)
# Helper function for delete
def _delete(self, data, cur_node):
if data > cur_node.data and cur_node.right:
cur_node.right = self._delete(data, cur_node.right)
elif data < cur_node.data and cur_node.left:
cur_node.left = self._delete(data, cur_node.left)
elif data == cur_node.data:
if cur_node.right is None:
return cur_node.left
elif cur_node.left is None:
return cur_node.right
else:
temp_node = cur_node.right
while temp_node.left:
temp_node = temp_node.left
cur_node.data = temp_node.data
cur_node.right = self._delete(temp_node.data, cur_node.right)
return cur_node
Conclusion
Splay trees are an efficient and self-balancing data structure. They provide time complexity of O(log n) for access, search, insertion, and deletion operations, as well as space complexity of O(n). With the example Python code provided in this article, you should now be able to understand and implement splay trees in your own programs.
Exercises
Write a function to count the number of nodes in a splay tree.
def count_nodes(root):
if root is None:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
Write a function to find the maximum value in a splay tree.
def find_max(root):
if root is None:
return None
if root.right is None:
return root.data
return find_max(root.right)
Write a function to find the minimum value in a splay tree.
def find_min(root):
if root is None:
return None
if root.left is None:
return root.data
return find_min(root.left)
Write a function to calculate the height of a splay tree.
def height(root):
if root is None:
return -1
return 1 + max(height(root.left), height(root.right))
Write a function to traverse a splay tree in-order.
def in_order_traversal(root):
if root is None:
return
in_order_traversal(root.left)
print(root.data)
in_order_traversal(root.right)