如何在不安全的情况下从二叉搜索树中移除一个节点?

Question

我正在尝试在Rust中实现二叉搜索树。remove方法使用了不安全的Rust代码，我想编写等价的安全Rust代码。

我遇到了问题，因为self是一个可变引用，当使用match语句解构它时，编译器会抱怨，因为我不能重新分配给它，因为它已经被借用了。

use std::cmp::Ordering;
#[derive(Debug)]
struct Node<T: Ord> {
key: T,
left: Tree<T>,
right: Tree<T>,
}
#[derive(Debug)]
struct Tree<T: Ord>(Option<Box<Node<T>>>);
#[derive(Debug)]
pub struct BinarySearchTree<T: Ord> {
root: Tree<T>,
}
impl<T: Ord> Node<T> {
fn new(value: T) -> Self {
Node {
key: value,
left: Tree(None),
right: Tree(None),
}
}
}
impl<T: Ord> Tree<T> {
fn add(&mut self, value: T) {
let mut current = self;
while let Some(ref mut node) = current.0 {
match node.key.cmp(&value) {
Ordering::Less => current = &mut node.right,
Ordering::Greater => current = &mut node.left,
Ordering::Equal => current = &mut node.right,
}
}
current.0 = Some(Box::new(Node::new(value)));
}
fn successor(&self, value: &T) -> Option<&T> {
let mut current = self.0.as_ref();
let mut successor = None;
while current.is_some() {
let node = current.unwrap();
if *value < node.key {
successor = current;
current = node.left.0.as_ref();
} else {
current = node.right.0.as_ref();
}
}
successor.map(|node| &node.key)
}
fn extract_min(&mut self) -> Option<T> {
let mut node = None;
if self.0.is_some() {
let mut current = self;
while current.0.as_ref().unwrap().left.0.is_some() {
current = &mut current.0.as_mut().unwrap().left;
}
let temp = current.0.take().unwrap();
node = Some(temp.key);
current.0 = temp.right.0;
}
node
}
fn extract_max(&mut self) -> Option<T> {
let mut node = None;
if self.0.is_some() {
let mut current = self;
while current.0.as_ref().unwrap().right.0.is_some() {
current = &mut current.0.as_mut().unwrap().right;
}
let temp = current.0.take().unwrap();
node = Some(temp.key);
current.0 = temp.left.0;
}
node
}
fn remove(&mut self, value: &T) {
let mut current: *mut Tree<T> = self;
unsafe {
while let Some(ref mut node) = (*current).0 {
match node.key.cmp(value) {
Ordering::Less => current = &mut node.right,
Ordering::Greater => current = &mut node.left,
Ordering::Equal => match (node.left.0.as_mut(), node.right.0.as_mut()) {
(None, None) => (*current).0 = None,
(Some(_), None) => (*current).0 = node.left.0.take(),
(None, Some(_)) => (*current).0 = node.right.0.take(),
(Some(_), Some(_)) => {
(*current).0.as_mut().unwrap().key = node.right.extract_min().unwrap();
}
},
}
}
}
}
}
impl<T: Ord> BinarySearchTree<T> {
pub fn new() -> Self {
BinarySearchTree { root: Tree(None) }
}
pub fn add(&mut self, value: T) {
self.root.add(value);
}
pub fn remove(&mut self, value: &T) {
self.root.remove(value);
}
pub fn successor(&self, value: &T) -> Option<&T> {
self.root.successor(value)
}
}

Answer 1

这个问题是由steffahn在users.rust-lang.org上解决的:

fn remove(&mut self, value: &T) {
let mut current = self;
while let Some(ref mut node) = current.0 {
match node.key.cmp(value) {
Ordering::Less => current = &mut current.0.as_mut().unwrap().right,
Ordering::Greater => current = &mut current.0.as_mut().unwrap().left,
Ordering::Equal => match (node.left.0.as_mut(), node.right.0.as_mut()) {
(None, None) => current.0 = None,
(Some(_), None) => current.0 = node.left.0.take(),
(None, Some(_)) => current.0 = node.right.0.take(),
(Some(_), Some(_)) => {
current.0.as_mut().unwrap().key = node.right.extract_min().unwrap();
}
}
}
}
}

根据作者，

最显著的变化是在Less和Greater分支上重新追踪到node的路径(使用unwrap等)。对于编译器优化，这可能是零开销。