内存数据库内核开发 工作日志（内存索引实现原理）（附红黑树实现清晰完整直接可编译运行代码）(十)

//Rbtree_Delete.cpp by konyel
#include "Rbtree.h"



void rb_tree::__delete_case1(struct rb_node* n){
    if (n->parent != NULL)
    __delete_case2(n);
}

void rb_tree::__delete_case2(struct rb_node* n)
{
    struct rb_node* s = __sibling(n);
    if (s->color == RB_RED) {
        n->parent->color = RB_RED;
        s->color = RB_BLACK;
        if (n == n->parent->left)
        __rotate_left(n->parent);
        else
        __rotate_right(n->parent);
    }
    __delete_case3(n);
}

void rb_tree::__delete_case3(struct rb_node* n){
    struct rb_node* s = __sibling(n);
    if ((n->parent->color == RB_BLACK) &&
    (s->color == RB_BLACK) &&
    (s->left==NULL||s->left->color == RB_BLACK) &&
    (s->right==NULL||s->right->color == RB_BLACK)) {
        s->color = RB_RED;
        __delete_case1(n->parent);
    } else
    __delete_case4(n);
}

void rb_tree::__delete_case4(struct rb_node* n){
    struct rb_node* s = __sibling(n);
    if ((n->parent->color == RB_RED) &&
    (s->color == RB_BLACK) &&
    (s->left==NULL||s->left->color == RB_BLACK) &&
    (s->right==NULL||s->right->color == RB_BLACK)) {
            s->color = RB_RED;
            n->parent->color = RB_BLACK;
    } else
    __delete_case5(n);
}

void rb_tree::__delete_case5(struct rb_node* n){
    struct rb_node* s = __sibling(n);
    if (s->color == RB_BLACK) {/* this if statement is trivial,
        due to Case 2 (even though Case two changed the sibling to a sibling's child,
        the sibling's child can't be red, since no red parent can have a red child). */
        // the following statements just force the red to be on the left of the left of the parent,
        // or right of the right, so case six will rotate correctly.
        if ((n == n->parent->left) &&
        (s->right->color == RB_BLACK) &&
        (s->left->color == RB_RED)) { // this last test is trivial too due to cases 2-4.
            s->color = RB_RED;
            s->left->color = RB_BLACK;
            __rotate_right(s);
            } else if ((n == n->parent->right) &&
            (s->left->color == RB_BLACK) &&
            (s->right->color == RB_RED)) {// this last test is trivial too due to cases 2-4.
                s->color = RB_RED;
                s->right->color = RB_BLACK;
                __rotate_left(s);
            }
    }
    __delete_case6(n);
}

void rb_tree::__delete_case6(struct rb_node* n){
    struct rb_node* s = __sibling(n);
    s->color = n->parent->color;
    n->parent->color = RB_BLACK;
    if (n == n->parent->left) {
        s->right->color = RB_BLACK;
        __rotate_left(n->parent);
    } else {
        s->left->color = RB_BLACK;
        __rotate_right(n->parent);
    }
}
rb_node* rb_tree::rb_delete(void* key){
    //两边都不是叶子节点
    struct rb_node* min_node;
    struct rb_node* fnode=root;
    int ret=0;
    while(ret=__rb_cmpkey(fnode->key,key)){
         if(__is_leaf(fnode)){
           return NULL;
         }
         if(ret>0)
             fnode=fnode->right;
         else
             fnode=fnode->left;
    }
    if(fnode->right!=NULL){
          min_node=fnode->right;
          while(min_node->left!=NULL)
              min_node=min_node->left;
    }
    else if(fnode->left!=NULL){
        min_node=fnode->left;
        while(min_node->right!=NULL)
              min_node=min_node->right;
    }
    else{
        min_node=fnode;
    }
    
    __replace_node(fnode, min_node);
    //用非叶子节点替换要删除的节点
    if (fnode->color == RB_BLACK) {
        if (min_node->color == RB_RED)
            min_node->color = RB_BLACK;
        else
            __delete_case1(min_node);
    }
    if(!__is_leaf(min_node)){
       return NULL;
    }
    if(min_node==root)
        root==NULL;
    else if(min_node->parent->right==min_node)
        min_node->parent->right=NULL;
    else
        min_node->parent->left=NULL;
    pool->Free(min_node);
    return NULL;
}