深入Rust Treap树实现（从零开始构建高性能平衡二叉搜索树）

什么是 Treap？

Treap 是一种随机化平衡二叉搜索树，其每个节点包含两个值：

• 键（key）：满足二叉搜索树性质（左子树 < 根 < 右子树）
• 优先级（priority）：满足最大堆性质（父节点优先级 ≥ 子节点）

通过为每个插入的节点随机分配一个优先级，Treap 在期望意义下保持平衡，从而保证操作（插入、删除、查找）的平均时间复杂度为 O(log n)。

为什么用 Rust 实现 Treap？

Rust 的内存安全和零成本抽象特性使其成为实现高效数据结构的理想选择。使用 Rc<RefCell<T>> 或 Box 可以安全地管理树节点的引用，避免空指针和数据竞争。此外，Rust 的模式匹配和不可变默认特性也促使我们写出更健壮的代码。

Treap 节点定义

首先，我们定义 Treap 的节点结构。为了简化，我们使用 Box 来管理子树，这样可以避免循环引用问题。

use std::rc::Rc;use std::cell::RefCell;use rand::Rng;#[derive(Debug, Clone)]struct TreapNode {    key: i32,    priority: u32,    left: Option<Rc<RefCell<TreapNode>>>,    right: Option<Rc<RefCell<TreapNode>>>,}impl TreapNode {    fn new(key: i32) -> Self {        let mut rng = rand::thread_rng();        let priority = rng.gen();        TreapNode {            key,            priority,            left: None,            right: None,        }    }}

这里我们使用 Rc<RefCell<TreapNode>> 来允许多个所有者共享同一个节点，并通过 RefCell 实现内部可变性。同时，rand crate 用于生成随机优先级。

旋转操作：维护堆性质

当插入或删除破坏了堆性质时，我们需要通过旋转来修复。Treap 支持两种旋转：

• 右旋（rotate_right）：将左子节点提升为根
• 左旋（rotate_left）：将右子节点提升为根

fn rotate_right(root: Rc<RefCell<TreapNode>>) -> Rc<RefCell<TreapNode>> {    let left_child = root.borrow().left.as_ref().unwrap().clone();    let left_right = left_child.borrow().right.clone();    left_child.borrow_mut().right = Some(root.clone());    root.borrow_mut().left = left_right;    left_child}fn rotate_left(root: Rc<RefCell<TreapNode>>) -> Rc<RefCell<TreapNode>> {    let right_child = root.borrow().right.as_ref().unwrap().clone();    let right_left = right_child.borrow().left.clone();    right_child.borrow_mut().left = Some(root.clone());    root.borrow_mut().right = right_left;    right_child}

插入操作

插入遵循 BST 规则，然后通过旋转恢复堆性质：

fn insert(    root: Option<Rc<RefCell<TreapNode>>>,    key: i32) -> Option<Rc<RefCell<TreapNode>>> {    match root {        None => Some(Rc::new(RefCell::new(TreapNode::new(key)))),        Some(node) => {            if key == node.borrow().key {                // 键已存在，不重复插入                return Some(node);            }            if key < node.borrow().key {                let new_left = insert(node.borrow().left.clone(), key);                node.borrow_mut().left = new_left;                // 检查堆性质                if node.borrow().priority < node.borrow().left.as_ref().unwrap().borrow().priority {                    return Some(rotate_right(node));                }            } else {                let new_right = insert(node.borrow().right.clone(), key);                node.borrow_mut().right = new_right;                if node.borrow().priority < node.borrow().right.as_ref().unwrap().borrow().priority {                    return Some(rotate_left(node));                }            }            Some(node)        }    }}

完整 Treap 封装类

为了方便使用，我们可以封装一个 Treap 结构体：

pub struct Treap {    root: Option<Rc<RefCell<TreapNode>>>,}impl Treap {    pub fn new() -> Self {        Treap { root: None }    }    pub fn insert(&mut self, key: i32) {        self.root = insert(self.root.take(), key);    }    // 可继续添加 search、delete、inorder_traversal 等方法}

总结

通过本教程，你已经掌握了如何在 Rust 语言 中从零实现一个功能完整的 Treap 数据结构。这种结构在竞赛编程、数据库索引、区间查询等场景中非常有用。Rust 的类型系统和内存模型帮助我们避免了许多 C/C++ 中常见的陷阱，使得实现既安全又高效。

如果你想进一步探索，可以尝试实现：可持久化 Treap（支持历史版本查询）、区间翻转、懒标记等高级功能。这些是 Rust Treap 实现 的进阶方向，也是提升算法能力的好方法。

希望这篇教程能帮助你理解 Treap 数据结构 并熟练运用 Rust 构建高性能程序！