You need to enable JavaScript to run this app. Rust实现BST节点删除:用孙节点替换待删子节点并保留子树
优惠活动
大模型
产品
解决方案
定价
更多

Rust实现BST节点删除:用孙节点替换待删子节点并保留子树

BST单孩子节点的删除实现(基于固定的Rc TreeNode结构)

核心逻辑

单孩子场景的本质是直接把待删节点的唯一子树,重连到待删节点的父节点对应指针位置,不需要对子树做任何修改或拷贝,待删节点本身脱离树结构后会被自动回收,全程完整保留原有子树结构。
具体执行步骤:

  • 定位待删除节点时,同步记录两个关键信息:待删节点的父节点引用、待删节点是父节点的左孩子还是右孩子
  • 取出待删节点的唯一非空子树,克隆对应的Rc引用(仅增加引用计数,不复制节点)
  • 修改父节点对应方向的指针,使其直接指向这个唯一子树,完成替换
  • 如果待删节点是根节点(无父节点),直接把树的根引用替换为该唯一子树即可

适配给定TreeNode的实际代码实现

首先我们默认已经有BST的基础持有结构,比如定义树的根入口为:

struct BST {
    root: Option<Rc<RefCell<TreeNode>>>,
}

首先需要一个辅助查找逻辑,定位待删值的节点时,同步返回父节点、当前待删节点、以及是否是父节点的左孩子:

// 查找目标值节点的辅助方法,返回(父节点引用, 待删节点, 是否为父节点左孩子)
fn find_target(
    root: &Option<Rc<RefCell<TreeNode>>>,
    val: i32,
) -> (Option<Rc<RefCell<TreeNode>>>, Rc<RefCell<TreeNode>>, bool) {
    let mut current = root.clone().expect("根节点不存在时不应调用查找");
    let mut parent: Option<Rc<RefCell<TreeNode>>> = None;
    let mut is_left = false;
    loop {
        let current_borrow = current.borrow();
        match val.cmp(&current_borrow.val) {
            std::cmp::Ordering::Equal => break,
            std::cmp::Ordering::Less => {
                parent = Some(current.clone());
                let next = current_borrow.left.clone().expect("目标值不存在");
                is_left = true;
                current = next;
            }
            std::cmp::Ordering::Greater => {
                parent = Some(current.clone());
                let next = current_borrow.right.clone().expect("目标值不存在");
                is_left = false;
                current = next;
            }
        }
    }
    (parent, current, is_left)
}

接下来是删除逻辑里处理单孩子分支的核心代码:

impl BST {
    pub fn delete(&mut self, val: i32) {
        if self.root.is_none() {
            return;
        }
        let (parent, target, is_left_child) = Self::find_target(&self.root, val);
        // 取出目标节点的左右子树,克隆引用后立刻释放不可变借用
        let (left, right) = {
            let target_borrow = target.borrow();
            (target_borrow.left.clone(), target_borrow.right.clone())
        };
        match (left, right) {
            // 单孩子场景:恰好一个子节点存在
            (Some(child), None) | (None, Some(child)) => {
                match parent {
                    // 待删节点是根节点,直接替换树的根
                    None => {
                        self.root = Some(child);
                    }
                    // 待删节点有父节点,重连父节点的指针
                    Some(p) => {
                        let mut p_borrow = p.borrow_mut();
                        if is_left_child {
                            p_borrow.left = Some(child);
                        } else {
                            p_borrow.right = Some(child);
                        }
                    }
                }
            }
            // 已掌握的无孩子场景
            (None, None) => {
                match parent {
                    None => self.root = None,
                    Some(p) => {
                        let mut p_borrow = p.borrow_mut();
                        if is_left_child {
                            p_borrow.left = None
                        } else {
                            p_borrow.right = None
                        }
                    }
                }
            }
            // 双孩子场景后续可单独实现,当前暂不展开
            (Some(_), Some(_)) => todo!("双孩子节点删除逻辑"),
        }
    }
}

实现注意事项

  • 必须在克隆待删节点的左右子树后,及时释放RefCell的不可变借用,否则后续修改父节点时触发borrow_mut会因运行时借用冲突直接panic
  • 不需要主动将待删节点的左右指针置空:待删节点脱离树结构后,如果没有其他强引用持有,引用计数会降到0自动回收,其挂接的子树因为已经被父节点的新指针持有引用,不会被误回收,结构完全保留
  • 根节点的边界场景必须单独处理:没有父节点时不需要修改其他节点的指针,直接替换树的根引用即可

内容的提问来源于stack exchange,提问作者Evgeni Nabokov

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.17 21:54:04