如何获得最小 BST 元素？

Question

鉴于此 BST 结构：

pub enum BST{
    Nil,
    Node{
        k: i32,
        l: Box<BST>,
        r: Box<BST>,
    }
}

如何编写函数以使其给出 BST 的最小元素？

我尝试了一些东西，我最近的尝试是：

fn min(&mut self) -> &mut BST{
        match self {
            BST::Nil => self,
            BST::Node{ l, ..} =>
                match **l {
                    BST::Nil => self,
                    BST::Node{..} => l.min(),
                }
        }
}

但是这不起作用，min 函数的目的是处理 BST 删除。

Answer 1

我认为解决这个问题的方法是将您的问题分解为更简单的步骤。 IE。你一次只能做一个，而不是一次做两个匹配，这样它也可以编译：

pub enum BST {
    Nil,
    Node { k: i32, l: Box<BST>, r: Box<BST> },
}

impl BST {
    fn min(&mut self) -> &mut BST {
        match self {
            BST::Nil => self,
            BST::Node { l, .. } => l.min(),
        }
    }
}

更新： 实际上，@Kevin Reid 注意到这改变了代码的语义，因为 OP 中的第二个匹配返回 self 而不是 l.

在我看来，这会使函数不一致，因为您要么想要最小元素（实际上总是 Nil 或它之前的 Node，这会使 self在外层匹配无效，应该用panic!代替）。

但是，如果你想在最小元素（即 Nil）之前获得 Node，你应该绕过这种特殊情况，如果调用则返回 Nil在 Nil 上。在我看来，这可以通过重构 BST 类型来最好地反映在类型系统中，如下所示。这里，min_node returns 始终是 l 中具有“nil”（即 None）的“节点”，但是，用户只能创建“节点”：

#[derive(Debug)]
pub struct BstNode {
    k: i32,
    l: Option<Box<BstNode>>,
    r: Option<Box<BstNode>>,
}

impl BstNode {
    fn min_node(&mut self) -> &mut BstNode {
        if let Some(ref mut l) = self.l {
            l.min_node()
        } else {
            self
        }
    }
}

Answer 2

编写一个接受可变借用并且 returns 的函数是非常有限制的；粗略地说，任何你return——通过匹配或函数调用——都永远不会停止在那个范围内被借用，即使你实际上没有return它，这对你的函数来说是个问题，因为你想检查树，然后可能 return self 而不是 self 的一个组件。我尝试了几种可能性并提出了编译器接受的这个版本：

impl BST {
    fn min(&mut self) -> &mut BST {
        match self {
            BST::Nil => self,
            BST::Node { l, .. } if matches!(**l, BST::Nil) => self,
            BST::Node { l, .. } => l.min(),
        }
    }
}

我认为使这个借用检查器友好的关键因素是对于两种 Node 可能性有两个完全独立的匹配臂（因此是独立的模式）：在第二个臂中，l 是临时的，在第三个分支中，l 被 returned（由 .min() 修改），但这两种情况对 l 有单独的绑定，因此他们可以有不同的生命周期。

（在 match guard, but we can't actually write a single pattern because of the Box; if box_patterns 中写 matches! 有点傻，然后我们就可以写一个像 BST::Node { l: box BST::Nil, .. } 这样的单一模式了。）

如何获得最小 BST 元素？

How to get minimum BST element?

rust

binary-search-tree