前言
Treap(树堆)是一种数据结构,同时具有二叉搜索树(BST)和最小堆的特性。它的实现相对简单,通常用于需要同时维护元素顺序和优先级的情况。
Treap的理论解释
Treap的每个节点包含两个属性:一个键值和一个随机优先级。它满足以下两个性质:
BST性质: 每个节点的左子树中的键值小于该节点的键值,右子树中的键值大于该节点的键值。
堆性质: 每个节点的优先级大于其子节点的优先级。
这两个性质共同确保了Treap的有序性和优先级性。
Java代码实现
import java.util.Random;
class Node {
int key, priority;
Node left, right;
Node(int key) {
this.key = key;
this.priority = new Random().nextInt(); // Assign random priority
}
}
public class Treap {
Node root;
private Node leftRotate(Node node) {
Node newRoot = node.right;
node.right = newRoot.left;
newRoot.left = node;
return newRoot;
}
private Node rightRotate(Node node) {
Node newRoot = node.left;
node.left = newRoot.right;
newRoot.right = node;
return newRoot;
}
public Node insert(Node root, int key) {
if (root == null)
return new Node(key);
if (key <= root.key) {
root.left = insert(root.left, key);
if (root.left.priority > root.priority)
root = rightRotate(root);
} else {
root.right = insert(root.right, key);
if (root.right.priority > root.priority)
root = leftRotate(root);
}
return root;
}
public void insert(int key) {
root = insert(root, key);
}
// In-order traversal for testing
private void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.key + " ");
inOrderTraversal(node.right);
}
}
public void inOrderTraversal() {
inOrderTraversal(root);
}
public static void main(String[] args) {
Treap treap = new Treap();
int[] testData = {5, 3, 7, 2, 4, 6, 8};
for (int key : testData)
treap.insert(key);
treap.inOrderTraversal();
}
}
使用场景
优先级队列: Treap可以用作优先级队列,允许你以一种高效的方式插入和删除具有不同优先级的元素。
动态中位数查找: 在一个数据流中,Treap可以用来实时查找中位数,因为它维护了有序性和优先级性。
范围查询: Treap允许高效地执行范围查询,如查找所有在给定范围内的元素。
平衡树替代: 在某些情况下,Treap可以作为平衡树(如AVL树、红黑树)的替代,提供较好的平衡性能。
随机化算法: 由于Treap的优先级随机性,它可以用于设计随机化算法。
优先级队列
import java.util.Random;
class Node {
int key, priority;
Node left, right;
Node(int key) {
this.key = key;
this.priority = new Random().nextInt(); // Assign random priority
}
}
public class TreapPriorityQueue {
Node root;
// ...(省略插入、旋转等方法,与前面的代码相同)
public int extractMax() {
if (root == null)
throw new IllegalStateException("Priority queue is empty");
int maxKey = root.key;
root = merge(root.left, root.right);
return maxKey;
}
public static void main(String[] args) {
TreapPriorityQueue pq = new TreapPriorityQueue();
pq.insert(5);
pq.insert(3);
pq.insert(7);
pq.insert(2);
pq.insert(4);
while (!pq.isEmpty()) {
System.out.println("Extracted max: " + pq.extractMax());
}
}
}
动态中位数查找
// 在 TreapPriorityQueue 类中添加以下方法
public int findMedian() {
if (root == null)
throw new IllegalStateException("Treap is empty");
int size = size(root.left) + 1;
if (size == (size(root) + 1) / 2)
return root.key;
else if (size > (size(root) + 1) / 2)
return findMedian(root.left);
else
return findMedian(root.right);
}
public static void main(String[] args) {
TreapPriorityQueue pq = new TreapPriorityQueue();
pq.insert(5);
pq.insert(3);
pq.insert(7);
pq.insert(2);
pq.insert(4);
pq.insert(6);
pq.insert(8);
System.out.println("Median: " + pq.findMedian()); // Should output 5
}
范围查询
// 在 TreapPriorityQueue 类中添加以下方法
public void rangeQuery(Node node, int low, int high) {
if (node == null)
return;
if (node.key >= low && node.key <= high) {
System.out.print(node.key + " ");
rangeQuery(node.left, low, high);
rangeQuery(node.right, low, high);
} else if (node.key < low)
rangeQuery(node.right, low, high);
else
rangeQuery(node.left, low, high);
}
public void rangeQuery(int low, int high) {
rangeQuery(root, low, high);
}
public static void main(String[] args) {
TreapPriorityQueue pq = new TreapPriorityQueue();
pq.insert(5);
pq.insert(3);
pq.insert(7);
pq.insert(2);
pq.insert(4);
pq.insert(6);
pq.insert(8);
System.out.print("Elements in range [4, 7]: ");
pq.rangeQuery(4, 7); // Should output 5 4 6 7
}
平衡树替代
// 在 TreapPriorityQueue 类中添加以下方法
public int getHeight(Node node) {
if (node == null)
return 0;
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
public boolean isBalanced() {
return isBalanced(root);
}
private boolean isBalanced(Node node) {
if (node == null)
return true;
int balanceFactor = getHeight(node.left) - getHeight(node.right);
return Math.abs(balanceFactor) <= 1 && isBalanced(node.left) && isBalanced(node.right);
}
public static void main(String[] args) {
TreapPriorityQueue pq = new TreapPriorityQueue();
pq.insert(5);
pq.insert(3);
pq.insert(7);
pq.insert(2);
pq.insert(4);
pq.insert(6);
pq.insert(8);
System.out.println("Is the Treap balanced? " + pq.isBalanced()); // Should output true
}
随机化算法
// 在 TreapPriorityQueue 类中添加以下方法
public void shuffle() {
List<Integer> keys = new ArrayList<>();
inOrderTraversalToList(root, keys);
Collections.shuffle(keys);
root = null;
for (int key : keys) {
insert(key);
}
}
private void inOrderTraversalToList(Node node, List<Integer> list) {
if (node != null) {
inOrderTraversalToList(node.left, list);
list.add(node.key);
inOrderTraversalToList(node.right, list);
}
}
public static void main(String[] args) {
TreapPriorityQueue pq = new TreapPriorityQueue();
pq.insert(5);
pq.insert(3);
pq.insert(7);
pq.insert(2);
pq.insert(4);
pq.insert(6);
pq.insert(8);
System.out.print("Original order: ");
pq.inOrderTraversal(); // Should output ordered elements
pq.shuffle();
System.out.print("\nShuffled order: ");
pq.inOrderTraversal(); // Should output shuffled elements
}
Treap的理论与Java代码实现