Rust: реализовать дерево AVL и ошибка: поток 'main' запаниковал на 'уже заимствованном: BorrowMutError'

Ручная реализация структур данных, таких как связанный список, дерево, граф, не является задачей для новичков из-за правил безопасности памяти в языке. Я предлагаю вам прочитать руководство Слишком много связанных списков, в котором обсуждает, как правильно реализовать безопасные и небезопасные связанные списки в Rust.

Также прочтите о затенении имен. Ваша ошибка в том, что внутри цикла вы пытаетесь заимствовать изменяемое что-то, что уже заимствовано как неизменное.

let node_key = &current_node.borrow().key; // Borrow as immutable

match node_key.cmp(&value) {
    Ordering::Less => { let current_tree = &mut current_node.borrow_mut().right; }, // Create a binding which will be immediately deleted and borrow as mutable.

И я рекомендую вам прочитать книгу о ржавчине, чтобы узнать о ржавчине.

Сначала позвольте нам исправить ваш алгоритм. Следующие строки неверны:

let current_tree = &mut current_node.borrow_mut().right;
...
let current_tree = &mut current_node.borrow_mut().left;

Оба не переназначают значение current_tree, а создают новое (неиспользуемое) (@Inline называет это затенением имени). Удалите let и сделайте current_tree mut.

Теперь мы получаем ошибку компилятора temporary value dropped while borrowed. Вероятно, сообщение об ошибке компилятора ввело вас в заблуждение. Он говорит вам использовать let для увеличения времени жизни, и это было бы правильно, если бы вы использовали результат в той же области, но никакая let не может увеличить время жизни за пределами области действия.

Проблема в том, что вы не можете передать ссылку на значение, принадлежащее циклу (как current_node.borrow_mut.right). Поэтому было бы лучше использовать current_tree как принадлежащую переменную. К сожалению, это означает, что многие хитрые приемы в вашем коде больше не будут работать.

Другая проблема в коде - проблема множественного заимствования (об этом говорится в вашем исходном предупреждении во время выполнения). Вы не можете вызывать borrow() и borrow_mut() на одном и том же RefCell без паники (это цель RefCell).

Итак, обнаружив проблемы в вашем коде, я заинтересовался, как я буду писать код. И теперь, когда он написан, я подумал, что было бы справедливо поделиться им: fn insert (& mut self, value: T) -> bool {if let None = self.root {self.root = TreeSet :: root (value) ; вернуть истину; } let mut current_tree = self.root.clone ();

  while let Some(current_node) = current_tree {
    let mut borrowed_node = current_node.borrow_mut();
    match borrowed_node.key.cmp(&value) {
      Ordering::Less => {
        if let Some(next_node) = &borrowed_node.right {
          current_tree = Some(next_node.clone());
        } else {
          borrowed_node.right = current_node.child(value);
          return true;
        }
      }
      Ordering::Equal => {
        return false;
      }
      Ordering::Greater => {
        if let Some(next_node) = &borrowed_node.left {
          current_tree = Some(next_node.clone());
        } else {
          borrowed_node.left = current_node.child(value);
          return true;
        }
      }
    };
  }
  true
}

//...

trait NewChild<T: Ord> {
  fn child(&self, value: T) -> AVLTree<T>;
}
impl<T: Ord> NewChild<T> for Rc<RefCell<TreeNode<T>>> {
  fn child(&self, value: T) -> AVLTree<T> {
    Some(Rc::new(RefCell::new(TreeNode {
      key: value,
      left: None,
      right: None,
      parent: Some(self.clone()),
    })))
  }
}

Чтобы сделать эту компиляцию, нужно написать два метода child(value:T) и root(value:T).