はじめに
本記事は 三重大学 計算研 Advent Calendar 2019 18日目です。
大学一年生の@scoopです。
Rustの文法の練習とデータ構造の勉強を兼ねてRustで二分探索木を書いてみました。
プログラミング初心者ですので、何か誤りや改善点等ございましたらご指摘いただけると幸いです。
実装について
概要
機能は作成、空判定、挿入、削除のみです。
unsafeな機能やRc<RefCell<T>>は使用していません。
定義
Ord、Defaultを実装する型を要素に持てます。
#[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>>>,
}
作成
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,
}))
}
}
}
削除
あまり上手く実装できておらず、remove_node()、remove_rec_min()などは非常に汚くなってしまっています。
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!()
}
全体
#[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を実装していない型にも使えるようにする。 - 所属判定などの実装。