數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)

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

介紹：
網(wǎng)站設計制作、網(wǎng)站設計的開發(fā)，更需要了解用戶，從用戶角度來建設網(wǎng)站，獲得較好的用戶體驗。創(chuàng)新互聯(lián)公司多年互聯(lián)網(wǎng)經(jīng)驗，見的多，溝通容易、能幫助客戶提出的運營建議。作為成都一家網(wǎng)絡公司，打造的就是網(wǎng)站建設產(chǎn)品直銷的概念。選擇創(chuàng)新互聯(lián)公司，不只是建站，我們把建站作為產(chǎn)品，不斷的更新、完善，讓每位來訪用戶感受到浩方產(chǎn)品的價值服務。
紅黑樹是一種特化的AVL樹（平衡二叉樹），都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。
紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于 1，所以紅黑樹不是嚴格意義上的平衡二叉樹（AVL），但對之進行平衡的代價較低，其平均統(tǒng)計性能要強于 AVL
由于每一棵紅黑樹都是一顆二叉排序樹，因此，在對紅黑樹進行查找時，可以采用運用于普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息

1. 圖文解析

紅黑樹性質(zhì)

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

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

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

typedef char DataType;

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

1.2 紅黑樹的插入操作

在紅黑樹的插入時，第一個問題就是新插入的結(jié)點應該為紅色還是黑色呢？
根據(jù)性質(zhì)二：如果初始紅黑樹為空，則插入的一定是根節(jié)點且為黑色
根據(jù)性質(zhì)五：如果新插入的結(jié)點為黑色，那么勢必會導致路徑上的黑色結(jié)點數(shù)量的增加，無疑增加了插入后的調(diào)整難度
根據(jù)性質(zhì)三：如果新插入的結(jié)點為紅色，那么新結(jié)點的兩個空結(jié)點一定為黑色，那么就不會增加路徑上的黑色結(jié)點數(shù)量
總結(jié)：若插入的是根結(jié)點，則設置為黑色，其他情況則設置為紅色

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

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

若父親結(jié)點為祖父結(jié)點的左孩子結(jié)點
叔叔結(jié)點為紅色
調(diào)整過程：父親結(jié)點和叔叔結(jié)點均變?yōu)楹谏?，祖父結(jié)點若不是根結(jié)點，則變?yōu)榧t色，并將祖父結(jié)點視為新插入的結(jié)點，繼續(xù)向上調(diào)整
叔叔結(jié)點為黑色
2.1 插入的位置是父親結(jié)點的左孩子
調(diào)整過程：父親結(jié)點變?yōu)楹谏?，祖父結(jié)點變?yōu)榧t色，最后右旋祖父結(jié)點
2.2 插入父親結(jié)點的右孩子
調(diào)整過程：左旋父結(jié)點，而后可視為2.1的情況進行調(diào)整
若父親結(jié)點為祖父結(jié)點的右孩子結(jié)點，其操作與以上情況對稱，詳細見代碼

2. 源代碼

#include#includetypedef char DataType;

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

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

// 創(chuàng)建新結(jié)點
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é)點左孩子
        // flag = 1：node為父結(jié)點右孩子
        !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é)點左孩子
        // flag = 1：node為父結(jié)點右孩子
        !flag ? (parent->lchild = right) : (parent->rchild = right);
    }
}


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

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

        // 以下同理，對稱操作
        if (uncle && uncle->color == 1)
        {// printf("\t\t叔叔(%c)為紅色\n", uncle->data);
            father->color = 0;
            uncle->color = 0;
            grandfather->color = 1;
            // 遞歸調(diào)整祖父結(jié)點
            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é)點\n");

            RightRotate(father, 1);
            RBTreeAdjust(father);
            
        }
        else
        {// printf("\t\t叔叔為黑色，插入位置為父親的右孩子\n");
            // printf("\t\t>>父結(jié)點(%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é)點作為根結(jié)點
    if ((*T) == NULL)
    {// 性質(zhì)二：根結(jié)點為黑色
        (*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é)點插入
    node = NewNode(1, x);
    if (parent->data >x)
    {parent->lchild = node;
    }
    else
    {parent->rchild = node;
    }
    node->parent = parent;
    
    
    // 若父結(jié)點為紅色，則不符合性質(zhì)三：紅色結(jié)點的孩子結(jié)點均為黑色
    if (parent->color == 1)
    {// printf("父結(jié)點(%c)為紅色，需要進行調(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ù):");    // 測試數(shù)據(jù)：FEKDCABNMOP
        scanf("%c", &x);
        if (x == '#')
        {break;
        }
        RBTreeInsert(&T, x);
        printf("先序遍歷:");
        PreOrderTraverse(T);
        printf("\n\n");
    }
    system("pause");
    return 0;
}

3. 測試結(jié)果

在這里插入圖片描述

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

網(wǎng)頁題目：數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)
文章URL：http://aaarwkj.com/article0/ieioo.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設、手機網(wǎng)站建設、品牌網(wǎng)站建設、網(wǎng)站設計公司、電子商務、移動網(wǎng)站建設

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区

數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)