Method insert

publication/code/chapter08/avl.rs:215–272

插入节点

(&mut self, key: T)

    // 插入节点
    fn insert(&mut self, key: T) -> (bool, bool) {
        let ret = match self {
            // 没有节点，直接插入
            Null => {
                let node = AvlNode {
                    key: key,
                    left: Null,
                    right: Null,
                    bfactor: 0,
                };
                *self = Tree(Box::new(node));
                (true, true)
            },
            // 比较节点值，再判断该从哪边插入
            Tree(ref mut node) => match node.key.cmp(&key) {
                Equal => (false, false), // 相等，无需插入
                Less => {
                    // 比节点数据大，插入右边
                    let (inserted, deepened) = node.right.insert(key);

                    // inserted 表示是否插入
                    // deepened 表示是否加深
                    if deepened {
                        let ret = match node.bfactor {
                            -1 => (inserted, false),
                             0 => (inserted, true),
                             1 => (inserted, false),
                             _ => unreachable!(),
                        };
                        node.bfactor += 1;
                        ret
                    } else {
                        (inserted, deepened)
                    }
                },
                Greater => {
                    // 比节点数据小，插入左边
                    let (inserted, deepened) = node.left.insert(key);

                    if deepened {
                        let ret = match node.bfactor {
                            -1 => (inserted, false),
                             0 => (inserted, true),
                             1 => (inserted, false),
                             _ => unreachable!(),
                        };
                        node.bfactor -= 1;
                        ret
                    } else {
                        (inserted, deepened)
                    }
                },
            },
        };
        self.rebalance();

        ret
    }