前言

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代码实现

前言