// SplayTree class // // CONSTRUCTION: with no initializer // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // Comparable find( x ) --> Return item that matches x // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // void printTree( ) --> Print tree in sorted order/** * Implements a top-down splay tree. Note that all "matching" is based on the * compareTo method. * * @author Mark Allen Weiss */ public class SplayTree {
// Test program; should print min and max and nothing else public static void main(String[] args) { SplayTree t = new SplayTree(); t.insert(new Integer(33)); t.insert(new Integer(55)); t.insert(new Integer(22)); t.insert(new Integer(44)); t.insert(new Integer(11)); t.insert(new Integer(99)); System.out.println("Insert complete"); t.printTree(); System.out.println("PrintTree complete"); if(t.find(new Integer(22)) != null) System.out.println("Find 22"); else System.out.println("Not find 22");
for (int i = 1; i <= 10; i ++) t.remove(new Integer(i)); System.out.println("Removes complete"); } /** * Construct the tree. */ public SplayTree() { root = nullNode; } /** * Insert into the tree. * * @param x * the item to insert. */ public void insert(Comparable x) { if (newNode == null) newNode = new BinaryNode(null); newNode.element = x; if (root == nullNode) { newNode.left = newNode.right = nullNode; root = newNode; } else { root = splay(x, root); if (x.compareTo(root.element) < 0) { newNode.left = root.left; newNode.right = root; root.left = nullNode; root = newNode; } else if (x.compareTo(root.element) > 0) { newNode.right = root.right; newNode.left = root; root.right = nullNode; root = newNode; } else return; } newNode = null; // So next insert will call new } /** * Remove from the tree. * * @param x * the item to remove. */ public void remove(Comparable x) { BinaryNode newTree; // If x is found, it will be at the root root = splay(x, root); if (root.element.compareTo(x) != 0) return; // Item not found; do nothing if (root.left == nullNode) newTree = root.right; else { // Find the maximum in the left subtree // Splay it to the root; and then attach right child newTree = root.left; newTree = splay(x, newTree); newTree.right = root.right; } root = newTree; } /** * Find the smallest item in the tree. Not the most efficient implementation * (uses two passes), but has correct amortized behavior. A good alternative * is to first call Find with parameter smaller than any item in the tree, * then call findMin. * * @return the smallest item or null if empty. */ public Comparable findMin() { if (isEmpty()) return null; BinaryNode ptr = root; while (ptr.left != nullNode) ptr = ptr.left; root = splay(ptr.element, root); return ptr.element; } /** * Find the largest item in the tree. Not the most efficient implementation * (uses two passes), but has correct amortized behavior. A good alternative * is to first call Find with parameter larger than any item in the tree, * then call findMax. * * @return the largest item or null if empty. */ public Comparable findMax() { if (isEmpty()) return null; BinaryNode ptr = root; while (ptr.right != nullNode) ptr = ptr.right; root = splay(ptr.element, root); return ptr.element; } /** * Find an item in the tree. * * @param x * the item to search for. * @return the matching item or null if not found. */ public Comparable find(Comparable x) { root = splay(x, root); if (isEmpty() || root.element.compareTo(x) != 0) return null; return root.element; } /** * Make the tree logically empty. */ public void makeEmpty() { root = nullNode; } /** * Test if the tree is logically empty. * * @return true if empty, false otherwise. */ public boolean isEmpty() { return root == nullNode; } /** * Print the tree contents in sorted order. */ public void printTree() { if (isEmpty()) System.out.println("Empty tree"); else printTree(root); } /** * Internal method to perform a top-down splay. The last accessed node * becomes the new root. * * @param x * the target item to splay around. * @param t * the root of the subtree to splay. * @return the subtree after the splay. */ private BinaryNode splay(Comparable x, BinaryNode t) { BinaryNode leftTreeMax, rightTreeMin; header.left = header.right = nullNode; leftTreeMax = rightTreeMin = header; nullNode.element = x; // Guarantee a match for (;;) if (x.compareTo(t.element) < 0) { if (x.compareTo(t.left.element) < 0) t = rotateWithLeftChild(t); if (t.left == nullNode) break; // Link Right rightTreeMin.left = t; rightTreeMin = t; t = t.left; } else if (x.compareTo(t.element) > 0) { if (x.compareTo(t.right.element) > 0) t = rotateWithRightChild(t); if (t.right == nullNode) break; // Link Left leftTreeMax.right = t; leftTreeMax = t; t = t.right; } else break; leftTreeMax.right = t.left; rightTreeMin.left = t.right; t.left = header.right; t.right = header.left; return t; } /** * Rotate binary tree node with left child. */ static BinaryNode rotateWithLeftChild(BinaryNode k2) { BinaryNode k1 = k2.left; k2.left = k1.right; k1.right = k2; return k1; } /** * Rotate binary tree node with right child. */ static BinaryNode rotateWithRightChild(BinaryNode k1) { BinaryNode k2 = k1.right; k1.right = k2.left; k2.left = k1; return k2; } /** * Internal method to print a subtree in sorted order. WARNING: This is * prone to running out of stack space. * * @param t * the node that roots the tree. */ private void printTree(BinaryNode t) { if (t != t.left) { printTree(t.left); System.out.println(t.element.toString()); printTree(t.right); } } private BinaryNode root; private static BinaryNode nullNode; static // Static initializer for nullNode { nullNode = new BinaryNode(null); nullNode.left = nullNode.right = nullNode; } private static BinaryNode newNode = null; // Used between different inserts private static BinaryNode header = new BinaryNode(null); // For splay}class BinaryNode { Comparable element; BinaryNode left; BinaryNode right; public BinaryNode(Comparable x) { this(x, null, null); } public BinaryNode(Comparable x, BinaryNode l, BinaryNode r) { element = x; left = l; right = r; } }
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order/**
* Implements a top-down splay tree. Note that all "matching" is based on the
* compareTo method.
*
* @author Mark Allen Weiss
*/
public class SplayTree {
// Test program; should print min and max and nothing else
public static void main(String[] args) {
SplayTree t = new SplayTree();
t.insert(new Integer(33));
t.insert(new Integer(55));
t.insert(new Integer(22));
t.insert(new Integer(44));
t.insert(new Integer(11));
t.insert(new Integer(99));
System.out.println("Insert complete"); t.printTree();
System.out.println("PrintTree complete"); if(t.find(new Integer(22)) != null)
System.out.println("Find 22");
else
System.out.println("Not find 22");
if(t.find(new Integer(77)) != null)
System.out.println("Find 77");
else
System.out.println("Not find 77");
System.out.println("Find complete");
for (int i = 1; i <= 10; i ++)
t.remove(new Integer(i));
System.out.println("Removes complete"); } /**
* Construct the tree.
*/
public SplayTree() {
root = nullNode;
} /**
* Insert into the tree.
*
* @param x
* the item to insert.
*/
public void insert(Comparable x) {
if (newNode == null)
newNode = new BinaryNode(null);
newNode.element = x; if (root == nullNode) {
newNode.left = newNode.right = nullNode;
root = newNode;
} else {
root = splay(x, root);
if (x.compareTo(root.element) < 0) {
newNode.left = root.left;
newNode.right = root;
root.left = nullNode;
root = newNode;
} else if (x.compareTo(root.element) > 0) {
newNode.right = root.right;
newNode.left = root;
root.right = nullNode;
root = newNode;
} else
return;
}
newNode = null; // So next insert will call new
} /**
* Remove from the tree.
*
* @param x
* the item to remove.
*/
public void remove(Comparable x) {
BinaryNode newTree; // If x is found, it will be at the root
root = splay(x, root);
if (root.element.compareTo(x) != 0)
return; // Item not found; do nothing if (root.left == nullNode)
newTree = root.right;
else {
// Find the maximum in the left subtree
// Splay it to the root; and then attach right child
newTree = root.left;
newTree = splay(x, newTree);
newTree.right = root.right;
}
root = newTree;
} /**
* Find the smallest item in the tree. Not the most efficient implementation
* (uses two passes), but has correct amortized behavior. A good alternative
* is to first call Find with parameter smaller than any item in the tree,
* then call findMin.
*
* @return the smallest item or null if empty.
*/
public Comparable findMin() {
if (isEmpty())
return null; BinaryNode ptr = root; while (ptr.left != nullNode)
ptr = ptr.left; root = splay(ptr.element, root);
return ptr.element;
} /**
* Find the largest item in the tree. Not the most efficient implementation
* (uses two passes), but has correct amortized behavior. A good alternative
* is to first call Find with parameter larger than any item in the tree,
* then call findMax.
*
* @return the largest item or null if empty.
*/
public Comparable findMax() {
if (isEmpty())
return null; BinaryNode ptr = root; while (ptr.right != nullNode)
ptr = ptr.right; root = splay(ptr.element, root);
return ptr.element;
} /**
* Find an item in the tree.
*
* @param x
* the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find(Comparable x) {
root = splay(x, root); if (isEmpty() || root.element.compareTo(x) != 0)
return null; return root.element;
} /**
* Make the tree logically empty.
*/
public void makeEmpty() {
root = nullNode;
} /**
* Test if the tree is logically empty.
*
* @return true if empty, false otherwise.
*/
public boolean isEmpty() {
return root == nullNode;
} /**
* Print the tree contents in sorted order.
*/
public void printTree() {
if (isEmpty())
System.out.println("Empty tree");
else
printTree(root);
} /**
* Internal method to perform a top-down splay. The last accessed node
* becomes the new root.
*
* @param x
* the target item to splay around.
* @param t
* the root of the subtree to splay.
* @return the subtree after the splay.
*/
private BinaryNode splay(Comparable x, BinaryNode t) {
BinaryNode leftTreeMax, rightTreeMin; header.left = header.right = nullNode;
leftTreeMax = rightTreeMin = header; nullNode.element = x; // Guarantee a match for (;;)
if (x.compareTo(t.element) < 0) {
if (x.compareTo(t.left.element) < 0)
t = rotateWithLeftChild(t);
if (t.left == nullNode)
break;
// Link Right
rightTreeMin.left = t;
rightTreeMin = t;
t = t.left;
} else if (x.compareTo(t.element) > 0) {
if (x.compareTo(t.right.element) > 0)
t = rotateWithRightChild(t);
if (t.right == nullNode)
break;
// Link Left
leftTreeMax.right = t;
leftTreeMax = t;
t = t.right;
} else
break; leftTreeMax.right = t.left;
rightTreeMin.left = t.right;
t.left = header.right;
t.right = header.left;
return t;
} /**
* Rotate binary tree node with left child.
*/
static BinaryNode rotateWithLeftChild(BinaryNode k2) {
BinaryNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
} /**
* Rotate binary tree node with right child.
*/
static BinaryNode rotateWithRightChild(BinaryNode k1) {
BinaryNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
} /**
* Internal method to print a subtree in sorted order. WARNING: This is
* prone to running out of stack space.
*
* @param t
* the node that roots the tree.
*/
private void printTree(BinaryNode t) {
if (t != t.left) {
printTree(t.left);
System.out.println(t.element.toString());
printTree(t.right);
}
} private BinaryNode root; private static BinaryNode nullNode;
static // Static initializer for nullNode
{
nullNode = new BinaryNode(null);
nullNode.left = nullNode.right = nullNode;
} private static BinaryNode newNode = null; // Used between different inserts private static BinaryNode header = new BinaryNode(null); // For splay}class BinaryNode {
Comparable element; BinaryNode left; BinaryNode right; public BinaryNode(Comparable x) {
this(x, null, null);
} public BinaryNode(Comparable x, BinaryNode l, BinaryNode r) {
element = x;
left = l;
right = r;
}
}