Ich kann Knoten nicht mehr als einmal ausleihen, während ich einen binären Suchbaum implementiere

Question

Ich versuche einen binären Suchbaum in Rust zu implementieren, und ich stoße auf Probleme beim Einfügen eines Elements. Was ist ein idiomatischer Weg, dies in Rust zu tun?

Hier ist meine Implementierung:

use std::cmp::Ordering; 

pub struct BinarySearchTree { 
    root: OptNode, 
    size: u32, 
} 

type OptNode = Option<Box<Node>>; 

struct Node { 
    key: i32, 
    left: OptNode, 
    right: OptNode, 
} 

impl BinarySearchTree { 
    pub fn new() -> Self { 
     BinarySearchTree { root: None, size: 0 } 
    } 

    pub fn is_empty(&self) -> bool { 
     self.size == 0 
    } 

    pub fn size(&self) -> u32 { 
     self.size 
    } 

    pub fn contains(&self, key: i32) -> bool { 
     let mut node = &self.root; 
     while let Some(ref boxed_node) = *node { 
      match key.cmp(&boxed_node.key) { 
       Ordering::Less => node = &boxed_node.left, 
       Ordering::Greater => node = &boxed_node.right, 
       Ordering::Equal => return true, 
      } 
     } 

     false 
    } 

    pub fn insert(&mut self, key: i32) { 
     let mut node = &mut self.root; 
     while let Some(ref mut boxed_node) = *node { 
      match key.cmp(&boxed_node.key) { 
       Ordering::Less => node = &mut boxed_node.left, 
       Ordering::Greater => node = &mut boxed_node.right, 
       Ordering::Equal => return, 
      } 
     } 

     *node = Some(Box::new(Node { key: key, left: None, right: None})); 
    } 
} 

Hier sind die Fehler, die ich bin immer:

error: cannot borrow `node.0` as mutable more than once at a time [E0499] 
      while let Some(ref mut boxed_node) = *node { 
           ^~~~~~~~~~~~~~~~~~ 
help: run `rustc --explain E0499` to see a detailed explanation 
note: previous borrow of `node.0` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `node.0` until the borrow ends 
      while let Some(ref mut boxed_node) = *node { 
           ^~~~~~~~~~~~~~~~~~ 
note: previous borrow ends here 
    pub fn insert(&mut self, key: i32) { 
    ... 
    } 
    ^
error: cannot assign to `node` because it is borrowed [E0506] 
          Ordering::Less => node = &mut boxed_node.left, 
                ^~~~~~~~~~~~~~~~~~~~~~~~~~~ 
note: borrow of `node` occurs here 
      while let Some(ref mut boxed_node) = *node { 
           ^~~~~~~~~~~~~~~~~~ 
error: cannot assign to `node` because it is borrowed [E0506] 
          Ordering::Greater => node = &mut boxed_node.right, 
                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
note: borrow of `node` occurs here 
      while let Some(ref mut boxed_node) = *node { 
           ^~~~~~~~~~~~~~~~~~ 
error: cannot assign to `*node` because it is borrowed [E0506] 
      *node = Some(Box::new(Node { key: key, left: None, right: None})); 
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
note: borrow of `*node` occurs here 
      while let Some(ref mut boxed_node) = *node { 
           ^~~~~~~~~~~~~~~~~~ 

Answer 1

Rust Compiler nicht anspruchsvoll genug ist, um mit dieser Situation zu umgehen (noch?). Rust sieht, dass Sie versuchen, den gleichen Wert mehrfach mehr als einmal zu borgen, da er ein wiederholtes veränderbares Borgen auf derselben Variablen in einer Schleife sieht. Das ist natürlich nicht das, was Sie zu tun versuchen, da Sie die Variable bei jeder Iteration neu zuweisen möchten, aber Rust unterstützt nicht die Zuweisung an eine Variable, die ausgeliehen wird.

Was wir stattdessen tun müssen, haben Zwischenvariablen, damit der Compiler die Ausleihen korrekt verfolgen kann. Wie schaffen wir eine unbestimmte Anzahl von Variablen? Mit Rekursion!

impl BinarySearchTree { 
    pub fn insert(&mut self, key: i32) { 
     fn insert_node(node: &mut OptNode, key: i32) { 
      if let Some(ref mut boxed_node) = *node { 
       match key.cmp(&boxed_node.key) { 
        Ordering::Less => insert_node(&mut boxed_node.left, key), 
        Ordering::Greater => insert_node(&mut boxed_node.right, key), 
        Ordering::Equal => return, 
       } 
      } else { 
       *node = Some(Box::new(Node { key: key, left: None, right: None})); 
      } 
     } 

     insert_node(&mut self.root, key) 
    } 
} 

Hinweis: Obwohl dieser Algorithmus Schwanz-rekursiv ist, rostet nicht optimieren dies in Endaufruf, so könnte es einen Stapelüberlauf in degenerierten Fällen verursachen.

Answer 2

Ohne Rekursion:

pub fn insert(&mut self, key: i32) { 
    let mut node = &mut self.root; 
    loop{ 
     node = match node.as_ref().map(|n| key.cmp(&n.key)) { 
      Some(Ordering::Less) => &mut {node}.as_mut().unwrap().left, 
      Some(Ordering::Equal) => return, 
      Some(Ordering::Greater) => &mut {node}.as_mut().unwrap().right, 
      None => { 
       *node = Some(Box::new(Node { key: key, left: None, right: None})); 
       return; 
      } 

     }; 
    } 
} 

Die unwrap() ist hier sicher.