Data Structure - Treap (Java)
分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击人工智能教程
package chimomo.learning.java.datastructure;
import java.util.Random;
/**
* Implements a treap.
* Note that all "matching" is based on the compareTo method.
*
* @author Created by Chimomo
*/
public class Treap<T extends Comparable<? super T>> {
private TreapNode<T> root;
private TreapNode<T> nullNode;
/**
* Construct the treap.
*/
public Treap() {
nullNode = new TreapNode<>(null);
nullNode.left = nullNode.right = nullNode;
nullNode.priority = Integer.MAX_VALUE;
root = nullNode;
}
// Test program.
public static void main(String[] args) throws Exception {
// Construct treap.
Treap<Integer> t = new Treap<>();
final int NUMS = 40000;
final int GAP = 307;
System.out.println("Checking... (no bad output means success)");
// Insert.
for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
t.insert(i);
}
System.out.println("Inserts complete");
// Remove.
for (int i = 1; i < NUMS; i += 2) {
t.remove(i);
}
System.out.println("Removes complete");
// Print tree.
if (NUMS < 40) {
t.printTree();
}
// Find min and find max.
if (t.findMin() != 2 || t.findMax() != NUMS - 2) {
System.out.println("FindMin or FindMax error!");
}
// Contains.
for (int i = 2; i < NUMS; i += 2) {
if (!t.contains(i)) {
System.out.println("Error: Find fails for " + i);
}
}
for (int i = 1; i < NUMS; i += 2) {
if (t.contains(i)) {
System.out.println("Error: Found deleted item " + i);
}
}
}
/**
* Insert into the tree.
* Does nothing if x is already present.
*
* @param x The item to insert.
*/
public void insert(T x) {
root = insert(x, root);
}
/**
* Remove from the tree.
* Does nothing if x is not found.
*
* @param x The item to remove.
*/
public void remove(T x) {
root = remove(x, root);
}
/**
* Find the smallest item in the tree.
*
* @return The smallest item, or throw exception if empty.
*/
public T findMin() throws Exception {
if (isEmpty()) {
throw new Exception("Treap is empty!");
}
TreapNode<T> ptr = root;
while (ptr.left != nullNode) {
ptr = ptr.left;
}
return ptr.element;
}
/**
* Find the largest item in the tree.
*
* @return The largest item, or throw exception if empty.
*/
public T findMax() throws Exception {
if (isEmpty()) {
throw new Exception("Treap is empty!");
}
TreapNode<T> ptr = root;
while (ptr.right != nullNode) {
ptr = ptr.right;
}
return ptr.element;
}
/**
* Find an item in the tree.
*
* @param x The item to search for.
* @return True if x is found.
*/
public boolean contains(T x) {
TreapNode<T> current = root;
nullNode.element = x;
for (; ; ) {
int compareResult = x.compareTo(current.element);
if (compareResult < 0) {
current = current.left;
} else if (compareResult > 0) {
current = current.right;
} else {
return current != nullNode;
}
}
}
/**
* 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("Treap is empty!");
} else {
printTree(root);
}
}
/**
* Internal method to insert into a subtree.
*
* @param x The item to insert.
* @param t The node that roots the subtree.
* @return The new root of the subtree.
*/
private TreapNode<T> insert(T x, TreapNode<T> t) {
if (t == nullNode) {
return new TreapNode<>(x, nullNode, nullNode);
}
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
t.left = insert(x, t.left);
if (t.left.priority < t.priority) {
t = rotateWithLeftChild(t);
}
} else if (compareResult > 0) {
t.right = insert(x, t.right);
if (t.right.priority < t.priority) {
t = rotateWithRightChild(t);
}
}
// Otherwise, it's a duplicate; do nothing
return t;
}
/**
* Internal method to remove from a subtree.
*
* @param x The item to remove.
* @param t The node that roots the subtree.
* @return The new root of the subtree.
*/
private TreapNode<T> remove(T x, TreapNode<T> t) {
if (t != nullNode) {
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
t.left = remove(x, t.left);
} else if (compareResult > 0) {
t.right = remove(x, t.right);
} else {
// Match found.
if (t.left.priority < t.right.priority) {
t = rotateWithLeftChild(t);
} else {
t = rotateWithRightChild(t);
}
// Continue on down.
if (t != nullNode) {
t = remove(x, t);
} else { // At a leaf.
t.left = nullNode;
}
}
}
return t;
}
/**
* Internal method to print a subtree in sorted order.
*
* @param t The node that roots the tree.
*/
private void printTree(TreapNode<T> t) {
if (t != t.left) {
printTree(t.left);
System.out.println(t.element.toString());
printTree(t.right);
}
}
/**
* Rotate binary tree node with left child.
*/
private TreapNode<T> rotateWithLeftChild(TreapNode<T> k2) {
TreapNode<T> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
/**
* Rotate binary tree node with right child.
*/
private TreapNode<T> rotateWithRightChild(TreapNode<T> k1) {
TreapNode<T> k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
/**
* Treap node class.
*
* @param <AnyType> Any type.
*/
private static class TreapNode<AnyType> {
private static Random randomObj = new Random();
AnyType element; // The data in the node.
TreapNode<AnyType> left; // Left child.
TreapNode<AnyType> right; // Right child.
int priority; // Priority.
// Constructors.
TreapNode(AnyType theElement) {
this(theElement, null, null);
}
TreapNode(AnyType element, TreapNode<AnyType> left, TreapNode<AnyType> right) {
this.element = element;
this.left = left;
this.right = right;
priority = randomObj.nextInt();
}
}
}
/*
Output:
Checking... (no bad output means success)
Inserts complete
Removes complete
*/