Method delete

publication/code/chapter08/rbtree.rs:343–471

(&mut self, key: &K)

    }

    fn delete(&mut self, key: &K) {
        unsafe {
            let mut parent = null_mut();
            let mut node = self.root;

            // 找到待删除节点
            while !node.is_null() {
                node = match (*node).key.cmp(key) {
                    Less => {
                        parent = node;
                        (*node).right
                    }
                    Equal => break,
                    Greater => {
                        parent = node;
                        (*node).left
                    }
                };
            }

            if node.is_null() {
                return;
            }

            let cl = (*node).left;
            let cr = (*node).right;
            let mut deleted_color;

            // 删除又分为多种情况
            if cl.is_null() {
                replace_node(self, parent, node, cr);

                /* 左右子节点均为空，n 随便着色
                 * (n could be either color here)
                 *
                 *     (n)             NULL
                 *    /   \    -->
                 *  NULL  NULL
                 */
                if cr.is_null() {
                    deleted_color = (*node).color;
                } else {
                    /*
                     * 左子节点空，右子节点不空
                     *     N             Cr
                     *    / \    -->    /  \
                     *  NULL cr       NULL NULL
                     */
                    (*cr).parent = parent;
                    (*cr).color = Color::Black;
                    deleted_color = Color::Red;
                }
            } else if cr.is_null() {
                /*
                 * 左子节点不空，右子节点空
                 *     N             Cl
                 *    / \    -->    /  \
                 *  cl  NULL      NULL NULL