Method insert

publication/code/chapter08/rbtree.rs:303–341

数据插入

(&mut self, key: K, val: V)

    // 数据插入
    fn insert(&mut self, key: K, val: V) {
        unsafe {
            let mut parent = null_mut();
            let mut node = self.root;

            // 找到待插入节点及其父节点位置
            while !node.is_null() {
                parent = node;
                node = match (*node).key.cmp(&key) {
                    Less => (*node).right,
                    Equal => {
                        (*node).val = val;
                        return;
                    }
                    Greater => (*node).left,
                }
            }

            // 数据插入
            node = Box::into_raw(Box::new(RBNode::new(key, val)));

            // 更新节点关系
            if !parent.is_null() {
                if (*node).key < (*parent).key {
                    (*parent).left = node;
                } else {
                    (*parent).right = node;
                }
            } else {
                self.root = node;
            }

            // 更新父节点关系
            (*node).parent = parent;

            // 旋转，更新节点颜色
            insert_fixup(self, node);
        }
    }

    fn delete(&mut self, key: &K) {
        unsafe {