实现二叉搜索树时不能多次借用节点作为可变节点

Question

我正在尝试在 Rust 中实现二叉搜索树，但在插入元素时遇到了问题。在 Rust 中这样做的惯用方法是什么？

这是我的实现：

use std::cmp::Ordering;

pub struct BinarySearchTree {
    root: OptNode,
    size: u32,
}

type OptNode = Option<Box<Node>>;

struct Node {
    key: i32,
    left: OptNode,
    right: OptNode,
}

impl BinarySearchTree {
    pub fn new() -> Self {
        BinarySearchTree {
            root: None,
            size: 0,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    pub fn size(&self) -> u32 {
        self.size
    }

    pub fn contains(&self, key: i32) -> bool {
        let mut node = &self.root;
        while let Some(ref boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &boxed_node.left,
                Ordering::Greater => node = &boxed_node.right,
                Ordering::Equal => return true,
            }
        }

        false
    }

    pub fn insert(&mut self, key: i32) {
        let mut node = &mut self.root;
        while let Some(ref mut boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &mut boxed_node.left,
                Ordering::Greater => node = &mut boxed_node.right,
                Ordering::Equal => return,
            }
        }

        *node = Some(Box::new(Node {
            key: key,
            left: None,
            right: None,
        }));
    }
}

fn main() {}

以下是我收到的错误：

use std::cmp::Ordering;

pub struct BinarySearchTree {
    root: OptNode,
    size: u32,
}

type OptNode = Option<Box<Node>>;

struct Node {
    key: i32,
    left: OptNode,
    right: OptNode,
}

impl BinarySearchTree {
    pub fn new() -> Self {
        BinarySearchTree {
            root: None,
            size: 0,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    pub fn size(&self) -> u32 {
        self.size
    }

    pub fn contains(&self, key: i32) -> bool {
        let mut node = &self.root;
        while let Some(ref boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &boxed_node.left,
                Ordering::Greater => node = &boxed_node.right,
                Ordering::Equal => return true,
            }
        }

        false
    }

    pub fn insert(&mut self, key: i32) {
        let mut node = &mut self.root;
        while let Some(ref mut boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &mut boxed_node.left,
                Ordering::Greater => node = &mut boxed_node.right,
                Ordering::Equal => return,
            }
        }

        *node = Some(Box::new(Node {
            key: key,
            left: None,
            right: None,
        }));
    }
}

fn main() {}

Answer 1

Rust 的编译器还不够复杂（还？）来处理这种情况。Rust 发现您试图多次可变地借用相同的值，因为它会在循环中看到对同一变量的重复可变借用。当然，这不是您想要做的，因为您想在每次迭代时重新分配变量，但 Rust 不支持分配给借用的变量。

我们需要做的是使用中间变量，以便编译器可以正确跟踪借用。我们如何创建不确定数量的变量？用递归！

impl BinarySearchTree {
    pub fn insert(&mut self, key: i32) {
        fn insert_node(node: &mut OptNode, key: i32) {
            if let Some(ref mut boxed_node) = *node {
                match key.cmp(&boxed_node.key) {
                    Ordering::Less => insert_node(&mut boxed_node.left, key),
                    Ordering::Greater => insert_node(&mut boxed_node.right, key),
                    Ordering::Equal => return,
                }
            } else {
                *node = Some(Box::new(Node { key: key, left: None, right: None}));
            }
        }

        insert_node(&mut self.root, key)
    }
}

注意：虽然该算法是尾递归的，但 Rust 并未将其优化为尾调用，因此在退化情况下可能会导致堆栈溢出。