Treap=Tree+Heap。Treap本身是一棵
二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的
二叉搜索树不同的是，Treap记录一个额外的数据，就是优先级。Treap在以关键码构成
二叉搜索树的同时，还按优先级来满足
堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。
旋转说明:
"
如果当前节点的优先级比父节点的优先级的值大就旋转，如果当前节点是根的左儿子就右旋如果当前节点是根的右儿子就左旋。"
右旋转
结点右旋:node x,令y=x->left; 先将y的右子树作为x的左子树,然后将x作为y的右子树, 最后将y作为x原父结点的子树(原x为左子树,此时y仍然为左子树,x为右子树,y也为右子树)
左旋转:
结点左旋:父节点node x,令y=x->right; 先将y的左子树作为x的右子树,然后将x作为y的左子树, 最后将y作为x原父结点的子树(原x为左子树,此时y仍然为左子树,x为右子树,y也为右子树)如下图所示.
完整的Java代码实现如下:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.ReentrantLock;
/**
* 随机二叉树的 Java代码实现
*
* @author xiemalin
*
*/
public class Treap<K extends Comparable<K>> extends ReentrantLock {
private Node root;
public void insert(K key, float fix) {
try {
Node node = new Node(key, fix);
lock();
if (root == null) {
root = node;
return;
}
insert(root, node);
} finally {
unlock();
}
}
private void insert(Node root, Node node) {
K key = node.key;
int compare = key.compareTo(root.key);
if (compare < 0) {
if (root.left == null) {
root.left = new Node(node.key, node.fix);
} else {
insert(root.left, node);
}
if (root.left.fix > root.fix) {
rotateRight(root);
}
} else if (compare > 0) {
if (root.right == null) {
root.right = new Node(node.key, node.fix);
} else {
insert(root.right, node);
}
if (root.right.fix > root.fix) {
rotateLeft(root);
}
} else {
//key exist do replace
root.fix = node.fix;
}
}
public Node remove(K key) {
try {
lock();
return remove(root, key);
} finally {
unlock();
}
}
public Node remove(Node root, K key) {
if (root == null) {
return null;
}
int compare = key.compareTo(root.key);
if (compare < 0) {
return remove(root.left, key);
} else if (compare > 0) {
return remove(root.right, key);
} else {
if (root.left == null && root.right == null) {
swapLocatePoint(root, null);
return root;
} else if (root.left == null) {
swapLocatePoint(root, root.right);
return root;
} else if (root.right == null) {
swapLocatePoint(root, root.left);
return root;
} else {
// has left and right node
if (root.left.fix < root.right.fix) {
rotateLeft(root);
root = find(root.key);
return remove(root, key);
} else {
rotateRight(root);
root = find(root.key);
return remove(root, key);
}
}
}
}
public Node find(K key) {
return find(root, key);
}
public Node find(Node root, K key) {
if (root == null) {
return null;
}
int compare = key.compareTo(root.key);
if (compare == 0) {
return root;
} else {
if (compare < 0) {
return find(root.left, key);
} else {
return find(root.right, key);
}
}
}
public Node findParent(Node root, K key, Node parent) {
if (root == null) {
return null;
}
int compare = key.compareTo(root.key);
if (compare == 0) {
return parent;
} else {
if (compare < 0) {
return findParent(root.left, key, root);
} else {
return findParent(root.right, key, root);
}
}
}
/**
* a
* \
* x
* / \
* nll y
*
* 左转之后的结果
* a
* \
* y
* / \
* x null
* \
* (y.left=null)
*
* @param x
*/
private void rotateLeft(Node x) {// rotate to left on node x //左旋当前节点
Node y = x.right; // 把当前节点的右节点，复制给y
x.right = y.left; // 把当前节点的右节点的左子树复制给当前节点
y.left = x; //
swapLocatePoint(x, y);
}
private void swapLocatePoint(Node x, Node y) {
Node parent = findParent(root, x.key, null);
if (parent == null) {
root = y;
return;
}
if (parent.left == x) {
parent.left = y;
} else {
parent.right = y;
}
}
public String toString() {
if (root == null) {
return "";
}
StringBuffer buffer = new StringBuffer(200);
flat(buffer, root);
return buffer.toString();
}
public void flat(StringBuffer buffer, Node
nodes) {
buffer.append("\n");
if (nodes != null && nodes.length > 0) {
List<Node> list = new LinkedList<Node>();
boolean hasValue = false;
for (Node node : nodes) {
buffer.append(node).append("|");
if (node.left != null) {
list.add(node.left);
hasValue = true;
} else {
list.add(new EmptyNode());
}
if (node.right != null) {
list.add(node.right);
hasValue = true;
} else {
list.add(new EmptyNode());
}
}
buffer = buffer.deleteCharAt(buffer.length() - 1);
if (hasValue) {
flat(buffer, list.toArray(new Treap.Node[list.size()]));
}
}
}
/**
* a
* \
* x
* / \
* y null
*
* 右转之后的结果
* a
* \
* y
* / \
* null x
* /
* (y.right=null)
*
* @param x
*/
private void rotateRight(Node x) {// rotate to right on node x
Node y = x.left;
x.left = y.right;
y.right = x;
swapLocatePoint(x, y);
}
public static void main(String[] args) {
Treap<Float> t = new Treap<Float>();
t.insert(9.5f, 0.491f);
t.insert(8.3f, 0.491f);
t.insert(10f, 0.971f);
t.insert(10.25f, 0.882f);
System.out.println(t);
//System.out.println(t.remove(10));
t.remove(10f);
System.out.println(t);
final Treap t2 = new Treap();
t2.insert(9.0f, 0.554f);
t2.insert(8.0f, 0.701f);
t2.insert(12.5f, 0.516f);
t2.insert(7.0f, 0.141f);
t2.insert(4.0f, 0.340f);
t2.insert(2.0f, 0.286f);
t2.insert(3.0f, 0.402f);
t2.insert(1.0f, 0.646f);
t2.insert(5.0f, 0.629f);
t2.insert(10.0f, 0.244f);
t2.insert(11.0f, 0.467f);
t2.insert(12.0f, 0.794f);
t2.insert(13.0f, 0.667f);
t2.insert(6.0f, 0.375f);
System.out.println(t2);
final Random r = new Random();
long time = System.currentTimeMillis();
ExecutorService es = Executors.newFixedThreadPool(3);
List<Future> futures = new ArrayList<Future>(3);
for (int i = 0; i < 3; i++) {
FutureTask<String> future =
new FutureTask<String>(new Callable<String>() {
public String call() {
for (int i = 0; i < 200000; i++) {
t2.insert(r.nextFloat(), r.nextFloat());
}
return null;
}});
es.execute(future);
futures.add(future);
}
for (Future future : futures) {
try {
future.get();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (ExecutionException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
System.out.println("time took:" + (System.currentTimeMillis() - time));
time = System.currentTimeMillis();
System.out.println(t2.find(6.0f));
System.out.println("time took:" + (System.currentTimeMillis() - time));
es.shutdown();
Treap<String> t3 = new Treap<String>();
t3.insert("abc", 222f);
t3.insert("ad", 222f);
t3.insert("fbc", 222f);
t3.insert("adbc", 222f);
t3.insert("bbc", 222f);
System.out.println(t3.find("bbc"));
}
class Node {
K key;
float fix;
Node left;
Node right;
public Node() {
}
/**
* @param key
* @param fix
*/
public Node(K key, float fix) {
super();
this.key = key;
this.fix = fix;
}
public String toString() {
return key+"";
}
}
class EmptyNode extends Node {
public String toString() {
return "NULL";
}
}
}
非泛型实现
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.ReentrantLock;
/**
* 随机二叉树的 Java代码实现
*
* @author xiemalin
*
*/
public class Treap extends ReentrantLock {
private Node root;
public void insert(float key, float fix) {
try {
Node node = new Node(key, fix);
lock();
if (root == null) {
root = node;
return;
}
insert(root, node);
} finally {
unlock();
}
}
public void set(float key, float fix) {
try {
Node node = new Node(key, fix);
lock();
if (root == null) {
root = node;
return;
}
try {
insert(root, node);
} catch (KeyExistException e) {
remove(root, key);
insert(root, node);
}
} finally {
unlock();
}
}
private void insert(Node root, Node node) {
float key = node.key;
if (key < root.key) {
if (root.left == null) {
root.left = new Node(node.key, node.fix);
} else {
insert(root.left, node);
}
if (root.left.fix > root.fix) {
rotateRight(root);
}
} else if (key > root.key) {
if (root.right == null) {
root.right = new Node(node.key, node.fix);
} else {
insert(root.right, node);
}
if (root.right.fix > root.fix) {
rotateLeft(root);
}
} else {
//key exist ignore
throw new KeyExistException("key=" + key + " already exist");
//root.fix = node.fix;
}
}
public Node remove(float key) {
try {
lock();
return remove(root, key);
} finally {
unlock();
}
}
public Node remove(Node root, float key) {
if (root == null) {
return null;
}
if (key < root.key) {
return remove(root.left, key);
} else if (key > root.key) {
return remove(root.right, key);
} else {
if (root.left == null && root.right == null) {
swapLocatePoint(root, null);
return root;
} else if (root.left == null) {
swapLocatePoint(root, root.right);
return root;
} else if (root.right == null) {
swapLocatePoint(root, root.left);
return root;
} else {
// has left and right node
if (root.left.fix < root.right.fix) {
rotateLeft(root);
root = find(root.key);
return remove(root, key);
} else {
rotateRight(root);
root = find(root.key);
return remove(root, key);
}
}
}
}
public Node find(float key) {
return find(root, key);
}
public Node find(Node root, float key) {
if (root == null) {
return null;
}
if (key == root.key) {
return root;
} else {
if (key < root.key) {
return find(root.left, key);
} else {
return find(root.right, key);
}
}
}
public Node findParent(Node root, float key, Node parent) {
if (root == null) {
return null;
}
if (key == root.key) {
return parent;
} else {
if (key < root.key) {
return findParent(root.left, key, root);
} else {
return findParent(root.right, key, root);
}
}
}
/**
* a
* \
* x
* / \
* nll y
*
* 左转之后的结果
* a
* \
* y
* / \
* x null
* \
* (y.left=null)
*
* @param x
*/
private void rotateLeft(Node x) {// rotate to left on node x //左旋当前节点
Node y = x.right; // 把当前节点的右节点，复制给y
x.right = y.left; // 把当前节点的右节点的左子树复制给当前节点
y.left = x; //
swapLocatePoint(x, y);
}
private void swapLocatePoint(Node x, Node y) {
Node parent = findParent(root, x.key, null);
if (parent == null) {
root = y;
return;
}
if (parent.left == x) {
parent.left = y;
} else {
parent.right = y;
}
}
public String toString() {
if (root == null) {
return "";
}
StringBuffer buffer = new StringBuffer(200);
flat(buffer, root);
return buffer.toString();
}
public void flat(StringBuffer buffer, Node nodes) {
buffer.append("\n");
if (nodes != null && nodes.length > 0) {
List<Node> list = new LinkedList<Node>();
boolean hasValue = false;
for (Node node : nodes) {
buffer.append(node).append("|");
if (node.left != null) {
list.add(node.left);
hasValue = true;
} else {
list.add(new EmptyNode());
}
if (node.right != null) {
list.add(node.right);
hasValue = true;
} else {
list.add(new EmptyNode());
}
}
buffer = buffer.deleteCharAt(buffer.length() - 1);
if (hasValue) {
flat(buffer, list.toArray(new Treap.Node[list.size()]));
}
}
}
/**
* a
* \
* x
* / \
* y null
*
* 右转之后的结果
* a
* \
* y
* / \
* null x
* /
* (y.right=null)
*
* @param x
*/
private void rotateRight(Node x) {// rotate to right on node x
Node y = x.left;
x.left = y.right;
y.right = x;
swapLocatePoint(x, y);
}
public static void main(String[] args) {
Treap t = new Treap();
t.insert(0.0f, 0.845f);
System.out.println(t);
t.insert(0.5f, 0.763f);
System.out.println(t);
t.insert(0.25f, 0.244f);
System.out.println(t);
t.insert(1.0f, 0.347f);
System.out.println(t);
t.insert(1.25f, 0.925f);
System.out.println(t);
//System.out.println(t.remove(10));
t.remove(10f);
System.out.println(t);
final Treap t2 = new Treap();
t2.insert(9.0f, 0.554f);
t2.insert(8.0f, 0.701f);
t2.insert(12.5f, 0.516f);
t2.insert(7.0f, 0.141f);
t2.insert(4.0f, 0.340f);
t2.insert(2.0f, 0.286f);
t2.insert(3.0f, 0.402f);
t2.insert(1.0f, 0.646f);
t2.insert(5.0f, 0.629f);
t2.insert(10.0f, 0.244f);
t2.insert(11.0f, 0.467f);
t2.insert(12.0f, 0.794f);
t2.insert(13.0f, 0.667f);
t2.insert(6.0f, 0.375f);
System.out.println(t2);
final Random r = new Random();
long time = System.currentTimeMillis();
ExecutorService es = Executors.newFixedThreadPool(3);
List<Future> futures = new ArrayList<Future>(3);
for (int i = 0; i < 3; i++) {
FutureTask<String> future =
new FutureTask<String>(new Callable<String>() {
public String call() {
for (int i = 0; i < 1000000; i++) {
t2.set(r.nextFloat(), r.nextFloat());
}
return null;
}});
es.execute(future);
futures.add(future);
}
for (Future future : futures) {
try {
future.get();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (ExecutionException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
System.out.println("time took:" + (System.currentTimeMillis() - time));
time = System.currentTimeMillis();
System.out.println(t2.find(6.0f));
System.out.println("time took:" + (System.currentTimeMillis() - time));
es.shutdown();
}
class Node {
float key;
float fix;
Node left;
Node right;
public Node() {
}
/**
* @param key
* @param fix
*/
public Node(float key, float fix) {
super();
this.key = key;
this.fix = fix;
}
public String toString() {
return key+"";
}
}
class EmptyNode extends Node {
public String toString() {
return "NULL";
}
}
}
参考资料:
DEMO示例 http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/Treap-Example.html
Good Luck!
Yours Matthew!
posted on 2012-05-16 14:37
x.matthew 阅读(4317)
评论(0) 编辑 收藏