Method insert

publication/code/chapter08/bst.rs:140–177

节点插入

(&mut self, key: T, val: U)

    // 节点插入
    fn insert(&mut self, key: T, val: U) {
        // 没数据直接插入
        if self.key.is_none() {
            self.key = Some(key);
            self.val = Some(val);
        } else {
            match &self.key {
                Some(k) => {
                    // 存在 key，更新 val
                    if key == *k {
                        self.val = Some(val);
                        return;
                    }

                    // 未找到相同 key，需要插入新节点
                    // 先找到需要插入的子树
                    let child = if key < *k {
                        &mut self.left
                    } else {
                        &mut self.right
                    };

                    // 根据节点递归下去，直到插入
                    match child {
                        Some(ref mut node) => {
                            node.insert(key, val);
                        },
                        None => {
                            let mut node = BST::new();
                            node.insert(key, val);
                            *child = Some(Box::new(node));
                        },
                    }
                },
                None => (),
            }
        }
    }

    // 节点查询
    fn contains(&self, key: &T) -> bool {