LoginSignup
2
0

More than 3 years have passed since last update.

@quercus491(Make犬)

Rustで二分木

Posted at

・Rustの練習で二分木の実装を行った。
最初は自分でデータ構造とか、ロジックとか考えてたけど、
ギブアップして「プログラミングコンテスト チャレンジブック 第２版」のp77〜78の
C++コードをRustで書き直すことにした。

全コードは以下。
https://github.com/FujiiNoritsugu/try_rust

間違ってるかもしれんし、バグもあると思うのでそのままコピペして使うのは危険。ダメ。ゼッタイ。

ノードの定義

・右と左の子の定義でコンパイル時にデータサイズがわからんと
コンパイルできんとrustcに怒られたので、Box型にノードの構造体をくるんだ。
また、子がない場合もあるのでさらにOption型でもくるんだ。

///
/// ノードの定義
/// 
pub struct Node{
    no:i32,
    right:Box<Option<Node>>,
    left:Box<Option<Node>>
}

・実装中に「Use of moved value」でしょっちゅう怒られたので、Copyトレイトを実装しようとした。するとフィールドの型がBoxではCopyトレイトは作れんとコンパイラにいわれたので
Cloneトレイトのみ実装、ノード構造の受け渡しはclone()メソッドでcloneを作って返すようにした。

impl Clone for Node {

    fn clone(&self) -> Self {
        Node {
            no: self.no,
            right: self.right.clone(),
            left: self.left.clone()
        }
    }

    fn clone_from(&mut self, source: &Self) {
        *self = source.clone();
    }
}

ノードの追加関数

・Optionからノードをとりだすのにunwrap()を使うと、ノードがない場合に実行時エラーになったのでmatch式をつかって場合分けした。コード全般にOptionがらみのmatch式を多用してる。
あと、Boxから値を取り出すときは前にアスタリスクをつけて取り出す。

///
/// 追加用の関数
/// 
pub fn insert(node:Box<Option<Node>>, x:i32)->Box<Option<Node>>{
    return match *node{
        None=>Box::new(Some(Node::new(x))),
        Some(v)=>{
            let mut target_node = v.clone();
            if x < target_node.no {
                target_node.left = insert(target_node.left, x);
            }else{
                target_node.right = insert(target_node.right, x);
            }
            Box::new(Some(target_node))
        }
    };
}

ノードの検索関数

・最初、追加用関数とまったくおんなじロジックで実装したが、
いざテストを書くときにテスト用のノードを作成後、おんなじノードに対して続けて
検索関数を適用すると「Use of moved value」がでてテストを続けて行えなくなった。ウンウン悩んだけど、単に関数のパラメータを参照の借用に変更すればよいだけだった。
match対象の「&**node」については「参照参照外し」→「Boxの値取り出し」→「再度参照」と理解してる。理解が間違ってるかもしれんがこうしないとコンパイラに怒られた。

///
/// 検索用の関数
/// 
pub fn find(node:&Box<Option<Node>>, x:i32)->bool{
    return match &**node{
        None=>false,
        Some(v)=>{
            if x == v.no{
                true
            }else if x < v.no{
                find(&v.left, x)
            }else{
                find(&v.right, x)
            }
        }
    }
}

ノードの削除関数

・「プログラミングコンテストチャレンジブック」にてノードの削除ロジックは以下となっている。
1.「削除したいノードが左の子を持っていない場合、右の子を持ってくる。」
2.「削除したいノードの左の子が右の子を持っていなければ、左の子を持ってくる。」
3.「どちらでもなければ、左の子以下で最も大きいノードを削除したいノードの場所に持ってくる。」
これの3番目のロジックでC++の実装では付替元ノードの削除をポインタの削除を使用して実装している。これをRustでどのように実装すればよいのか結局わからなかったので、
削除関数を再帰的に使用して実装したが、これでよいのかわからない。
また、この付替え処理でも「Use of moved value」でガンガン怒られたので
Optionの「as_mut()」と「map(|x|〜)」を併用して回避。

以下3番目のロジックの実装

///
/// 左の子以下で最も大きいノードを削除したいノードの場所に持ってくる
/// 
fn search_return_node(target_node:Node, left_node:Node)->Box<Option<Node>>{
    // 左の子以下で最も大きいノードを探す
    let mut max_node = Some(left_node.clone());
    loop {

        match max_node.as_ref() {
            Some(v)=>{
                let right_right_node = &*(v.right);
                match right_right_node{
                    Some(v2)=>{
                        max_node = Some(v2.clone());
                    },
                    None=>{
                        break;
                    }
                }
            },
            None=>{
                break;
            }
        }
    }

    let result3 = max_node.as_mut().map(|x|{
        // この時点でtarget_nodeからmax_nodeを削除する
        let temp = Box::new(Some(target_node));
        let removed_node = (*remove(temp, x.no)).unwrap();

        x.left = make_clone(*(removed_node.left));
        x.right = make_clone(*(removed_node.right));
        (*x).clone()
    });

    Box::new(result3)

}

テストケース

・テストケースは「プログラミングコンテストチャレンジブック」P77の「図B:削除の例」のケースとこの例でさらに付替え元ノード(11番)が左の子を持っているケースの２ケースのみ作成しテストがパスしていることを確認。
多分ケースを増やすとガンガンバグがでてくると思う。

#[cfg(test)]
mod tests{
    use super::*;

    #[test]
    fn check_remove(){
        let mut checked_tree = insert(Box::new(None),7);
        checked_tree = insert(checked_tree, 2);
        checked_tree = insert(checked_tree, 1);
        checked_tree = insert(checked_tree, 5);
        checked_tree = insert(checked_tree, 4);
        checked_tree = insert(checked_tree, 15);
        checked_tree = insert(checked_tree, 10);
        checked_tree = insert(checked_tree, 8);
        checked_tree = insert(checked_tree, 11);
        checked_tree = insert(checked_tree, 17);
        checked_tree = insert(checked_tree, 16);
        checked_tree = insert(checked_tree, 19);
        checked_tree = remove(checked_tree, 15);

        // check 15 removed, 11, 10 exists
        assert_eq!(false, find(&checked_tree, 15));
        assert_eq!(true, find(&checked_tree, 11));
        assert_eq!(true, find(&checked_tree, 10));

        let right = get_right_node(&checked_tree);
        let right_left = get_left_node(&right);
        let right_left_right = get_right_node(&right_left);

        // check right no is 11
        assert_eq!(11, right.unwrap().no);
        // check right_left no is 10
        assert_eq!(10, right_left.unwrap().no);
        // check right_left_right is None
        assert!(right_left_right.is_none());
    }


    #[test]
    fn check_move_left_node(){
        let mut checked_tree = insert(Box::new(None),7);
        checked_tree = insert(checked_tree, 2);
        checked_tree = insert(checked_tree, 1);
        checked_tree = insert(checked_tree, 5);
        checked_tree = insert(checked_tree, 4);
        checked_tree = insert(checked_tree, 15);
        checked_tree = insert(checked_tree, 10);
        checked_tree = insert(checked_tree, 8);
        checked_tree = insert(checked_tree, 14);
        checked_tree = insert(checked_tree, 13);
        checked_tree = insert(checked_tree, 17);
        checked_tree = insert(checked_tree, 16);
        checked_tree = insert(checked_tree, 19);
        checked_tree = remove(checked_tree, 15);

        // check 15 removed, 13, 14 exists
        assert_eq!(false, find(&checked_tree, 15));
        assert_eq!(true, find(&checked_tree, 14));
        assert_eq!(true, find(&checked_tree, 13));

        let right = get_right_node(&checked_tree);
        let right_left = get_left_node(&right);
        let right_left_right = get_right_node(&right_left);

        // check right no is 14
        assert_eq!(14, right.unwrap().no);
        // check right_left no is 10
        assert_eq!(10, right_left.unwrap().no);
        // check right_left_right is 13
        assert_eq!(13, right_left_right.unwrap().no);
    }

}

モジュール化

・最初、全部の実装を「main.rs」に書いていたが、「実践Rust入門」のクイックツアーと「THE RUST PROGRAMMING LANGUAGE」の最後の章を元に以下の手順でモジュール化

1.binary_tree.rsを作成して二分木のコードを移動し、
構造体と主要関数にpubを付ける
2.lib.rsを作成し、「pub mod binary_tree.rs;」を追加
3.main.rsをbin/main.rsに移動し「use (プロジェクト名)::binary_tree::*;」を追加
※プロジェクト名はCargo.tomlに定義されているもの

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0