Home Data Structures and Algorithms with Java Splay Trees in Java

Lesson 18 of 48

In Progress

← Previous Next→

Splay Trees in Java

Yasin Cakal

Data Structures and Algorithms with Java can be a challenging topic to learn, but splay trees are a powerful tool to have in your programming arsenal. In this article, we’ll explore what splay trees are, how they work, their time and space complexity, and how to use them in Java. By the end of this article, you’ll be able to confidently implement and use splay trees in your own programs.

What is a Splay Tree?

A splay tree is a self-balancing binary search tree. It is similar to other self-balancing binary search trees such as AVL trees and red-black trees, but it has some key differences. In a splay tree, nodes are moved around the tree to improve performance. This is done by splaying the tree, which is the process of rearranging the tree to make a certain node the root.

A splay tree is useful in applications where the tree needs to be frequently accessed and updated. This is because the splay tree is optimized for quick access. The splay tree can rearrange itself to make the most frequently used nodes the root, so it can be quickly accessed.

How Does a Splay Tree Work?

A splay tree works by rearranging nodes within the tree to improve performance. This is done by splaying the tree, which is the process of making a certain node the root of the tree. When a node is accessed, it is splayed so that it becomes the root of the tree.

When a node is inserted into the tree, it is first inserted as a leaf node. Then, the tree is splayed so that the inserted node is the root of the tree. Similarly, when a node is deleted from the tree, it is first deleted as a leaf node. Then, the tree is splayed so that the parent of the deleted node is the root of the tree.

Time Complexity

The time complexity of a splay tree is O(log n) for access, search, insertion and deletion. This is because the tree is self-balancing and is optimized for quick access.

Space Complexity

The space complexity of a splay tree is O(n) in the worst case. This is because a splay tree stores all of its nodes in memory.

Using Splay Trees in Java

Now that we’ve explored what a splay tree is and how it works, let’s look at how to use it in Java.

To implement a splay tree in Java, we must first create a Node class that represents the nodes in the tree. This class should have attributes for the data stored in the node, the left and right children, and the parent of the node.

public class Node { 
	int data; 
	Node left, right, parent; 
 
	public Node(int data) { 
		this.data = data; 
		left = right = parent = null; 
	} 
}

We must also create a SplayTree class that represents the tree. This class should have a root node and methods for insert, search, and delete.

public class SplayTree { 
	Node root; 
 
	public SplayTree() { 
		root = null; 
	} 
 
	public void insert(int data) { 
		// Code for insert 
	} 
 
	public Node search(int data) { 
		// Code for search 
	} 
 
	public void delete(int data) { 
		// Code for delete 
	} 
}

Conclusion

In this article, we explored what splay trees are and how they work. We also looked at their time and space complexity, and how to use them in Java. Splay trees are a powerful tool that can be used to improve performance in applications where the tree needs to be frequently accessed and updated.

Exercises

Write a Java program to insert an element into a splay tree.

public class SplayTree { 
	Node root; 
 
	public SplayTree() { 
		root = null; 
	} 
 
	public void insert(int data) { 
		// Create a new node 
		Node node = new Node(data); 
 
		// If the tree is empty, set the root to the node 
		if (root == null) { 
			root = node; 
			return; 
		} 
 
		// Find the parent of the new node 
		Node parent = findParent(data); 
 
		// Set the parent of the new node 
		node.parent = parent; 
 
		// Set the left or right child of the parent 
		if (data < parent.data) { 
			parent.left = node; 
		} else { 
			parent.right = node; 
		} 
 
		// Splay the tree 
		splay(node); 
	} 
 
	private Node findParent(int data) { 
		// Code to find the parent 
	} 
 
	private void splay(Node node) { 
		// Code to splay the tree 
	} 
}

Write a Java program to search for an element in a splay tree.

public class SplayTree { 
	Node root; 
 
	public SplayTree() { 
		root = null; 
	} 
 
	public Node search(int data) { 
		// If the tree is empty, return null 
		if (root == null) { 
			return null; 
		} 
 
		// Start at the root 
		Node node = root; 
 
		// Iterate until the node is found 
		while (node != null && node.data != data) { 
			if (data < node.data) { 
				node = node.left; 
			} else { 
				node = node.right; 
			} 
		} 
 
		// Splay the tree 
		splay(node); 
 
		// Return the node 
		return node; 
	} 
 
	private void splay(Node node) { 
		// Code to splay the tree 
	} 
}

Write a Java program to delete an element from a splay tree.

public class SplayTree { 
	Node root; 
 
	public SplayTree() { 
		root = null; 
	} 
 
	public void delete(int data) { 
		// Find the node to be deleted 
		Node node = search(data); 
 
		// If the node is not found, return 
		if (node == null) { 
			return; 
		} 
 
		// Delete the node 
		if (node.left == null && node.right == null) { 
			if (node.parent == null) { 
				root = null; 
			} else { 
				if (node == node.parent.left) { 
					node.parent.left = null; 
				} else { 
					node.parent.right = null; 
				} 
			} 
		} else if (node.left != null && node.right == null) { 
			node.left.parent = node.parent; 
			if (node.parent == null) { 
				root = node.left; 
			} else { 
				if (node == node.parent.left) { 
					node.parent.left = node.left; 
				} else { 
					node.parent.right = node.left; 
				} 
			} 
		} else if (node.left == null && node.right != null) { 
			node.right.parent = node.parent; 
			if (node.parent == null) { 
				root = node.right; 
			} else { 
				if (node == node.parent.left) { 
					node.parent.left = node.right; 
				} else { 
					node.parent.right = node.right; 
				} 
			} 
		} else { 
			Node successor = findSuccessor(node); 
			successor.left = node.left; 
			node.left.parent = successor; 
			if (node.parent == null) { 
				root = successor; 
			} else { 
				if (node == node.parent.left) { 
					node.parent.left = successor; 
				} else { 
					node.parent.right = successor; 
				} 
			} 
			successor.parent = node.parent; 
		} 
 
		// Splay the tree 
		splay(node.parent); 
	} 
 
	private Node findSuccessor(Node node) { 
		// Code to find the successor 
	} 
 
	private void splay(Node node) { 
		// Code to splay the tree 
	} 
}

Write a Java program to traverse a splay tree in in-order.

public class SplayTree { 
	Node root; 
 
	public SplayTree() { 
		root = null; 
	} 
 
	public void inOrder() { 
		if (root == null) { 
			return; 
		} 
 
		inOrder(root); 
	} 
 
	private void inOrder(Node node) { 
		if (node == null) { 
			return; 
		} 
 
		inOrder(node.left); 
		System.out.print(node.data + " "); 
		inOrder(node.right); 
	} 
}

Write a Java program to perform a pre-order traversal of a splay tree.

public class SplayTree { 
	Node root; 
 
	public SplayTree() { 
		root = null; 
	} 
 
	public void preOrder() { 
		if (root == null) { 
			return; 
		} 
 
		preOrder(root); 
	} 
 
	private void preOrder(Node node) { 
		if (node == null) { 
			return; 
		} 
 
		System.out.print(node.data + " "); 
		preOrder(node.left); 
		preOrder(node.right); 
	} 
}

Data Structures and Algorithms with Java

Participants 676