バイナリ検索ツリーを実装する際に、ノードを複数回変更することはできません。

Question

Rustにバイナリ検索ツリーを実装しようとしていますが、要素の挿入に問題があります。 Rustでこれを行う慣用方法は何ですか？

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})); 
    } 
} 

は、ここで私が取得していますエラーです：

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はループ内の同じ変数に対して繰り返し可変的なボローを見るので、同じ値を複数回可変的に借りようとしていることが分かります。もちろん、これはあなたがやろうとしていることではありません。各反復で変数を再割り当てしたいからですが、Rustは借用されている変数に代入することをサポートしていません。

コンパイラが借用を正しく追跡できるように、中間変数が必要です。不確実な量の変数を作成するにはどうすればよいですか？再帰で！

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) 
    } 
} 

注：このアルゴリズムは末尾再帰ではあるが、それは縮退例でスタックオーバーフローを引き起こす可能性がありますので、錆は、末尾再帰にこれを最適化しません。再帰なし

Answer 2

：

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; 
      } 

     }; 
    } 
} 

unwrap()はここに安全です。