Rust文法練習(二分探索木)

# はじめに
本記事は 三重大学 計算研 Advent Calendar 2019 18日目です。
大学一年生の@scoopです。

Rustの文法の練習とデータ構造の勉強を兼ねてRustで二分探索木を書いてみました。

プログラミング初心者ですので、何か誤りや改善点等ございましたらご指摘いただけると幸いです。

# 実装について
## 概要
機能は作成、空判定、挿入、削除のみです。
`unsafe`な機能や`Rc<RefCell<T>>`は使用していません。
## 定義
`Ord`、`Default`を実装する型を要素に持てます。

```rust
#[derive(Debug)]
struct BST<T: Ord> {
    root: Option<Box<Node<T>>>,
}

#[derive(Debug)]
struct Node<T: Ord> {
    val: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}
```


## 作成
```rust
pub fn new() -> Self {
    BST { root: None }
}
```
## 空判定
```rust
pub fn is_empty(&self) -> bool {
    self.root.is_none()
}
```
## 挿入
```rust
pub fn insert(&mut self, val: T) {
    let mut root = self.root.take();
    self.insert_rec(&mut root, val);
    self.root = root;
}

fn insert_rec(&self, node: &mut Option<Box<Node<T>>>, val: T) {
    match node {
        Some(node) => {
            if node.val > val {
                self.insert_rec(&mut node.left, val);
            } else if node.val < val {
                self.insert_rec(&mut node.right, val);
            }
        }
        None => {
            *node = Some(Box::new(Node {
                val: val,
                left: None,
                right: None,
            }))
        }
    }
}
```

## 削除
あまり上手く実装できておらず、`remove_node()`、`remove_rec_min()`などは非常に汚くなってしまっています。

```rust
pub fn remove(&mut self, val: T) {
    let mut root = self.root.take();
    self.remove_rec(&mut root, val);
    self.root = root;
}

fn remove_rec(&self, node: &mut Option<Box<Node<T>>>, val: T) {
    if let Some(mut n) = node.take() {
        *node = match &val.cmp(&n.val) {
            Equal => {
                let mut temp = Some(n);
                self.remove_node(&mut temp);
                temp
            }
            Less => {
                self.remove_rec(&mut n.left, val);
                Some(n)
            }
            Greater => {
                self.remove_rec(&mut n.right, val);
                Some(n)
            }
        }
    }
}

fn remove_node(&self, node: &mut Option<Box<Node<T>>>) {
    if let Some(mut n) = node.take() {
        *node = match (n.left.take(), n.right.take()) {
            (None, None) => None,
            (x @ Some(_), None) | (None, x @ Some(_)) => x,
            (l @ Some(_), mut r @ Some(_)) => {
                n.left = l;
                std::mem::replace(&mut n.val, self.remove_rec_min(&mut r));
                n.right = r;
                Some(n)
            }
        }
    }
}

fn remove_rec_min(&self, node: &mut Option<Box<Node<T>>>) -> T {
    if let Some(mut n) = node.take() {
        let ans;
        *node = if n.left.is_some() {
            ans = self.remove_rec_min(&mut n.left);
            Some(n)
        } else {
            ans = std::mem::take(&mut n.val);
            let mut tn = Some(n);
            self.remove_node(&mut tn);
            tn
        };
        return ans;
    }
    unreachable!()
}
```
## 全体
```rust
#[derive(Debug)]
struct BST<T: Ord> {
    root: Option<Box<Node<T>>>,
}

#[derive(Debug)]
struct Node<T: Ord> {
    val: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T: Ord + Default> BST<T> {
    pub fn new() -> Self {
        BST { root: None }
    }

    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }

    pub fn insert(&mut self, val: T) {
        let mut root = self.root.take();
        self.insert_rec(&mut root, val);
        self.root = root;
    }

    fn insert_rec(&self, node: &mut Option<Box<Node<T>>>, val: T) {
        match node {
            Some(node) => {
                if node.val > val {
                    self.insert_rec(&mut node.left, val);
                } else if node.val < val {
                    self.insert_rec(&mut node.right, val);
                }
            }
            None => {
                *node = Some(Box::new(Node {
                    val: val,
                    left: None,
                    right: None,
                }))
            }
        }
    }

    pub fn remove(&mut self, val: T) {
        let mut root = self.root.take();
        self.remove_rec(&mut root, val);
        self.root = root;
    }

    fn remove_rec(&self, node: &mut Option<Box<Node<T>>>, val: T) {
        if let Some(mut n) = node.take() {
            *node = match &val.cmp(&n.val) {
                Equal => {
                    let mut temp = Some(n);
                    self.remove_node(&mut temp);
                    temp
                }
                Less => {
                    self.remove_rec(&mut n.left, val);
                    Some(n)
                }
                Greater => {
                    self.remove_rec(&mut n.right, val);
                    Some(n)
                }
            }
        }
    }

    fn remove_node(&self, node: &mut Option<Box<Node<T>>>) {
        if let Some(mut n) = node.take() {
            *node = match (n.left.take(), n.right.take()) {
                (None, None) => None,
                (x @ Some(_), None) | (None, x @ Some(_)) => x,
                (l @ Some(_), mut r @ Some(_)) => {
                    n.left = l;
                    std::mem::replace(&mut n.val, self.remove_rec_min(&mut r));
                    n.right = r;
                    Some(n)
                }
            }
        }
    }

    fn remove_rec_min(&self, node: &mut Option<Box<Node<T>>>) -> T {
        if let Some(mut n) = node.take() {
            let ans;
            *node = if n.left.is_some() {
                ans = self.remove_rec_min(&mut n.left);
                Some(n)
            } else {
                ans = std::mem::take(&mut n.val);
                let mut tn = Some(n);
                self.remove_node(&mut tn);
                tn
            };
            return ans;
        }
        unreachable!()
    }
}
```

# 今後の課題
- `remove_node()`、`remove_rec_min()`をきれいに書き直す。
- `Default`を実装していない型にも使えるようにする。
- 所属判定などの実装。