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 閱讀(4293)
評論(0) 編輯 收藏