Rust-二分探索木

binary_search_tree.rs

use std::boxed::Box;

#[derive(Debug)]
pub struct Node
{
    data: isize,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node
{
    pub fn new(num: isize) -> Self
    {
        Self {
            data: num,
            left: None,
            right: None,
        }
    }

    pub fn insert(&mut self, num: isize)
    {
        if &self.data > &num {                  //Left Node
            if let Some(left_node) = &mut self.left {
                left_node.insert(num);
            } else {
                let node = Self::new(num);
                self.left = Some(Box::new(node));
            }
        } else if &self.data < &num {           //Right Node
            if let Some(right_node) = &mut self.right {
                right_node.insert(num);
            } else {
                let node = Self::new(num);
                self.right = Some(Box::new(node));
            }
        } else {}                               //既にある場合なにもしない
    }

    pub fn search(&self, num: isize) -> bool
    {
        if &self.data > &num {                  //Left Node
            if let Some(left_node) = &self.left {
                left_node.search(num)
            } else { false }
        } else if &self.data < &num {           //Right Node
            if let Some(right_node) = &self.right {
                right_node.search(num)
            } else { false }
        } else { true }
    }

    pub fn delete(&mut self, num: isize) -> Option<isize>
    {
        let mut log = vec![];

        if &self.data > &num {                  //Left Node
            if let Some(left_node) = &mut self.left {
                if left_node.data == num {      // 一致した場合削除処理に進む
                    left_node.delete_impl(&mut log);
                    self.left = None;           //削除
                    for n in log.iter() {
                        self.insert(*n);
                    };
                    return Some(num);
                }
                left_node.delete(num)           //子ノードを探索
            } else { None }
        } else if &self.data < &num {          //Right Node
            if let Some(right_node) = &mut self.right {
                if right_node.data == num {
                    right_node.delete_impl(&mut log);
                    self.right = None;
                    for n in log.iter() {
                        self.insert(*n);
                    };
                    return Some(num);
                }
                right_node.delete(num)
            } else { None }
        } else {
            self.delete_impl(&mut log);
            self.left = None;
            self.right = None;
            for n in log.iter() {
                self.insert(*n);
            };
            return Some(num);
        }
    }

    fn delete_impl(&self, log: &mut Vec<isize>)
    {
        //削除されるノード以下を全探索して、データをリストに保存する
        //Left Node
        if let Some(left_node) = &self.left {
            log.push(left_node.data);
            left_node.delete_impl(log);
        };

        //Right Node
        if let Some(right_node) = &self.right {
            log.push(right_node.data);
            right_node.delete_impl(log);
        };
    }
}