红黑树复习...写一遍好累..

[sunstrikes]

首先是node:

struct node {
    int value;
    int color;//red 0 , black 1
    node * left;
    node * right;
    node* parent;
    node(int val) {
        value = val;
        left = right = parent = NULL;
    }
};
const int red = 0;
const int black = 1;

类声明:

#include"node.h"
class RBTree {
    /*
    I、红黑树的五个性质：
    1）每个结点要么是红的，要么是黑的。
    2）根结点是黑的。
    3）每个叶结点，即空结点（NIL）是黑的。
    4）如果一个结点是红的，那么它的俩个儿子都是黑的。
    5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
    */
private:
    node * root;
    void rotate_left(node* target);
    void rotate_right(node* target);
    node* successor(node* target);
    void insertAdjust(node* target);
    void removeAdjust(node* target);
public:
    RBTree();
    ~RBTree();
    node* insert(node* parent, int data);
    bool remove(node* parent, int data);
    node* search(node* root, int data);
};

方法实现:
1.左右旋转

void RBTree::rotate_left(node * target)
{
    node* right = target->right;
    node* parent = target->parent;
    if (parent!=NULL)
    {
        right->parent = parent;
        if (parent->right == target)
            parent->right = right;
        else
            parent->left = right;
    }
    node* move = right->left;
    right->parent = target->parent;
    target->parent = right;
    right->left = target;
    if (move!=NULL)
    {
        target->right = move;
        move->parent = target;
    }
    if (target == root)
    {
        root = right;
    }
}

void RBTree::rotate_right(node * target)
{
    node* left = target->left;
    node* parent = target->parent;
    if (parent != NULL) {
        left->parent = parent;//把left挂到parent下
        if (parent->left == target)
            parent->left = left;
        else
            parent->right = left;
    }
    node* move = left->right;
    left->parent = target->parent;//parent is null
    target->parent= left;
    left->right = target;
    if (move != NULL) {
        target->left = move;
        move->parent = target;
    }
    if (target == root)//旋转的是根节点的情况
        root = left;
}

2.查找后继节点:

node * RBTree::successor(node * target)
{
    node* tmp = target;
    if (target->right != NULL) {//case1 当target节点有右孩子时，返回右子树中最小的节点，即7节点
        tmp = target->right;
        while (tmp->left != NULL)
            tmp = tmp->left;
        return tmp;
    }
    while (tmp->parent!=NULL&&tmp==tmp->parent->right)
    {//case 2 当左子树为空时，可以理解为比7节点 小的，但是小节点中最大的节点，这个节点就应该是7节点的             左子树中最大的节点，即6节点。
        tmp = tmp->parent;
    }
    return tmp->parent;
}

3.插入与插入调整

node * RBTree::insert(node * parent, int data)
{
    if (parent->value > data) {
        if (parent->left == NULL) {
            node* res = new node(data);
            res->parent = parent;
            parent->left = res;
            res->color = red;
            insertAdjust(res);
            return res;
        }
        else
            return insert(parent->left, data);
    }
    else {
        if (parent->right == NULL) {
            node* res = new node(data);
            res->parent = parent;
            parent->right = res;
            res->color = red;
            insertAdjust(res);
            return res;
        }
        else {
            return insert(parent->right, data);
        }
    }
}

void RBTree::insertAdjust(node * target)
{
    node* tmp = target;
    while (tmp != NULL&&tmp != root&&tmp->parent->color == red) {
        //父节点为红
        node* parent = tmp->parent;
        node* grand = parent->parent;
        if (parent == grand->left) //case1
        {
            node* uncle = grand->left;
            if (uncle&&uncle->color == red) {
                grand->color = red;
                parent->color = black;
                uncle->color = black;
                tmp = grand;//观察爷节点
            }
            else {
                if (tmp == parent->right) {//case2
                    tmp = tmp->parent;
                    rotate_left(tmp);
                }
                tmp->parent->color = black;//case3
                tmp->parent->parent->color = red;
                rotate_right(tmp->parent->parent);
            }
        }
        else//反方向
        {
            node* uncle = grand->left;
            if (uncle&&uncle->color == red) {
                grand->color = red;
                parent->color = black;
                uncle->color = black;
                tmp = grand;
            }
            else {
                if (tmp == parent->left) {
                    tmp = tmp->parent;
                    rotate_right(tmp);
                }
                tmp->parent->color = black;
                tmp->parent->parent->color = red;
                rotate_left(tmp->parent->parent);
            }
        }
        root->color = black;
    }
}

4.删除与删除调整

void RBTree::removeAdjust(node * tar)
{
    node* other;//w
    node* parent = tar->parent;
    while ((!tar || tar->color == black) && tar != root)
    {
        if (parent->left == tar) {
            other = parent->right;
            if (other->color == red) {
                //case1 : x的兄弟w是红的
                other->color = black;
                parent->color = red;
                rotate_left(parent);
                other = parent->right;
            }
            if ((!other->left || other->left->color == black) &&
                (!other->right || other->right->color == black))
            { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 
                other->color = red;
                tar = parent;
                parent = tar->parent;
            }
            else {
                if (!other->right || other->right->color == black) {
                    // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。  
                    other->left->color = black;
                    other->color = red;
                    rotate_right(other);
                    other = parent->right;
                }
                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                other->color = parent->color;
                parent->color = black;
                other->right->color = black;
                rotate_left(parent);
                tar = root;
                break;
            }
        }
        else {
            other = parent->left;
            if (other->color == red) {
                //case1 : x的兄弟w是红的
                other->color = black;
                parent->color = red;
                rotate_right(parent);
                other = parent->left;
            }
            if ((!other->left || other->left->color == black) &&
                (!other->right || other->right->color == black))
            { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 
                other->color = red;
                tar = parent;
                parent = tar->parent;
            }
            else {
                if (!other->left || other->left->color == black) {
                    // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。  
                    other->right->color = black;
                    other->color = red;
                    rotate_left(other);
                    other = parent->left;
                }
                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                other->color = parent->color;
                parent->color = black;
                other->left->color = black;
                rotate_right(parent);
                tar = root;
                break;
            }
        }
    }
    if (tar)
        tar->color = black;
}

bool RBTree::remove(node * root, int data)
{
    node* del = search(root,data);
    node* child;
    node* parent;
    if (!del) {//找不到的情况
        return false;
    }
    if (del->left != NULL && del->right != NULL) {
        node* replace = del;//用来代替被删节点,即后继节点
        replace = replace->right;
        while (replace->left != NULL) {
            replace = replace->left;
        }
        if (del->parent) {
            //不是根节点
            if (del->parent->left == del)
                del->parent->left = replace;
            else
                del->parent->right = replace;
        }
        else
            root = replace;

        //child 是 取代节点右孩子
        child = replace->right;
        parent = replace->parent;
        int color = replace->color;
        if (parent == del)
            parent = replace;//是后继节点的父节点
        else {
            if (child)//删掉后继节点的处理
                child->parent = parent;
            parent->left = child;

            replace->right = del->right;//设好del的右子树
            del->right->parent = replace;
        }

        replace->parent = del->parent;
        replace->color = del->color;
        replace->left = del->left;
        del->left->parent = replace;

        if (color == black)
            removeAdjust(child);
        delete del;
    }

    //只有一个子树的情况
    if (del->left != NULL)
        child = del->left;
    else
        child = del->right;

    parent = del->parent;
    int color = del->color;
    if (child)
        child->parent = parent;
    if (parent) {
        if (parent->left == del)
            parent->left = child;
        else
            parent->right = child;
    }
    else
        root = child;
    //如果y不是黑色，是红色的，则当y被删除时，红黑性质仍然得以保持。不做操作，返回。

    //因为：1.树种各结点的黑高度都没有变化。2.不存在俩个相邻的红色结点。

    //3.因为入宫y是红色的，就不可能是根。所以，根仍然是黑色的。
    if (color == black)
        removeAdjust(child);
    delete del;
    return true;
}

5.查找:

node * RBTree::search(node * root, int data)
{
    node* tmp = root;
    while (tmp != NULL) {
        if (data < tmp->value) {
            tmp = tmp->left;
        }
        else if (data > tmp->value)
        {
            tmp = tmp->right;
        }
        else
            break;
    }
    return tmp;
}