Treap=Tree+Heap。Treap本身是一棵
二叉搜索樹(shù)，它的左子樹(shù)和右子樹(shù)也分別是一個(gè)Treap，和一般的
二叉搜索樹(shù)不同的是，Treap記錄一個(gè)額外的數(shù)據(jù)，就是優(yōu)先級(jí)。Treap在以關(guān)鍵碼構(gòu)成
二叉搜索樹(shù)的同時(shí)，還按優(yōu)先級(jí)來(lái)滿足
堆的性質(zhì)(在這里我們假設(shè)節(jié)點(diǎn)的優(yōu)先級(jí)大于該節(jié)點(diǎn)的孩子的優(yōu)先級(jí))。但是這里要注意的是Treap和二叉堆有一點(diǎn)不同，就是二叉堆必須是完全二叉樹(shù)，而Treap可以并不一定是。
旋轉(zhuǎn)說(shuō)明:
"
如果當(dāng)前節(jié)點(diǎn)的優(yōu)先級(jí)比父節(jié)點(diǎn)的優(yōu)先級(jí)的值大就旋轉(zhuǎn)，如果當(dāng)前節(jié)點(diǎn)是根的左兒子就右旋如果當(dāng)前節(jié)點(diǎn)是根的右兒子就左旋。"
右旋轉(zhuǎn)
結(jié)點(diǎn)右旋:node x,令y=x->left; 先將y的右子樹(shù)作為x的左子樹(shù),然后將x作為y的右子樹(shù), 最后將y作為x原父結(jié)點(diǎn)的子樹(shù)(原x為左子樹(shù),此時(shí)y仍然為左子樹(shù),x為右子樹(shù),y也為右子樹(shù))
左旋轉(zhuǎn):
結(jié)點(diǎn)左旋:父節(jié)點(diǎn)node x,令y=x->right; 先將y的左子樹(shù)作為x的右子樹(shù),然后將x作為y的左子樹(shù), 最后將y作為x原父結(jié)點(diǎn)的子樹(shù)(原x為左子樹(shù),此時(shí)y仍然為左子樹(shù),x為右子樹(shù),y也為右子樹(shù))如下圖所示.
完整的Java代碼實(shí)現(xiàn)如下:
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;
/**
* 隨機(jī)二叉樹(shù)的 Java代碼實(shí)現(xiàn)
*
* @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
*
* 左轉(zhuǎn)之后的結(jié)果
* a
* \
* y
* / \
* x null
* \
* (y.left=null)
*
* @param x
*/
private void rotateLeft(Node x) {// rotate to left on node x //左旋當(dāng)前節(jié)點(diǎn)
Node y = x.right; // 把當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)，復(fù)制給y
x.right = y.left; // 把當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)的左子樹(shù)復(fù)制給當(dāng)前節(jié)點(diǎn)
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
*
* 右轉(zhuǎn)之后的結(jié)果
* 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";
}
}
}
非泛型實(shí)現(xiàn)
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;
/**
* 隨機(jī)二叉樹(shù)的 Java代碼實(shí)現(xiàn)
*
* @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
*
* 左轉(zhuǎn)之后的結(jié)果
* a
* \
* y
* / \
* x null
* \
* (y.left=null)
*
* @param x
*/
private void rotateLeft(Node x) {// rotate to left on node x //左旋當(dāng)前節(jié)點(diǎn)
Node y = x.right; // 把當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)，復(fù)制給y
x.right = y.left; // 把當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)的左子樹(shù)復(fù)制給當(dāng)前節(jié)點(diǎn)
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
*
* 右轉(zhuǎn)之后的結(jié)果
* 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 閱讀(4304)
評(píng)論(0) 編輯 收藏