Rust稳定二叉搜索树库stable_bst使用指南

stable_bst是一个Rust实现的稳定二叉搜索树库，提供了高效的有序数据存储和检索功能。它特别适合需要维护有序数据集合的场景。

主要特性

• 基于二叉搜索树实现，保证数据有序性
• 提供O(log n)时间复杂度的插入、删除和查找操作
• 支持迭代器和范围查询
• 内存安全且线程安全的设计

安装

在Cargo.toml中添加依赖：

[dependencies]
stable_bst = "0.2.0"

基本使用方法

创建二叉搜索树

use stable_bst::TreeMap;

let mut tree = TreeMap::new();

插入元素

tree.insert(3, "three");
tree.insert(1, "one");
tree.insert(2, "two");

查找元素

if let Some(value) = tree.get(&2) {
    println!("Found: {}", value);  // 输出: Found: two
}

删除元素

tree.remove(&1);

遍历元素

for (key, value) in &tree {
    println!("{}: {}", key, value);
}
// 输出:
// 2: two
// 3: three

高级功能

范围查询

use std::ops::Bound;

// 查询2到3之间的元素
let range = tree.range((Bound::Included(2), Bound::Included(3)));
for (key, value) in range {
    println!("{}: {}", key, value);
}

获取最小和最大元素

if let Some((min_key, min_value)) = tree.first_key_value() {
    println!("Min: {}: {}", min_key, min_value);
}

if let Some((max_key, max_value)) = tree.last_key_value() {
    println!("Max: {}: {}", max_key, max_value);
}

自定义比较函数

use stable_bst::TreeSet;
use std::cmp::Ordering;

#[derive(Debug)]
struct Person {
    name: String,
    age: u32,
}

let mut people = TreeSet::new(|a: &Person, b: &Person| a.age.cmp(&b.age));

people.insert(Person { name: "Alice".to_string(), age: 30 });
people.insert(Person { name: "Bob".to_string(), age: 25 });
people.insert(Person { name: "Charlie".to_string(), age: 35 });

for person in &people {
    println!("{}: {}", person.name, person.age);
}
// 输出:
// Bob: 25
// Alice: 30
// Charlie: 35

完整示例代码

use stable_bst::TreeMap;
use std::ops::Bound;

fn main() {
    // 创建二叉搜索树
    let mut tree = TreeMap::new();
    
    // 插入元素
    tree.insert(5, "apple");
    tree.insert(3, "banana");
    tree.insert(7, "orange");
    tree.insert(2, "pear");
    tree.insert(4, "grape");
    
    // 查找元素
    if let Some(fruit) = tree.get(&4) {
        println!("Key 4 contains: {}", fruit); // 输出: grape
    }
    
    // 删除元素
    tree.remove(&3);
    
    // 遍历元素
    println!("All elements:");
    for (key, value) in &tree {
        println!("{}: {}", key, value);
    }
    /* 输出:
    2: pear
    4: grape
    5: apple
    7: orange
    */
    
    // 范围查询
    println!("Range query (3-6):");
    let range = tree.range((Bound::Included(3), Bound::Included(6)));
    for (key, value) in range {
        println!("{}: {}", key, value);
    }
    /* 输出:
    4: grape
    5: apple
    */
    
    // 获取最小和最大元素
    if let Some((min_key, min_value)) = tree.first_key_value() {
        println!("Min key: {}, value: {}", min_key, min_value); // 输出: 2, pear
    }
    
    if let Some((max_key, max_value)) = tree.last_key_value() {
        println!("Max key: {}, value: {}", max_key, max_value); // 输出: 7, orange
    }
}

性能注意事项

• 对于随机数据，stable_bst表现良好
• 对于已排序的数据，可能导致树不平衡，影响性能
• 考虑使用BTreeMap作为替代，特别是当数据量较大时

stable_bst是一个简单但功能完整的二叉搜索树实现，适合需要有序数据存储和检索的中小型数据集场景。