深入理解Splay树：Rust语言实现自平衡二叉搜索树（从零开始构建高效动态数据结构）

为什么选择 Rust 实现？

Rust 以其内存安全、零成本抽象和并发无畏著称。使用 Rust 实现 Splay 树不仅能学习数据结构，还能深入理解 Rust 的所有权（ownership）、借用（borrowing）和智能指针（如 Rc<RefCell<T>>）等核心概念。

第一步：定义树节点结构

首先，我们需要定义 Splay 树的节点。每个节点包含值、左子树和右子树：

use std::rc::Rc;use std::cell::RefCell;#[derive(Debug)]struct SplayNode {    val: i32,    left: Option<Rc<RefCell<SplayNode>>>,    right: Option<Rc<RefCell<SplayNode>>>,}impl SplayNode {    fn new(val: i32) -> Self {        SplayNode {            val,            left: None,            right: None,        }    }}

这里我们使用 Rc<RefCell<T>> 来允许多个所有者共享同一个节点，并支持内部可变性——这是在不使用 unsafe 的情况下构建图或树结构的常用模式。

第二步：实现旋转操作

Splay 操作依赖于三种基本旋转：右旋（zig）、左旋（zag），以及组合旋转（zig-zig, zig-zag）。我们先实现单次旋转：

// 右旋：将左子节点提升为父节点fn rotate_right(root: &Option<Rc<RefCell<SplayNode>>>) -> Option<Rc<RefCell<SplayNode>>> {    if let Some(node) = root {        let mut node_ref = node.borrow_mut();        if let Some(left_child) = node_ref.left.take() {            let left_right = left_child.borrow().right.clone();            node_ref.left = left_right;            drop(node_ref);            left_child.borrow_mut().right = Some(node.clone());            return Some(left_child);        }    }    root.clone()}// 左旋：将右子节点提升为父节点fn rotate_left(root: &Option<Rc<RefCell<SplayNode>>>) -> Option<Rc<RefCell<SplayNode>>> {    if let Some(node) = root {        let mut node_ref = node.borrow_mut();        if let Some(right_child) = node_ref.right.take() {            let right_left = right_child.borrow().left.clone();            node_ref.right = right_left;            drop(node_ref);            right_child.borrow_mut().left = Some(node.clone());            return Some(right_child);        }    }    root.clone()}

第三步：实现 Splay 操作

Splay 操作会将目标值对应的节点移动到根。我们采用递归方式查找并伸展：

fn splay(root: Option<Rc<RefCell<SplayNode>>>, key: i32) -> Option<Rc<RefCell<SplayNode>>> {    if root.is_none() {        return None;    }    let val = root.as_ref().unwrap().borrow().val;    if val == key {        return root;    }    if key < val {        // 目标在左子树        let left = root.as_ref().unwrap().borrow().left.clone();        if left.is_none() {            return root;        }        let left_val = left.as_ref().unwrap().borrow().val;        if key < left_val {            // Zig-Zig: 先对左子树 splay，再两次右旋            let new_left = splay(left, key);            let mut root_clone = root.unwrap();            root_clone.borrow_mut().left = new_left;            let once_rotated = rotate_right(&Some(Rc::new(RefCell::new(root_clone))));            rotate_right(&once_rotated)        } else if key > left_val {            // Zig-Zag: 先对左子树 splay，再左旋再右旋            let new_left = splay(left, key);            let mut root_clone = root.unwrap();            root_clone.borrow_mut().left = new_left;            let once_rotated = rotate_left(&Some(Rc::new(RefCell::new(root_clone))));            rotate_right(&once_rotated)        } else {            // Zig            rotate_right(&root)        }    } else {        // 目标在右子树（对称处理）        let right = root.as_ref().unwrap().borrow().right.clone();        if right.is_none() {            return root;        }        let right_val = right.as_ref().unwrap().borrow().val;        if key > right_val {            // Zag-Zag            let new_right = splay(right, key);            let mut root_clone = root.unwrap();            root_clone.borrow_mut().right = new_right;            let once_rotated = rotate_left(&Some(Rc::new(RefCell::new(root_clone))));            rotate_left(&once_rotated)        } else if key < right_val {            // Zag-Zig            let new_right = splay(right, key);            let mut root_clone = root.unwrap();            root_clone.borrow_mut().right = new_right;            let once_rotated = rotate_right(&Some(Rc::new(RefCell::new(root_clone))));            rotate_left(&once_rotated)        } else {            // Zag            rotate_left(&root)        }    }}

第四步：封装 SplayTree 结构

为了更易用，我们封装一个 SplayTree 类型：

pub struct SplayTree {    root: Option<Rc<RefCell<SplayNode>>>,}impl SplayTree {    pub fn new() -> Self {        SplayTree { root: None }    }    pub fn insert(&mut self, key: i32) {        if self.root.is_none() {            self.root = Some(Rc::new(RefCell::new(SplayNode::new(key))));            return;        }        self.root = splay(self.root.clone(), key);        let root_val = self.root.as_ref().unwrap().borrow().val;        if root_val == key {            return; // 已存在        }        let new_node = Rc::new(RefCell::new(SplayNode::new(key)));        if key < root_val {            new_node.borrow_mut().left = self.root.as_ref().unwrap().borrow().left.clone();            new_node.borrow_mut().right = Some(self.root.clone().unwrap());            if let Some(ref mut r) = new_node.borrow_mut().right {                r.borrow_mut().left = None;            }        } else {            new_node.borrow_mut().right = self.root.as_ref().unwrap().borrow().right.clone();            new_node.borrow_mut().left = Some(self.root.clone().unwrap());            if let Some(ref mut l) = new_node.borrow_mut().left {                l.borrow_mut().right = None;            }        }        self.root = Some(new_node);    }    pub fn search(&mut self, key: i32) -> bool {        self.root = splay(self.root.clone(), key);        if let Some(root) = &self.root {            root.borrow().val == key        } else {            false        }    }}

第五步：测试你的 Splay 树

现在你可以这样使用它：

fn main() {    let mut tree = SplayTree::new();    tree.insert(10);    tree.insert(20);    tree.insert(5);    tree.insert(15);    println!("Search 15: {}", tree.search(15)); // true    println!("Search 100: {}", tree.search(100)); // false}

总结

通过本教程，你已经掌握了如何在 Rust 中实现一个完整的 Splay 树。这不仅加深了你对 Rust Splay树实现 的理解，也让你熟悉了 Rust自平衡二叉搜索树 的构建技巧。Splay 树虽然实现稍复杂，但其“越用越快”的特性使其在某些场景下优于 AVL 或红黑树。

希望这篇 Splay树教程 能帮助你开启 Rust 数据结构之旅。记住，实践是最好的老师——尝试添加删除操作、遍历方法，或将其泛型化以支持任意类型！

关键词回顾：Rust Splay树实现、Rust自平衡二叉搜索树、Splay树教程、Rust数据结构。