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(¤t_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
相关产品推荐
相关产品推荐

