admin管理员组

文章数量:1352167

Explanation

I'm attempting to implement a binary search tree in Rust. The problem is in the insert method, where I have a &mut Box<Node<T>> called node_to_insert_at. To insert the given value, I travel down the binary search tree, replacing node_to_insert_at with it's left or right child depending on the value I'm trying to insert's (value from the function signature) relation to the current node. I'm attempting to store the path to the node that will be inserted in node_to_insert_at_path which I do by pushing node_to_insert_at into the stack (Vec) before I overwrite node_to_insert_at with it's left or right child.

The problem is in the last three lines of this code snippet:

if value < node_to_insert_at.value {
    if node_to_insert_at.left.is_some() {
        let temp = node_to_insert_at.left.as_mut().unwrap();
        node_to_insert_at_path.push(node_to_insert_at);
        node_to_insert_at = temp;

Rust says that the line node_to_insert_at_path.push(node_to_insert_at); creates a second mutable reference, which is illegal. However, I'm unsure how this could be the case, since on the line above it I am only creating a mutable reference to node_to_insert_at's left value.

Code in Full

For reference, this is what the Node struct looks like (Node is in the components file):

pub struct Node<T> {
    pub value: T,
    pub left: Option<Box< Node<T>>>,
    pub right: Option<Box< Node<T>>>
}

Here's the entire file looks like for reference:

use crate::components;
use std::vec::Vec;
use crate::components::Node;

pub struct BSTree<T>{
    vars: components::BSTVars<T>
}

impl<T> Default for BSTree<T>{
    fn default() -> Self {
        BSTree{vars: components::BSTVars{root: None, name: String::from("BSTree"), count: 0}}
    }
}

impl<T: Clone + PartialOrd> components::BSTMethods<T> for BSTree<T>{
    fn insert(&mut self, value: T){
        if self.vars.root.is_none(){
            self.vars.root = Option::Some(Box::new(Node {value, left: None, right: None}));
            return;
        }
        
        let mut node_to_insert_at = self.vars.root.as_mut().unwrap();
        let mut node_to_insert_at_path: Vec<&mut Box<Node<T>>> = Vec::new();

        let mut not_inserted = true;
        while not_inserted {
            if value < node_to_insert_at.value {
                if node_to_insert_at.left.is_some() {
                    let temp = node_to_insert_at.left.as_mut().unwrap();
                    node_to_insert_at_path.push(node_to_insert_at);
                    node_to_insert_at = temp;
                } else {
                    node_to_insert_at.left = Option::Some(Box::new(Node {value: value.clone(), left: None, right: None}));
                    not_inserted = false;
                }
            } else if value > node_to_insert_at.value {
                /*if node_to_insert_at.right.is_some() {
                    node_to_insert_at_path.push(node_to_insert_at);
                    node_to_insert_at = node_to_insert_at.right.as_mut().unwrap();
                } else {
                    node_to_insert_at.right = Option::Some(Box::new(Node{value: value.clone(), left: None, right: None}))
                }*/
            } else {
                node_to_insert_at.right = Option::Some(Box::new(Node{value: value.clone(), left: None, right: None}));
                not_inserted = false;
            }
        }
    }

    // impl continues...
}

Possible Explanations & Solutions

From what I gather from this question I might be performing a reborrow, which I think would invalidate node_to_insert_at because I'm mutably borrowing one of its member variables (please correct me on this if I'm wrong).

To fix this, the stack should be a list of immutable references, which I turn into mutable references as needed by dereferencing the immutable reference.

Is this explanation and solution correct, or is there something I missed?

本文标签： rustError When Mutably Borrowing a Value From a Struct That Has Been Mutably BorrowedStack Overflow