Splay Trees

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

def count_nodes(root): 
    if root is None: 
        return 0 
    return 1 + count_nodes(root.left) + count_nodes(root.right) 

def find_max(root): 
    if root is None: 
        return None 
    if root.right is None: 
        return root.data 
    return find_max(root.right) 

def find_min(root): 
    if root is None: 
        return None 
    if root.left is None: 
        return root.data 
    return find_min(root.left) 

def height(root): 
    if root is None: 
        return -1 
    return 1 + max(height(root.left), height(root.right)) 

def in_order_traversal(root): 
    if root is None: 
        return 
    in_order_traversal(root.left) 
    print(root.data) 
    in_order_traversal(root.right)