Back to Course

0% Complete
0/0 Steps

Lesson 18 of 48
In Progress

# Splay Trees in Java

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 (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);
}
}