Of course! Here is a comprehensive guide to implementing a Splay Tree in Java, including the theory, the code, and a detailed explanation.
（图片来源网络，侵删）
What is a Splay Tree?
A Splay Tree is a self-adjusting binary search tree. The key idea is that after every access (search, insert, or delete), the accessed node is "splayed" or moved to the root of the tree.
This splaying operation ensures that frequently accessed nodes are kept near the root, which leads to an amortized time complexity of O(log n) for these operations. "Amortized" means that while a single operation might be slow (O(n) in the worst case), the average performance over a sequence of operations is logarithmic.
The splaying is done using a series of tree rotations. The three fundamental rotations are:
- Zig (or Right Rotation): Used when the node is the left child of its parent and the parent is the root.
- Zag (or Left Rotation): Used when the node is the right child of its parent and the parent is the root.
- Zig-Zig: Used when the node and its parent are both left children (or both right children).
- Zig-Zag: Used when the node is a left child and its parent is a right child (or vice-versa).
These rotations are chosen based on the node's position relative to its parent and grandparent.
（图片来源网络，侵删）
Java Implementation
Here is a complete, well-commented Java implementation of a Splay Tree. It includes the Node class, the SplayTree class with core operations (insert, delete, search), and a main method for demonstration.
SplayTree.java
import java.util.LinkedList;
import java.util.Queue;
public class SplayTree<T extends Comparable<T>> {
private Node<T> root;
// Inner Node class
private static class Node<T> {
T data;
Node<T> left;
Node<T> right;
public Node(T data) {
this.data = data;
}
}
// Public method to insert a new element into the tree
public void insert(T data) {
if (root == null) {
root = new Node<>(data);
return;
}
// Splay the node to be inserted or its predecessor/successor to the root
splay(new Node<>(data));
int cmp = data.compareTo(root.data);
if (cmp < 0) {
// New data is smaller than the root's data
Node<T> newNode = new Node<>(data);
newNode.left = root.left;
newNode.right = root;
root.left = null;
root = newNode;
} else if (cmp > 0) {
// New data is larger than the root's data
Node<T> newNode = new Node<>(data);
newNode.right = root.right;
newNode.left = root;
root.right = null;
root = newNode;
}
// If cmp == 0, the data already exists. We still splay it to the root.
// The tree structure remains the same as we are just replacing the root's data
// (or not, depending on implementation choice). Here, we do nothing as the node is already at root.
}
// Public method to find an element in the tree
public Node<T> search(T data) {
if (root == null) return null;
splay(new Node<>(data)); // Splay the node with the given data to the root
if (root.data.compareTo(data) == 0) {
return root; // Found
}
return null; // Not found
}
// Public method to delete an element from the tree
public void delete(T data) {
if (root == null) return;
// Splay the node to be deleted to the root
splay(new Node<>(data));
// If the node to be deleted is not found, the splay operation
// will bring the closest node to the root. We should not delete it.
if (root.data.compareTo(data) != 0) {
return;
}
Node<T> leftSubtree = root.left;
Node<T> rightSubtree = root.right;
// If there is no right child, the left subtree becomes the new root
if (rightSubtree == null) {
root = leftSubtree;
} else {
// Otherwise, find the minimum node in the right subtree
// and splay it to the root of the right subtree
root = rightSubtree;
splay(new Node<>(leftSubtree != null ? leftSubtree.data : null)); // Splay the predecessor or null
// Attach the left subtree to the new root
root.left = leftSubtree;
}
}
/**
* The core splaying operation.
* This method brings the node with the given data to the root of the tree.
* If the node is not found, it brings the last accessed node (the closest one) to the root.
*/
private void splay(Node<T> node) {
Node<T> parent = null;
Node<T> grandParent = null;
Node<T> current = root;
// Standard BST search to find the node and its ancestors
while (current != null) {
int cmp = node.data.compareTo(current.data);
if (cmp == 0) {
break; // Node found, we will splay it
}
parent = current;
if (cmp < 0) {
current = current.left;
} else {
current = current.right;
}
}
// If the node wasn't found, current is the last node visited.
// We will splay this "closest" node to the root.
if (current == null) {
current = parent;
}
// Now, perform the splaying rotations from the bottom up
while (current != root) {
parent = findParent(current);
if (parent == null) continue; // Should not happen if current is not root
grandParent = findParent(parent);
if (grandParent == null) {
// Zig or Zag (Parent is root)
if (parent.left == current) {
rightRotate(parent); // Zig
} else {
leftRotate(parent); // Zag
}
} else {
// Determine the rotation pattern
boolean isZigZig = (grandParent.left == parent && parent.left == current) ||
(grandParent.right == parent && parent.right == current);
boolean isZigZag = (grandParent.left == parent && parent.right == current) ||
(grandParent.right == parent && parent.left == current);
if (isZigZig) {
if (grandParent.left == parent) {
// Zig-Zig on the left
rightRotate(grandParent);
rightRotate(parent);
} else {
// Zig-Zig on the right
leftRotate(grandParent);
leftRotate(parent);
}
} else if (isZigZag) {
if (grandParent.left == parent && parent.right == current) {
// Zig-Zag (Left-Right)
leftRotate(parent);
rightRotate(grandParent);
} else {
// Zag-Zig (Right-Left)
rightRotate(parent);
leftRotate(grandParent);
}
}
}
}
}
// Helper method to find the parent of a node
private Node<T> findParent(Node<T> child) {
if (child == root || child == null) {
return null;
}
Node<T> parent = root;
while (parent != null) {
if ((parent.left != null && parent.left == child) ||
(parent.right != null && parent.right == child)) {
return parent;
}
if (child.data.compareTo(parent.data) < 0) {
parent = parent.left;
} else {
parent = parent.right;
}
}
return null;
}
// Right rotation (Zig)
private void rightRotate(Node<T> x) {
Node<T> y = x.left;
x.left = y.right;
y.right = x;
// The root update is handled by the splay method's loop
if (x == root) {
root = y;
}
}
// Left rotation (Zag)
private void leftRotate(Node<T> x) {
Node<T> y = x.right;
x.right = y.left;
y.left = x;
// The root update is handled by the splay method's loop
if (x == root) {
root = y;
}
}
// --- Utility Methods for Testing ---
public void printTree() {
if (root == null) {
System.out.println("Tree is empty.");
return;
}
Queue<Node<T>> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
Node<T> current = queue.poll();
System.out.print(current.data + " ");
if (current.left != null) queue.add(current.left);
if (current.right != null) queue.add(current.right);
}
System.out.println(); // New line for next level
}
}
public boolean isEmpty() {
return root == null;
}
public static void main(String[] args) {
SplayTree<Integer> tree = new SplayTree<>();
System.out.println("--- Inserting 10, 5, 15, 3, 7, 12, 18 ---");
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);
tree.insert(12);
tree.insert(18);
System.out.println("Tree structure after inserts:");
tree.printTree();
System.out.println("Root is now: " + tree.root.data); // Should be 18
System.out.println("\n-------------------------------------------\n");
System.out.println("--- Searching for 7 ---");
tree.search(7);
System.out.println("Tree structure after searching for 7:");
tree.printTree();
System.out.println("Root is now: " + tree.root.data); // Should be 7
System.out.println("\n-------------------------------------------\n");
System.out.println("--- Deleting 15 ---");
tree.delete(15);
System.out.println("Tree structure after deleting 15:");
tree.printTree();
System.out.println("Root is now: " + tree.root.data); // Should be 12
System.out.println("\n-------------------------------------------\n");
System.out.println("--- Searching for a non-existent element 99 ---");
tree.search(99);
System.out.println("Tree structure after searching for 99:");
tree.printTree();
System.out.println("Root is now: " + tree.root.data); // Should be 18 (or 7, depending on implementation details of splay)
System.out.println("\n-------------------------------------------\n");
}
}
Explanation of the Code
Node Class
A simple private static inner class to represent a node in the tree. It holds the data and references to its left and right children.
SplayTree Class
insert(T data)
- If the tree is empty, it creates a new root node.
- It calls the
splay(new Node<>(data))method. This will either find the node with the given data or the node that would be its parent and move it to the root. - It then compares the new data with the root's data.
- If
data < root.data, the new node becomes the new root. The old root becomes its right child, and the old root's left subtree becomes the new node's left subtree. - If
data > root.data, the new node becomes the new root. The old root becomes its left child, and the old root's right subtree becomes the new node's right subtree. - If
data == root.data, the node is already at the root (due to splaying), so no structural change is needed.
- If
search(T data)
- It calls
splay(new Node<>(data))to bring the target node (or the closest one) to the root. - It checks if the root's data matches the search key.
- If it matches, the node is found and returned.
- If not, the node is not in the tree, and
nullis returned. The tree is still modified by the splay operation.
delete(T data)
- It calls
splay(new Node<>(data))to bring the target node to the root. This is crucial for the deletion logic. - It checks if the root is indeed the node to be deleted. If not, it does nothing.
- If the node is found, it handles two cases:
- No right child: The left subtree simply becomes the new root.
- Has a right child: This is the more complex case.
- The right subtree becomes the new root.
- The minimum node in this new right subtree (which is the root's right child) is then splayed. This ensures the tree remains balanced.
- The original left subtree is then attached as the left child of this new root.
splay(Node node) (The Core Logic)
This is the most complex part. It doesn't necessarily find the node first; it finds the node and its ancestors during a search-like traversal.
- Find Node: It traverses the tree to find the
nodeor the last node visited before reaching a null pointer. - Bottom-Up Rotations: It then enters a loop that continues until the
currentnode becomes the root. In each iteration:- It identifies the
parentandgrandParentof thecurrentnode. - If there's no
grandParent(i.e.,parentis the root), it performs a single Zig or Zag rotation. - If there is a
grandParent, it checks the configuration (Zig-Zig, Zig-Zag, etc.) and performs the corresponding double rotation. - The loop ensures that rotations are performed from the bottom of the path up, moving the target node closer to the root with each step.
- It identifies the
Rotation Helper Methods (leftRotate, rightRotate)
These methods perform the fundamental tree rotations. They carefully re-wire the pointers between nodes. The splay method is responsible for tracking the root, so these methods only need to handle the local rotation.
Analysis and Use Cases
Time Complexity
- Amortized Time Complexity: O(log n). This is the most important property of a splay tree. Any sequence of
moperations on a splay tree withnnodes takes O(m log n + n) time. This means the average time per operation is O(log n). - Worst-Case Time Complexity: O(n). A single operation can take linear time, for example, if you search for the deepest node in the tree. However, this "bad" operation improves the performance of subsequent operations by bringing frequently accessed nodes to the top.
Space Complexity
- O(n), as it's a standard binary tree.
Use Cases Splay trees are excellent in scenarios where:
- There is a temporal locality of reference: Some elements are accessed much more frequently than others. For example, in a compiler's symbol table, recently declared variables are accessed more often.
- You need a simple implementation. The splaying logic, while complex, is contained within one method, and the core BST logic is simpler than in an AVL or Red-Black tree.
- Memory is a concern, as they do not require storing extra balance information (like heights or colors) in each node.
They are generally not a good choice for real-time systems where a guaranteed O(log n) time per operation is critical.
