英文:
What's causing infinite recursion in my Rust Red-Black Tree insertion code?
问题
Here is the translated part of your code:
如何停止以下代码的无限递归？我在创建要插入的节点的父链接时遇到问题。如果删除这两行：
node.parent = Some(parent.clone()); x2
代码可以正常工作，但加上这行会导致无限递归
```rust
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);
}
Hope this helps! If you have any more questions or need further assistance, feel free to ask.
英文:
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
答案1
得分: 1
我检查了你的代码，根据我的了解，你的bug来自Node结构体的insert方法。据我观察，你正在将parent_node的引用传递给递归的insert调用，这是不正确的。你可以尝试将parent的引用传递，像下面这样：
parent_node.borrow_mut().insert(parent, node);
让我提供我的更新后的insert函数代码如下：
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)));
}
}
}
}
请让我知道这是否对你有帮助。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论