我的Rust红黑树插入代码为何出现无限递归？如何解决？

问题根源 #

你遇到的不是insert函数的无限递归，而是Debug trait递归打印循环引用导致的栈溢出。当你给新节点设置parent后，节点和父节点之间形成了双向引用：父节点的left/right指向子节点，子节点的parent指向父节点。使用println!("{:?}", rb_tree)时，Debug会递归遍历每个节点的所有字段，包括parent，而父节点又会遍历它的left/right，如此循环往复，最终导致栈溢出，表现为类似"无限递归"的崩溃。

验证逻辑正确性 #

你可以注释掉最后的println!("{:?}", rb_tree);，保留node.parent = Some(parent.clone());，程序会正常运行，这说明插入逻辑本身是正确的，问题完全出在打印环节。

解决方法 #

方法1：自定义Debug实现，打破循环打印 #

为Node手动实现Debug trait，跳过parent字段的打印，或者只打印父节点的value而非整个节点：

use std::fmt;

impl fmt::Debug for Node {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Node")
            .field("value", &self.value)
            .field("left", &self.left)
            .field("right", &self.right)
            // 跳过parent字段避免循环，也可以改为显示父节点值：
            // .field("parent", &self.parent.as_ref().map(|p| p.borrow().value))
            .finish()
    }
}

方法2：用Weak引用存储parent（更规范的双向引用方案） #

在红黑树这类需要双向引用的结构中，用Rc存储子节点、Weak存储父节点是更合理的选择——Weak不会增加引用计数，既避免了循环引用导致的内存泄漏，也能自然避免Debug打印的循环问题：

use std::rc::{Rc, Weak};
use std::cell::RefCell;

type StrongLink = Option<Rc<RefCell<Node>>>;
type WeakLink = Option<Weak<RefCell<Node>>>;

#[derive(Debug)]
struct Node {
    value: u32,
    parent: WeakLink,
    left: StrongLink,
    right: StrongLink,
}

impl Node {
    fn new(value: u32) -> Self {
        Self {
            value,
            parent: None,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, parent: &Rc<RefCell<Node>>, mut node: Node) {
        if self.value <= node.value {
            match &self.right {
                Some(parent_node) => {
                    parent_node.borrow_mut().insert(parent_node, node);
                }
                None => {
                    node.parent = Some(Rc::downgrade(parent));
                    self.right = Some(Rc::new(RefCell::new(node)));
                }
            }
        } else {
            match &self.left {
                Some(parent_node) => {
                    parent_node.borrow_mut().insert(parent_node, node);
                }
                None => {
                    node.parent = Some(Rc::downgrade(parent));
                    self.left = Some(Rc::new(RefCell::new(node)));
                }
            }
        }
    }
}

关于RefCell改Box的问题 #

Box是独占所有权的智能指针，无法处理红黑树中父节点与子节点的双向引用场景——因为子节点需要引用父节点，父节点也需要引用子节点，而Box只能有一个所有者。因此必须使用Rc（共享所有权）+RefCell（内部可变性）的组合，或者上面提到的Rc+Weak组合来实现双向引用。

内容的提问来源于stack exchange，提问作者Frank