<![CDATA[public class SplayTree {
private SplayingNode root = null;
public SplayTree() {
super();
}
private void continueRotation(SplayingNode gr, SplayingNode par,
SplayingNode ch, SplayingNode desc) {
if (gr != null) { // if p has a grandparent;
if (gr.right == ch.parent)
gr.right = ch;
else gr.left = ch;
}
else root = ch;
if (desc != null)
desc.parent = par;
par.parent = ch;
ch.parent = gr;
}
private void rotateR(SplayingNode p) {
p.parent.left = p.right;
p.right = p.parent;
continueRotation(p.parent.parent,p.right,p,p.right.left);
}
private void rotateL(SplayingNode p) {
p.parent.right = p.left;
p.left = p.parent;
continueRotation(p.parent.parent,p.left,p,p.left.right);
}
private void semisplay(SplayingNode p) {
while (p != root) {
if (p.parent.parent == null) // if p's parent is the root;
if (p.parent.left == p)
rotateR(p);
else rotateL(p);
else if (p.parent.left == p) // if p is a left child;
if (p.parent.parent.left == p.parent) {
rotateR(p.parent);
p = p.parent;
}
else {
rotateR(p); // rotate p and its parent;
rotateL(p); // rotate p and its new parent;
}
else // if p is a rigth child;
if (p.parent.parent.right == p.parent) {
rotateL(p.parent);
p = p.parent;
}
else {
rotateL(p); // rotate p and its parent;
rotateR(p); // rotate p and its new parent;
}
if (root == null) // update the root;
root = p;
}
}
public Object search(BaseObject el) {
SplayingNode p = root;
while (p != null) {
if (p.el.equals(el)) { // if el is in the tree,
semisplay(p); // move it upward;
return p.el;
}
else if (el.isLessThan(p.el))
p = p.left;
else p = p.right;
}
return null;
}
public void insert(BaseObject el) {
SplayingNode p = root, prev = null, newNode;
while (p != null) { // find a place for inserting a new node;
prev = p;
if (el.isLessThan(p.el))
p = p.left;
else p = p.right;
}
if ((newNode = new SplayingNode(el,null,null,prev)) == null) {
System.err.println("No room for new nodes");
Runtime.getRuntime().exit(0);
}
if (root == null) // if tree is empty
root = newNode;
else if (el.isLessThan(prev.el))
prev.left = newNode;
else prev.right = newNode;
}
protected void inorder() {
inorder(root);
}
protected void inorder(SplayingNode p) {
if (p != null) {
inorder(p.left);
visit(p);
inorder(p.right);
}
}
protected void visit(SplayingNode p) {
}
}
]]>