算法读书笔记第3章-2

一、红黑树：是一种弱平衡二叉树，无论键的插入顺序如何，红黑树基本是完美平衡的，保证了查找、插入、删除的时间复杂度最坏为O(log n)

二、性质:

1、根节点必须是黑色的
2、所有结点必须是红色、黑色
3、终端节点（NULL）认为是黑色
4、没有两个红节点互为父子关系一个结点是红的，则孩子结点必为黑色
5、从任意结点出发，到其所有可以到达的终端结点的各条路径上的黑色结点个数必须相同
6、新来结点都是红的

三、插入——解决方法：旋转和变色

插入的代码如下：

/**
    Name:   Red-Black_Tree
    Author: Bryant_xw
    Date: 2018-12-06-17.56.09
*/
#include<stdio.h>
#include<stdlib.h>

#define RED 0
#define BLACK 1

typedef struct Node
{
    int    nValue;
    struct Node* pLeft;
    struct Node* pRight;
    struct Node* pFather;
    int    nColor;   //RED 0  BLACK 1
}RB_Tree;

RB_Tree* pRBT = NULL;

//右旋
void RightRotate(RB_Tree** tree)
{  RB_Tree* pNode = *tree; //需要旋转的支点  RB_Tree* pMark = pNode->pLeft;//标记点  pNode->pLeft = pMark->pRight;  pMark->pRight = pNode;

    //判断支点是否有父亲  if(pNode->pFather == NULL)  {  pRBT = pMark;  }else{  if(pNode == pNode->pFather->pLeft){  pNode->pFather->pLeft = pMark;  }else{  pNode->pFather->pRight = pMark;  }  }  if(pNode->pLeft != NULL){  pNode->pLeft->pFather = pNode;  }  pMark->pFather = pNode->pFather;  pNode->pFather = pMark;
}

//左旋——原理类似于右旋
void LeftRotate(RB_Tree** tree)
{  RB_Tree* pNode = *tree;  RB_Tree* pMark = pNode->pRight;  pNode->pRight = pMark->pLeft;  pMark->pLeft = pNode;  if(pNode->pFather == NULL){  pRBT = pMark;  }else{  if(pNode->pFather->pLeft == pNode)  pNode->pFather->pLeft = pMark;  else  pNode->pFather->pRight = pMark;  }  if(pNode->pRight != NULL)  {  pNode->pRight->pFather = pNode;  }  pMark->pFather = pNode->pFather;  pNode->pFather = pMark;

}

//获取叔叔结点
RB_Tree* GetUncle(RB_Tree *pNode)
{
//   ps：这个叔叔是对于pTemp结点的，实质是pNode的兄弟结点
    if(pNode == pNode->pFather->pLeft)
        return pNode->pFather->pRight;
    else
        return pNode->pFather->pLeft;
}


void RB_AddNode(int num)
{
    RB_Tree* pTemp = NULL;
    RB_Tree* pNode = NULL;

    pTemp = (RB_Tree*)malloc(sizeof(RB_Tree));  pTemp->nValue = num;  pTemp->nColor = RED;  pTemp->pFather = NULL;  pTemp->pLeft = NULL;  pTemp->pRight = NULL;  pNode = pRBT;
    //树是空树，直接为根，涂黑即可  if(pNode == NULL){  pRBT = pTemp;  pRBT->nColor = BLACK;  return;  }else{   //非空树
        while(pNode){

            if(pNode->nValue < num){
                    //向右子树插入
                if(pNode->pRight == NULL){
                    pNode->pRight = pTemp;
                    pTemp->pFather =pNode;
                    break;
                }
                pNode = pNode->pRight;
            }else if(pNode->nValue > num){
                    //向左子树插入
                if(pNode->pLeft == NULL){
                    pNode->pLeft = pTemp;
                    pTemp->pFather = pNode;
                    break;
                }
                pNode = pNode->pLeft;
            }else{
                    //出现相等的情况
                printf("data is error!\n");
                free(pTemp);
                pTemp = NULL;
                return ;
            }
        }

        //颜***况分析
        RB_Tree *pUncle = NULL;
        RB_Tree *pGrandPa = NULL;

        //2.父亲是黑色的，直接插入即可
        if(pNode->nColor == BLACK){
            return;
        }else{
            //3.父亲是红色的
            while(pNode->nColor == RED){
                pGrandPa = pNode->pFather;
                pUncle = GetUncle(pNode); //获取pNode的兄弟结点

                //3.1 叔叔结点是红色
                if(pUncle != NULL && pUncle->nColor == RED){
                    pNode->nColor = BLACK;
                    pUncle->nColor = BLACK;
                    pGrandPa->nColor = RED;

                    pTemp = pGrandPa;
                    pNode = pTemp->pFather;

                    //新支点是空，则直接变为根root
                    if(pNode == NULL){
                        pRBT->nColor = BLACK;
                        break;
                    }
                    //否则继续向上调整
                    continue;
                }

                //3.2 叔叔是黑色的(两种情况：NULL个BLACK)
                if(pUncle == NULL || pUncle->nColor == BLACK){

                    //3.2.1 父亲结点是爷爷的左
                    if(pNode == pGrandPa->pLeft){
                        //3.2.1.1 当前结点是父亲结点的右
                        if(pTemp == pNode->pRight){
                            pTemp = pNode;
                            LeftRotate(&pTemp);
                            pNode = pTemp->pFather;
                            continue;
                        }
                        //3.2.1.2 当前结点是父亲结点的左
                        if(pTemp == pNode->pLeft){
                            pNode->nColor = BLACK;
                            pGrandPa->nColor = RED;
                            RightRotate(&pGrandPa);
                            break;
                        }
                    }
                    //3.2.2 父亲结点是爷爷的右
                    if(pNode == pGrandPa->pRight){
                        //3.2.2.1 当前结点是父亲结点的左
                        if(pTemp == pNode->pLeft){
                            pTemp = pNode;
                            RightRotate(&pTemp);
                            pNode = pTemp -> pFather;
                            continue;
                        }
                        //3.2.2.2 当前结点是父亲结点的右
                        if(pTemp == pNode->pRight){
                            pNode->nColor = BLACK;
                            pGrandPa->nColor = RED;
                            LeftRotate(&pGrandPa);
                            break;
                        }
                    }
                }
            }
        }  }
}

void PreOrder(RB_Tree* tree)
{
    if(tree == NULL)
        return;
    printf("color == %d nValue == %d\n",tree->nColor,tree->nValue);
    PreOrder(tree->pLeft);
    PreOrder(tree->pRight);
}

int main(){
    int i;
    int arr[] = {11,2,14,1,7,5,15,8,4};

    for(i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i)
    {
        RB_AddNode(arr[i]);
    }
    PreOrder(pRBT);
    printf("--------------------------\n");
    return 0;
}

四、红黑树的删除是挺重要的，但是情况也是十分繁琐的，具体的情况分析我都在代码的实现中分类讨论了并做了详细的注释

哇~~~~红黑树还真是值得花时间去搞搞的货，挺底层的一种数据结构了，mysql中也基本使用红黑树检索。

ps：是真复杂呀，足足花了差不多两天时间，心在滴血

这次算是完结了

——12.08 23：38

删除结点的代码

(X)是操作的结点，（P）是（X）的父亲结点，（S）是（X）的兄弟结点，（LN）（RN）是（X）的侄子，也就是（S）的孩子

void RB_DelNode(int num)
{
    RB_Tree* pTemp = NULL;
    //查找
    pTemp = pRBT;
    while(pTemp)
    {
        if(pTemp->nValue == num){
            break;
        }else if (pTemp->nValue > num)
        {
            pTemp = pTemp->pLeft;
        }else{
            pTemp = pTemp->pRight;
        }
    }

    //分析被删除的位置
    //查无此数
    if(pTemp == NULL)   return;

    //要删除的结点(x)有两个孩子
    RB_Tree* pMark = NULL;
    if(pTemp->pLeft != NULL && pTemp->pRight != NULL){
       //寻找左的最右来替代pMark，实现删除pMark结点
       pMark = pTemp;
       pTemp = pTemp->pLeft;
       while(pTemp->pRight != NULL)
       {
            pTemp = pTemp -> pRight;
       }
       //值覆盖
       pMark -> nValue = pTemp->nValue;
    }

    //分析颜色
    RB_Tree* pNode = NULL;
    pNode = pTemp -> pFather;

    //1.根
    //pTemp即Root，此时pTemp->pFather == NULL 就是pNode
    if(pNode == NULL)
    {
        //没有孩子,直接删除
        if(pTemp->pLeft == NULL && pTemp->pRight == NULL)
        {
            free(pTemp);
            pTemp = NULL;
            pRBT = NULL;
            return;
        }
        //有一个孩子，删除(x)，将孩子涂黑
        if(pTemp->pLeft != NULL || pTemp->pRight != NULL)
        {
            pRBT = pTemp->pLeft ? pTemp->pLeft : pTemp->pRight;
            pRBT->nColor = BLACK;
            pRBT->pFather = NULL;
            free(pTemp);
            pTemp = NULL;
            return;
        }
    }

    //2.非根
    //2.1 删除的结点(x)是RED
    if(pTemp->nColor == RED)
    {
        //直接删，因为之前的Search过程已将(x)从逻辑上换到叶子结点
        if(pTemp == pNode->pLeft)
        {
            pNode->pLeft = NULL;
        }else{
            pNode->pRight = NULL;
        }
        free(pTemp);
        pTemp = NULL;
        return;
    }
    //2.2 删除的结点(x)是BLACK
    if (pTemp->nColor == BLACK)
    {
        //2.2.1 有一个红孩子
        if (pTemp -> pLeft != NULL || pTemp -> pRight != NULL)
        {
            if(pTemp == pNode->pLeft){
                pNode->pLeft = pTemp->pLeft ? pTemp->pLeft : pTemp -> pRight;
                pNode->pLeft->pFather = pNode;
                pNode->pLeft->nColor = BLACK;
            }else{
                pNode->pRight = pTemp->pLeft?pTemp->pLeft : pTemp -> pRight;
                pNode->pRight->pFather = pNode;
                pNode->pRight->nColor = BLACK;
            }
            free(pTemp);
            pTemp = NULL;
            return;
        }

        ///2.2.2 没有孩子
        //开始判断 兄弟结点(S)、侄子结点(LN) (RN) === 分2个case：(S)：BlACK || RED
        RB_Tree* pBrother = NULL;
        pBrother = GetUncle(pTemp);

        //假删除
        if(pTemp == pNode->pLeft)
        {
            pNode->pLeft = NULL;
        }else{
            pNode->pRight = NULL;
        }

        pMark = pTemp;
        while(pTemp != pRBT && pTemp->nColor == BLACK)
        {
            //case1: 兄弟结点(S)是RED
            //处理方式：(S)涂黑，(P)涂红，(X)是左孩子->左旋，右孩子->右旋、
            if(pBrother!= NULL && pBrother->nColor == RED)
            {
                pBrother->nColor = BLACK;
                pNode->nColor = RED;
                /*
                 *兄弟结点(S)是父亲结点(P)的左孩子
                 *等价：(X)即pMark是右孩子->右旋(P)
                 *更新兄弟结点(S)为(S)->pRight
                 *画图理解
                */
                if(pBrother == pNode->pLeft)
                {
                    pBrother = pBrother->pRight;
                    RightRotate(&pNode);
                    continue;
                }
                /*
                 *兄弟结点(S)是父亲结点(P)的右孩子
                 *等价：(X)即pMark是左孩子->左旋(P)
                 *更新兄弟结点(S)为(S)->pLight
                 *画图理解
                */
                if(pBrother == pNode->pRight)
                {
                    pBrother = pBrother->pLeft;
                    LeftRotate(&pNode);
                    continue;
                }
            }

            //case2:兄弟结点(S)是BLACK
            if(pBrother->nColor == BLACK)
            {
                //2.1两个侄子(LN)、(RN)均是黑色
                //要看父亲结点(P)的颜色
                if( (pBrother->pLeft == NULL && pBrother->pRight == NULL)
                    ||
                    (   (pBrother->pLeft != NULL && pBrother->pLeft->nColor == BLACK)
                        &&
                        (pBrother->pRight != NULL && pBrother->pRight->nColor == BLACK)
                    )//||
                  )//if
                {
                    //2.1.1 父亲结点(S)是红色
                    if (pNode->nColor == RED)
                    {
                        pBrother->nColor = RED;
                        pNode->nColor = BLACK;
                        break;
                    }

                    //2.1.2 父亲结点(S)是黑色
                    if (pNode->nColor == BLACK)
                    {
                        pBrother->nColor = RED;
                        pTemp = pNode;  //(X)回溯到(P)
                        pNode = pTemp->pFather;
                        if(pNode == NULL){
                            break;
                        }
                        pBrother = GetUncle(pTemp);
                        continue;
                    }

                }

                //2.2左侄子(LN)是红色，右侄子(RN)是黑色
                //处理方式：(S)涂红，(LN)涂黑，(X)左孩子->右旋(S) 右孩子->左旋(S)
                if((pBrother->pLeft != NULL && pBrother->pLeft->nColor == RED)
                    &&
                    (pBrother->pRight == NULL || pBrother->pRight->nColor == BLACK)
                  )
                {
                    //2.2.1 兄弟结点(S)是父亲结点(P)的right孩子
                    //等价：(X)是(P)的left孩子===右旋
                    if(pBrother == pNode->pRight)
                    {
                        pBrother->nColor = RED;
                        pBrother->pLeft->nColor = BLACK;
                        RightRotate(&pBrother);
                        pBrother = pNode->pRight;
                        continue;
                    }

                    //2.2.2 兄弟结点(S)是父亲结点(P)的left孩子
                    //等价：(X)是(P)的right孩子===左旋
                    //处理方式：父色子用，(P)、(LN)涂黑，左旋(P)==结束
                    if(pBrother == pNode->pLeft)
                    {
                        pBrother->nColor = pNode->nColor;
                        pNode->nColor = BLACK;
                        pBrother->pLeft->nColor = BLACK;
                        RightRotate(&pNode);
                        break;
                    }

                }

                //2.3 右侄子(RN)红色
                if(pBrother->pRight != NULL && pBrother->pRight->nColor == RED)
                {
                    //2.3.1 兄弟结点(S)是父亲结点(P)的left孩子
                    if (pBrother == pNode->pLeft)
                    {
                        pBrother->nColor = RED;
                        pBrother->pRight->nColor = BLACK;
                        LeftRotate(&pBrother);
                        pBrother = pNode->pLeft;
                        continue;
                    }

                    //2.3.2 兄弟结点(S)是父亲结点(P)的right孩子
                    //处理方式：父色子用，(P)、(RN)涂黑，左旋(P)==结束
                    if(pBrother == pNode->pRight)
                    {
                        pBrother->nColor = pNode->nColor;
                        pNode->nColor = BLACK;
                        pBrother->pRight->nColor = BLACK;
                        LeftRotate(&pNode);
                        break;
                    }
                }
            }
        }
        //释放
        free(pMark);
        pMark = NULL;
    }

}

#笔记##读书笔记#