package edu.princeton.cs.algs4.growingtree.demos; /** * All of the Splay Tree Operators. * @author Josh Israel */ import edu.princeton.cs.algs4.growingtree.framework.NodeProperties; import edu.princeton.cs.algs4.growingtree.interfaces.IAlgorithmNode; import edu.princeton.cs.algs4.growingtree.interfaces.IDeleteOperator; import edu.princeton.cs.algs4.growingtree.interfaces.IDeletingNode; import edu.princeton.cs.algs4.growingtree.interfaces.IInsertingNode; import edu.princeton.cs.algs4.growingtree.interfaces.INode; import edu.princeton.cs.algs4.growingtree.interfaces.ISearchingNode; public class SplayOperators { public
void splay(IAlgorithmNode
x, IAlgorithmNode
root) { IAlgorithmNode
p, g; /*check if node x is the root node*/ if(x.getParent() == null) return; /*Performs Zig step*/ else if(x.getParent()==root) { if(x==x.getParent().getLeft()) { root.rotateRight(); root = root.getParent(); } else root.rotateLeft(); root = root.getParent(); } else { p = x.getParent(); /*now points to parent of x*/ g = p.getParent(); /*now points to parent of x's parent*/ /*Performs the Zig-zig step when x is left and x's parent is left*/ if(x==p.getLeft() && p==g.getLeft()) { g.rotateRight(); p.rotateRight(); } /*Performs the Zig-zig step when x is right and x's parent is right*/ else if(x==p.getRight() && p==g.getRight()) { g.rotateLeft(); p.rotateLeft(); } /*Performs the Zig-zag step when x's is right and x's parent is left*/ else if(x==p.getRight() && p==g.getLeft()) { p.rotateLeft(); g.rotateRight(); } /*Performs the Zig-zag step when x's is left and x's parent is right*/ else if(x==p.getLeft() && p==g.getRight()) { p.rotateRight(); g.rotateLeft(); } splay(x, x.getRoot()); } } public class SplayInsertion
extends BSTInsertion
{ public void doInsert(IInsertingNode
root, INode
newNode) { if (newNode == null) return; IAlgorithmNode
inserted = insert(root, newNode); if (inserted != null) splay(inserted, root); } } public class SplaySearch
extends BSTSearch
{ public INode
doSearch(ISearchingNode
root, Comparable found = search(root, keyCompare);
if (found == null) {
return null;
}
splay(found, root);
return found;
}
}
public class SplayDeletion implements IDeleteOperator {
public void doDelete(IAlgorithmNode root, IDeletingNode node) {
IAlgorithmNode parent = node.getParent();
node.successorHibbardDelete();
if (parent != null) {
splay(parent, root);
}
}
}
}