What's causing infinite recursion in my Rust Red-Black Tree insertion code?

Question

How do I stop infinite recursion on the following code? I am having a problem creating the parent link to a node being inserted. If you remove the 2 lines

node.parent = Some(parent.clone()); x2

The code works but with that line, it goes into an infinite recursion

use std::rc::Rc;
use std::cell::RefCell;

type Link = Option<Rc<RefCell<Node>>>;

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

impl Node {
    fn new(value: u32) -> Self {
        Self {
            value: 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(ref parent_node) => {
                    parent_node.borrow_mut().insert(parent_node, node);
                }
                None => {
                    node.parent = Some(parent.clone());
                    self.right = Some(Rc::new(RefCell::new(node)));
                }
            }
        } else {
            match self.left {
                Some(ref parent_node) => {
                    parent_node.borrow_mut().insert(parent_node, node);
                }
                None => {
                    node.parent = Some(parent.clone());
                    self.left = Some(Rc::new(RefCell::new(node)));
                }
            }
        }
    }

}

#[derive(Debug)]
struct RedBlackTree {
    root: Link,
}

impl RedBlackTree {
    fn new() -> Self {
        Self {
            root: None,
        }
    }

    fn insert_node(&mut self, node: Node) {
        match self.root {
            Some(ref root_node) => {
                root_node.borrow_mut().insert(root_node, node);
            }
            None => {
                self.root = Some(Rc::new(RefCell::new(node)));
            }
        }
    }
}

fn main() {
    let mut rb_tree = RedBlackTree::new();
    let node1 = Node::new(3);
    let node2 = Node::new(5);
    rb_tree.insert_node(node1);
    rb_tree.insert_node(node2);
    println!("{:?}", rb_tree);

}

I tried converting the RefCell to Box but it just throws too many errors that my limited rust knowledge cannot debug

You have a memory leak because you have a `Rc` cycle. – Chayim Friedman Jun 05 '23 at 03:56 — Chayim Friedman, Jun 05 '23 at 03:56

score 1 · Answer 1 · answered Jun 05 '23 at 01:06

I checked your code, according to my knowledge, your bug is from insert method of the Node struct. As I look, you are passing the parent_node reference to the recursive insert calls. That's incorrect. Can you try with passing the parent reference, like below?

parent_node.borrow_mut().insert(parent_node, node);

to

parent_node.borrow_mut().insert(parent, node);

Let me provide my updated insert function code below.

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);
      }
      None => {
        node.parent = Some(Rc::clone(parent));
        self.right = Some(Rc::new(RefCell::new(node)));
      }
    }
  } else {
    match &self.left {
      Some(parent_node) => {
        parent_node.borrow_mut().insert(parent, node);
      }
      None => {
        node.parent = Some(Rc::clone(parent));
        self.left = Some(Rc::new(RefCell::new(node)));
      }
    }
  }
}

Please let me know if this would help you.

Thanks, I am far from my machine right now but will try it out. I knew it had something to do with references which is the other confusing part of rust — Frank, Jun 05 '23 at 13:57
Hello, I checked it out and it was still recursing as before. However, it helped me search for the right question and found that I have to implement debug that only traverses in the right order. https://stackoverflow.com/questions/74271963/debug-print-is-causing-stack-overflow-for-a-struct-with-field-type-stdrcrc — Frank, Jun 05 '23 at 22:18

What's causing infinite recursion in my Rust Red-Black Tree insertion code?

1 Answers1