在Rust中实现Trie字典树的更优方案及编译错误解决

44 | curr.children.push((c, Node { is_end: false, children: Vec::new() }));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| |
| second mutable borrow occurs here
| first borrow later used here

error[E0499]: cannot borrow curr.children as mutable more than once at a time
--> C:\Users\first\Developments\Temp\trie.rs:45:22
|
41 | curr = match curr.children.iter_mut().find(|e| e.0 == c) {
| ------------------------ first mutable borrow occurs here
...
45 | &mut curr.children.last_mut().unwrap().1
| ^^^^^^^^^^^^^^^^^^^^^^^^
| |
| second mutable borrow occurs here
| first borrow later used here

error: aborting due to 2 previous errors; 1 warning emitted

现咨询：是否有方法在保持类似C++写法的前提下解决该问题？若需重新实现，最优方案是什么？若我的curr相关理解有误，也请指正。

---

# 解答

## 一、保持类似C++写法的解决办法
可以通过**拆分查找和修改操作**，让前一次的可变借用提前释放，绕开借用检查器的限制。核心是把`find`操作从`match`的条件表达式中移出来，这样`iter_mut()`产生的可变借用在查找完成后就会被释放，不会和后续修改`children`的操作冲突。

修改后的`push`函数代码：
```rust
fn push(&mut self, string: &str) {
    let mut curr = self;

    for c in string.chars() {
        // 先执行查找，此时的可变借用在find结束后立即释放
        let existing_node = curr.children.iter_mut().find(|e| e.0 == c);
        
        curr = match existing_node {
            Some(e) => &mut e.1,
            None => {
                // 此时curr的children没有被借用，可以安全修改
                curr.children.push((c, Node { is_end: false, children: Vec::new() }));
                // 获取新添加节点的可变引用
                curr.children.last_mut().unwrap().1
            }
        };
    }

    curr.is_end = true;
}

这个版本的逻辑和你的C++代码完全一致，只是调整了代码结构，让借用检查器能够确认同一时间只有一个可变引用存在。

二、Rust环境下的最优实现方案 #

如果不局限于贴近C++的写法，Rust提供了更高效简洁的实现方式，核心是利用标准库的工具优化查找和插入逻辑：

方案1：使用HashMap（通用字符场景） #

用HashMap<char, Node>替代Vec<(char, Node)>，利用HashMap的entryAPI直接完成"查找不存在则插入"的操作，代码更简洁，查找效率也更高：

use std::collections::HashMap;

struct Node {
    is_end: bool,
    children: HashMap<char, Node>,
}

impl Node {
    fn new() -> Self {
        Node {
            is_end: false,
            children: HashMap::new(),
        }
    }

    fn push(&mut self, string: &str) {
        let mut curr = self;
        for c in string.chars() {
            // entry API自动处理查找/插入逻辑，返回可变引用
            curr = curr.children.entry(c).or_insert_with(Node::new);
        }
        curr.is_end = true;
    }

    fn has(&self, string: &str) -> bool {
        let mut curr = self;
        for c in string.chars() {
            match curr.children.get(&c) {
                Some(node) => curr = node,
                None => return false,
            }
        }
        curr.is_end
    }
}

方案2：使用数组（固定字符集场景） #

如果只处理固定范围的字符（比如小写英文字母），可以用数组替代HashMap，实现O(1)的查找和插入效率：

struct Node {
    is_end: bool,
    children: [Option<Box<Node>>; 26], // 对应a-z共26个小写字母
}

impl Node {
    fn new() -> Self {
        Node {
            is_end: false,
            children: Default::default(),
        }
    }

    fn push(&mut self, string: &str) {
        let mut curr = self;
        for c in string.chars() {
            // 将字符转换为数组索引（仅支持小写a-z）
            let idx = (c as u8 - b'a') as usize;
            // 获取或插入节点，返回可变引用
            curr = curr.children[idx].get_or_insert_with(|| Box::new(Node::new()));
        }
        curr.is_end = true;
    }

    fn has(&self, string: &str) {
        let mut curr = self;
        for c in string.chars() {
            let idx = (c as u8 - b'a') as usize;
            match &curr.children[idx] {
                Some(node) => curr = node,
                None => return false,
            }
        }
        curr.is_end
    }
}

三、关于curr的理解纠正 #

在C++中，curr是原始指针，编译器不会检查指针的借用冲突和有效性，你可以随意修改指向。但在Rust中，curr是可变引用（&mut Node），必须遵守严格的借用规则：

1. 同一时间，同一数据只能存在一个可变引用；
2. 引用的生命周期不能超过它指向的数据。

你最初的代码报错，是因为在match表达式中，curr.children.iter_mut()创建了对curr.children的可变借用，这个借用在整个match执行期间都有效。而在None分支中，你又尝试对curr.children进行第二次可变借用（push和last_mut），直接违反了"同一时间只能有一个可变引用"的规则。

把find操作移到match外面后，iter_mut()产生的借用在查找完成后就被释放了，后续修改curr.children时没有其他借用存在，因此通过了借用检查。

内容的提问来源于stack exchange，提问作者S.Y. Kim