數(shù)據(jù)結(jié)構(gòu)總目錄紅黑樹

介紹：

網(wǎng)站設(shè)計(jì)制作、網(wǎng)站設(shè)計(jì)的開發(fā)，更需要了解用戶，從用戶角度來建設(shè)網(wǎng)站，獲得較好的用戶體驗(yàn)。創(chuàng)新互聯(lián)公司多年互聯(lián)網(wǎng)經(jīng)驗(yàn)，見的多，溝通容易、能幫助客戶提出的運(yùn)營(yíng)建議。作為成都一家網(wǎng)絡(luò)公司，打造的就是網(wǎng)站建設(shè)產(chǎn)品直銷的概念。選擇創(chuàng)新互聯(lián)公司，不只是建站，我們把建站作為產(chǎn)品，不斷的更新、完善，讓每位來訪用戶感受到浩方產(chǎn)品的價(jià)值服務(wù)。

• 紅黑樹是一種特化的AVL樹（平衡二叉樹），都是在進(jìn)行插入和刪除操作時(shí)通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。
• 紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于 1，所以紅黑樹不是嚴(yán)格意義上的平衡二叉樹（AVL），但 對(duì)之進(jìn)行平衡的代價(jià)較低， 其平均統(tǒng)計(jì)性能要強(qiáng)于 AVL
• 由于每一棵紅黑樹都是一顆二叉排序樹，因此，在對(duì)紅黑樹進(jìn)行查找時(shí)，可以采用運(yùn)用于普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息

1. 圖文解析

紅黑樹性質(zhì)

• 性質(zhì)一：結(jié)點(diǎn)是紅色或黑色
• 性質(zhì)二：根結(jié)點(diǎn)是黑色
• 性質(zhì)三：空結(jié)點(diǎn)為葉子結(jié)點(diǎn)，且所有葉子結(jié)點(diǎn)都是黑色
• 性質(zhì)四：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)都是黑色
• 性質(zhì)五：從任一結(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)

1.1 存儲(chǔ)結(jié)構(gòu)

與一般二叉樹相比，紅黑樹的結(jié)構(gòu)存在父結(jié)點(diǎn)指針和結(jié)點(diǎn)顏色的標(biāo)識(shí)

typedef char DataType;

typedef struct RBNode
{int color;                      // 結(jié)點(diǎn)顏色（0:黑色  1:紅色）
    DataType data;                  // 結(jié)點(diǎn)數(shù)據(jù)
    struct RBNode *parent;          // 父結(jié)點(diǎn)指針，用于定位
    struct RBNode *lchild, *rchild; // 左右孩子指針
}RBNode, *RBTree;

1.2 紅黑樹的插入操作

在紅黑樹的插入時(shí)，第一個(gè)問題就是新插入的結(jié)點(diǎn)應(yīng)該為紅色還是黑色呢？

• 根據(jù)性質(zhì)二：如果初始紅黑樹為空，則插入的一定是根節(jié)點(diǎn)且為黑色
• 根據(jù)性質(zhì)五：如果新插入的結(jié)點(diǎn)為黑色，那么勢(shì)必會(huì)導(dǎo)致路徑上的黑色結(jié)點(diǎn)數(shù)量的增加，無疑增加了插入后的調(diào)整難度
• 根據(jù)性質(zhì)三：如果新插入的結(jié)點(diǎn)為紅色，那么新結(jié)點(diǎn)的兩個(gè)空結(jié)點(diǎn)一定為黑色，那么就不會(huì)增加路徑上的黑色結(jié)點(diǎn)數(shù)量

總結(jié)：若插入的是根結(jié)點(diǎn)，則設(shè)置為黑色，其他情況則設(shè)置為紅色

已知新插入的結(jié)點(diǎn)為紅色，而如果父結(jié)點(diǎn)也為紅色，就會(huì)違反性質(zhì)四，則說明此時(shí)需要調(diào)整紅黑樹
同時(shí)在父親結(jié)點(diǎn)為紅色的條件下，則根據(jù)性質(zhì)二，父親結(jié)點(diǎn)一定不是根結(jié)點(diǎn)，且存在祖父結(jié)點(diǎn)

調(diào)整情況如下：

若父親結(jié)點(diǎn)為祖父結(jié)點(diǎn)的左孩子結(jié)點(diǎn)

1. 叔叔結(jié)點(diǎn)為紅色
   調(diào)整過程：父親結(jié)點(diǎn)和叔叔結(jié)點(diǎn)均變?yōu)楹谏?，祖父結(jié)點(diǎn)若不是根結(jié)點(diǎn)，則變?yōu)榧t色，并將祖父結(jié)點(diǎn)視為新插入的結(jié)點(diǎn)，繼續(xù)向上調(diào)整

---

2. 叔叔結(jié)點(diǎn)為黑色

2.1 插入的位置是父親結(jié)點(diǎn)的左孩子

• 調(diào)整過程：父親結(jié)點(diǎn)變?yōu)楹谏?，祖父結(jié)點(diǎn)變?yōu)榧t色，最后右旋祖父結(jié)點(diǎn)

---

2.2 插入父親結(jié)點(diǎn)的右孩子

• 調(diào)整過程：左旋父結(jié)點(diǎn)，而后可視為2.1的情況進(jìn)行調(diào)整

---

若父親結(jié)點(diǎn)為祖父結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，其操作與以上情況對(duì)稱，詳細(xì)見代碼

2. 源代碼

#include#includetypedef char DataType;

typedef struct RBNode
{int color;                      // 結(jié)點(diǎn)顏色（0:黑色  1:紅色）
    DataType data;                  // 結(jié)點(diǎn)數(shù)據(jù)
    struct RBNode *parent;          // 父結(jié)點(diǎn)指針，用于定位
    struct RBNode *lchild, *rchild; // 左右孩子指針
}RBNode, *RBTree;

void InitRBTree(RBTree *T)
{(*T) = NULL;
    printf("紅黑樹已初始化!\n");
}

// 創(chuàng)建新結(jié)點(diǎn)
RBNode *NewNode(int color, DataType x)
{RBNode *newNode;
    newNode = (RBNode *)malloc(sizeof(RBNode));
    newNode->data = x;
    newNode->color = color;    
    newNode->parent = newNode->lchild = newNode->rchild = NULL;
    return newNode;
}

// 右旋轉(zhuǎn)， 
void RightRotate(RBNode *node, int flag)
{RBNode *parent = node->parent;
    RBNode *left = node->lchild;

    node->lchild = left->rchild;
    if (left->rchild)
    {left->rchild->parent = node;
    }
    
    left->rchild = node;
    node->parent = left;

    left->parent = parent;
    if (parent)
    {// flag = 0：node為父結(jié)點(diǎn)左孩子
        // flag = 1：node為父結(jié)點(diǎn)右孩子
        !flag ? (parent->lchild = left) : (parent->rchild = left);
    }
}

// 左旋轉(zhuǎn)
void LeftRotate(RBNode *node, int flag)
{RBNode *parent = node->parent;
    RBNode *right = node->rchild;
    
    node->rchild = right->lchild;
    if (right->lchild)
    {right->lchild->parent = node;
    }
    
    right->lchild = node;
    node->parent = right;

    right->parent = parent;
    if (parent)
    {// flag = 0：node為父結(jié)點(diǎn)左孩子
        // flag = 1：node為父結(jié)點(diǎn)右孩子
        !flag ? (parent->lchild = right) : (parent->rchild = right);
    }
}


// 紅黑樹調(diào)整
void RBTreeAdjust(RBNode *node)
{// 父結(jié)點(diǎn)為紅色，則父結(jié)點(diǎn)一定不是根結(jié)點(diǎn)，且祖父結(jié)點(diǎn)一定存在
    RBNode *father = node->parent;
    RBNode *grandfather = father->parent;
    RBNode *uncle;

    if (father && father == grandfather->lchild)
    {// 父親為祖父的左孩子
        uncle = grandfather->rchild;
        // printf("\t父親(%c)為祖父(%c)的左孩子\n", father->data, grandfather->data);
        if (uncle && uncle->color == 1)
        {// 若叔叔結(jié)點(diǎn)存在且為紅色，則進(jìn)行變色
            // printf("\t\t叔叔(%c)為紅色，進(jìn)行變色\n", uncle->data);
            father->color = 0;
            uncle->color = 0;
            grandfather->color = 1;
            // 遞歸調(diào)整祖父結(jié)點(diǎn)
            if (grandfather->parent && grandfather->parent->color == 1)
            {RBTreeAdjust(grandfather);
            }
            else if(!grandfather->parent)
            {grandfather->color = 0;
            }
        }
        // 叔叔結(jié)點(diǎn)不存在，或者為黑色
        else if (node == father->lchild)
        {// 若插入的結(jié)點(diǎn)是父親的左孩子，則進(jìn)行變色并對(duì)祖父進(jìn)行右旋轉(zhuǎn)
            // printf("\t\t叔叔為黑色，插入位置為父親的左孩子\n");
            // printf("\t\t>>父結(jié)點(diǎn)(%c)變黑色，祖父(%c)邊紅色, 右旋祖父\n", father->data, grandfather->data);

            father->color = 0;
            grandfather->color = 1;
            RightRotate(grandfather, 0);
        }
        else
        {// 若插入的結(jié)點(diǎn)是父親的右孩子，則對(duì)父親進(jìn)行左旋轉(zhuǎn)
            // printf("\t\t叔叔為黑色，插入位置為父親的右孩子\n");
            // printf("\t\t>>左旋父親結(jié)點(diǎn)\n");
            
            LeftRotate(father, 0);
            RBTreeAdjust(father);
        }
    }
    else
    {// 父親為祖父的右孩子
        uncle = grandfather->lchild;
        // printf("\t父親(%c)為祖父(%c)的右孩子\n", father->data, grandfather->data);

        // 以下同理，對(duì)稱操作
        if (uncle && uncle->color == 1)
        {// printf("\t\t叔叔(%c)為紅色\n", uncle->data);
            father->color = 0;
            uncle->color = 0;
            grandfather->color = 1;
            // 遞歸調(diào)整祖父結(jié)點(diǎn)
            if (grandfather->parent && grandfather->parent->color == 1)
            {RBTreeAdjust(grandfather);
            }
            else  if(!grandfather->parent)
            {grandfather->color = 0;
            }
        }
        else if (node == father->lchild)
        {// printf("\t\t叔叔為黑色，插入位置為父親的左孩子\n");
            // printf("\t\t>>右旋父親結(jié)點(diǎn)\n");

            RightRotate(father, 1);
            RBTreeAdjust(father);
            
        }
        else
        {// printf("\t\t叔叔為黑色，插入位置為父親的右孩子\n");
            // printf("\t\t>>父結(jié)點(diǎn)(%c)變黑色，祖父(%c)邊紅色, 左旋祖父\n", father->data, grandfather->data);

            father->color = 0;
            grandfather->color = 1;
            LeftRotate(grandfather, 1);
        }
    }
}

// 插入
void RBTreeInsert(RBTree *T, DataType x)
{// 若樹為空，則創(chuàng)建新結(jié)點(diǎn)作為根結(jié)點(diǎn)
    if ((*T) == NULL)
    {// 性質(zhì)二：根結(jié)點(diǎn)為黑色
        (*T) = NewNode(0, x);
        return;
    }

    // 根據(jù)二叉排序樹的性質(zhì)查找插入位置
    RBNode *node = (*T), *parent;
    while (node)
    {parent = node;
        if (node->data >x)
        {node = node->lchild;
        }
        else if (node->data< x)
        {node = node->rchild;
        }
        else
        {printf("插入失敗，存在相同數(shù)據(jù)\n");
            return;
        }      
    }
    // 根據(jù)查找到的位置的父結(jié)點(diǎn)插入
    node = NewNode(1, x);
    if (parent->data >x)
    {parent->lchild = node;
    }
    else
    {parent->rchild = node;
    }
    node->parent = parent;
    
    
    // 若父結(jié)點(diǎn)為紅色，則不符合性質(zhì)三：紅色結(jié)點(diǎn)的孩子結(jié)點(diǎn)均為黑色
    if (parent->color == 1)
    {// printf("父結(jié)點(diǎn)(%c)為紅色，需要進(jìn)行調(diào)整!\n", parent->data);
        RBTreeAdjust(node);
    }
}



// 先序遍歷
void PreOrderTraverse(RBTree T)
{if (T)
    {printf("%c", T->data);
        T->color == 0 ? printf("[黑] ") : printf("[紅] ");
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}


int main()
{RBTree T;
    DataType x;
    InitRBTree(&T);

    while (1)
    {fflush(stdin);
        printf("輸入插入數(shù)據(jù):");    // 測(cè)試數(shù)據(jù)：FEKDCABNMOP
        scanf("%c", &x);
        if (x == '#')
        {break;
        }
        RBTreeInsert(&T, x);
        printf("先序遍歷:");
        PreOrderTraverse(T);
        printf("\n\n");
    }
    system("pause");
    return 0;
}

3. 測(cè)試結(jié)果

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)題目：數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)
URL地址：http://weahome.cn/article/ieioo.html