日韩无码中出,自拍亚洲精品探花久

1 摘要

紅黑樹（Red Black Tree）是一種自平衡二叉搜索樹，它是在1972年由Rudolf Bayer發(fā)明的，當(dāng)時(shí)被稱為平衡二叉B樹（symmetric binary B-trees）。后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。紅黑樹確保沒有一條路徑會比其他路徑長出兩倍。這個樹大致上是平衡的，因此，插入、刪除和查找操作在最壞情況下都是高效的。

2 性質(zhì)

在二叉查找樹強(qiáng)制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

性質(zhì)1. 每個結(jié)點(diǎn)是紅色或黑色
性質(zhì)2. 根結(jié)點(diǎn)是黑色
性質(zhì)3. 每個葉子結(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色
性質(zhì)4. 每個紅色結(jié)點(diǎn)的兩個子結(jié)點(diǎn)是黑色（子結(jié)點(diǎn)是紅色父結(jié)點(diǎn)一定是黑色）
性質(zhì)5. 從任意結(jié)點(diǎn)到其每個葉子結(jié)點(diǎn)的路徑包含相同數(shù)目的黑色結(jié)點(diǎn)

結(jié)論（證明可查閱其他資料，這里不討論）：一棵有n個結(jié)點(diǎn)的紅黑樹的高度至多為為2lg(n+1)

數(shù)據(jù)結(jié)構(gòu)定義

#include <stdio.h>
#include <stdlib.h>

//定義顏色類型
typedef enum Color
{
    RED = 0,
    BLACK = 1
}Color;

//定義結(jié)點(diǎn)結(jié)構(gòu)
typedef struct Node //
{
    struct Node *parent;
    struct Node *left;
    struct Node *right;
    int value;
    Color color;
}Node, *Tree;

/*
 方便處理邊界，結(jié)點(diǎn)NIL替代NULL
 所有空都指向它，可以看成外部結(jié)點(diǎn)
 */
Node *NIL=NULL;

3 旋轉(zhuǎn)

當(dāng)進(jìn)行插入或刪除操作時(shí)，可能導(dǎo)致新樹不滿足紅黑樹的性質(zhì)，此刻需要適當(dāng)?shù)男D(zhuǎn)來完成

左旋右旋示意圖

3.1 左旋

過程：x的右孩子指向y的左孩子，y的父結(jié)點(diǎn)指向x的父結(jié)點(diǎn)，y的左孩子指向x

code：

//左旋：將x的右子樹y旋轉(zhuǎn)成x的父母
void LeftRotate(Tree T, Node *x)
{
    if(x->right != NIL) {
        Node *y=x->right;
        //1.修改x的右孩子與y的左孩子的父結(jié)點(diǎn)的指針
        x->right=y->left;
        if(y->left != NIL) {
            y->left->parent=x;
        }
        //2.修改y的父結(jié)點(diǎn)與x父結(jié)點(diǎn)的孩子結(jié)點(diǎn)的指針
        y->parent=x->parent;
        if(x->parent == NIL){
            T=y;
        }else{
            if(x == x->parent->left) {
                x->parent->left=y;
            }else{
                x->parent->right=y;
            }
        }
        //3.修改y的左孩子與x的父結(jié)點(diǎn)的指針
        y->left=x;
        x->parent=y;
    } else {
        printf("can't execute left rotate due to null right child/n");
    }
}

3.2 右旋

過程：y的左孩子指向x的右孩子，x的父結(jié)點(diǎn)指向y的父結(jié)點(diǎn)，x的右孩子指向y

code：

//右旋：將x的左子樹y旋轉(zhuǎn)成x的父母
void RightRotate(Tree T, Node *x)
{
    if( x->left != NIL ) {
        Node *y=x->left;
        //1.修改x的左孩子與y的右孩子的父結(jié)點(diǎn)的指針
        x->left=y->right;
        if( y->right != NIL ) {
            y->right->parent=x;
        }
        //2.修改y的父結(jié)點(diǎn)與x父結(jié)點(diǎn)的孩子結(jié)點(diǎn)的指針
        y->parent=x->parent;
        if( x->parent == NIL ) {
            T=y;
        } else {
            if(x == x->parent->left) {
                x->parent->left=y;
            } else {
                x->parent->right=y;
            }
        }
        //3.修改y的右孩子與x的父結(jié)點(diǎn)的指針
        y->right=x;
        x->parent=y;
    } else {
        printf("can't execute right rotate due to null left child/n");
    }
}

4 插入

4.1 插入過程

紅黑樹的插入過程是在二叉搜索樹插入的基礎(chǔ)上改進(jìn)的，具體過程是先按照二叉搜索樹的插入過程插入并標(biāo)記紅色，然后對插入的結(jié)點(diǎn)進(jìn)行調(diào)整

code：

void Insert(Tree T, int val)
{
    if(T == NULL) {
        T=(Tree)malloc(sizeof(Node));
        NIL=(Node*)malloc(sizeof(Node));
        NIL->color=BLACK;
        T->left=NIL;
        T->right=NIL;
        T->parent=NIL;
        T->value=val;
        T->color=BLACK;
    }else{
        Node *x=T;
        Node *p=NIL;
        while(x != NIL) {
            p=x;
            if(val < x->value){
                x=x->left;
            }else if(val > x->value){
                x=x->right;
            }else{
                printf("duplicate value %d/n",val);
                return;
            }
        }
        x=(Node*)malloc(sizeof(Node));
        x->color=RED;
        x->left=NIL;
        x->right=NIL;
        x->parent=p;
        x->value=val;
        if(val < p->value){
            p->left = x;
        }else{
            p->right = x;
        }
        //從x開始調(diào)整
        InsertFixup(T, x);
    }
}

4.2.調(diào)整過程

4.2.1 分析

當(dāng)插入一個新的結(jié)點(diǎn)（紅色），至多違反一個性質(zhì)，可能違反性質(zhì)2或性質(zhì)4。 ① 如果違反性質(zhì)2，新增的結(jié)點(diǎn)z必定是根，此樹只有一個結(jié)點(diǎn)，直接將根結(jié)點(diǎn)置黑即可。 ② 如果違反性質(zhì)4，此時(shí)z與其父結(jié)點(diǎn)都為紅色，根據(jù)紅黑樹的性質(zhì)，z的祖父結(jié)點(diǎn)一定是黑色。我們再根據(jù)z的父結(jié)點(diǎn)是z的祖父結(jié)點(diǎn)的左孩子還是右孩子進(jìn)行討論。由于左右是對稱的，這里只討論z的父結(jié)點(diǎn)是z的祖父的左孩子進(jìn)行討論，分為3種情況:

情況1：z的叔叔結(jié)點(diǎn)y是RED
處理：將y與z的父結(jié)點(diǎn)著為BLACK，z的祖父著為紅色，此時(shí)z的祖父可能違反性質(zhì)3，將z上移至祖父結(jié)點(diǎn)

情況1

情況2：z的叔叔結(jié)點(diǎn)y是BLACK，z是右孩子
處理：將z上移到父結(jié)點(diǎn)，對z左旋，轉(zhuǎn)化為情況3

情況2

情況3：z的叔叔結(jié)點(diǎn)y是BLACK，z是左孩子
處理：將z的父結(jié)點(diǎn)著為BLACK，z的祖父結(jié)點(diǎn)著為RED，對z的祖父結(jié)點(diǎn)右旋

情況3

4.2.2 過程模擬

插入過程請點(diǎn)擊這里

code:

void InsertFixup(Tree T, Node *z) {
    Node *y;
    //插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色時(shí)，違反性質(zhì)4
    while( z->parent->color == RED ) {
        if( z->parent->parent->left == z->parent ) {
            //y指向z的叔叔結(jié)點(diǎn)
            y=z->parent->parent->right;
            /*
             情況1:如果y為RED，將y與z的父結(jié)點(diǎn)著為BLACK，z的祖父著為紅色，此時(shí)z的祖父可能違反性質(zhì)3，將z上移至祖父結(jié)點(diǎn)
             */
            if(y->color == RED) {
                y->color=BLACK;
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            } else {
                /*
                 情況2：如果y為BLACK，且z是右孩子，將z上移到父結(jié)點(diǎn)，對z左旋，轉(zhuǎn)化為情況3
                 */
                if(z == z->parent->right) {
                    z=z->parent;
                    LeftRotate(T, z);
                }
                /*
                 情況3：如果y為BLACK，且z是左孩子，將z的父結(jié)點(diǎn)著為BLACK，z的祖父結(jié)點(diǎn)著為RED，對z的祖父結(jié)點(diǎn)右旋
                 */
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                RightRotate(T,z->parent->parent);
            }
        } else {
            //對稱，左右替換即可
            y=z->parent->parent->left;
            if( y->color == RED) {
                y->color=BLACK;
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            } else {
                if( z == z->parent->left) {
                    z=z->parent;
                    RightRotate(T,z);
                }
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                LeftRotate(T,z->parent->parent);
            }
        }
    }
    T->color=BLACK;
}

5 刪除

5.1 刪除過程

紅黑樹的刪除過程同樣是在二叉搜索樹刪除的基礎(chǔ)上改進(jìn)的。二叉搜索樹的刪除過程分為3種情況：①無左右孩子 ②有左孩子或右孩子 ③既有左孩子又有右孩子。在刪除過程中，如果刪除的結(jié)點(diǎn)為RED，并沒有破壞紅黑樹的性質(zhì)；如果刪除的結(jié)點(diǎn)為BLACK，破壞了紅黑樹的性質(zhì)，需要調(diào)整，從刪除結(jié)點(diǎn)y的唯一孩子結(jié)點(diǎn)x或是NIL處開始調(diào)整（這里做了轉(zhuǎn)換，實(shí)際刪除的是右子樹最小結(jié)點(diǎn)或左子樹最大結(jié)點(diǎn)）

code:

//右子樹最小結(jié)點(diǎn)
Node* Successor(Tree T, Node *x)
{
    if(x->right != NIL) {
        Node *p=x->right;
        while( p->left != NIL ) {
            p=p->left;
        }
        //右孩子中最小的結(jié)點(diǎn)
        return p;
    }
    return x;
}

void Delete(Tree T, Node *z) {
    Node *y;//指向?qū)⒁粍h除的結(jié)點(diǎn)
    Node *x;//指向?qū)⒁粍h除的結(jié)點(diǎn)的唯一兒子
    //如果有一個子結(jié)點(diǎn)為NIL，刪除當(dāng)前結(jié)點(diǎn)
    if(z->left == NIL || z->right == NIL){
        y=z;
    } else {
        //刪除左子樹的最大結(jié)點(diǎn)或右子樹最小結(jié)點(diǎn)
        y=Successor(T, z);//這里是右子樹最大結(jié)點(diǎn)
    }
    
    //開始刪除
    if(y->left != NIL) {
        x=y->left;
    } else {
        x=y->right;
    }
    if (x != NIL){
        x->parent=y->parent;
    }
    if( y->parent == NIL ) {
        T=x;
    } else {
        if( y == y->parent->left ) {
            y->parent->left=x;
        } else {
            y->parent->right=x;
        }
    }
    //交換值
    if( y != z ) {
        z->value=y->value;
    }
    //如果刪除的是黑色結(jié)點(diǎn)，進(jìn)行調(diào)整
    if( y->color == BLACK ) {
        //沒有修改y結(jié)點(diǎn)，任意屬性的值，可以使用
        DeleteFixup(T,NIL!=x ? x:y);
    }
}

5.2 調(diào)整過程

5.2.1 分析

如果被刪除結(jié)點(diǎn)y是黑色會產(chǎn)生的問題：①如果y是根，y的紅色孩子成為新根，違反性質(zhì)2。 ②如果x與y的父結(jié)點(diǎn)都是紅色，違反性質(zhì)4。 ③刪除y會導(dǎo)致之前包含y的任意路徑上的黑色結(jié)點(diǎn)少1，違反性質(zhì)5。
恢復(fù)過程需要根據(jù)x是左孩子還是右孩子進(jìn)行恢復(fù)，由于左右是對稱的，這里只討論x是左孩子的恢復(fù)過程

具體過程如下：從x結(jié)點(diǎn)開始循環(huán)，直到：

① x指向一個RED結(jié)點(diǎn)，此時(shí)將x著為BLACK
② x指向根，x若為RED，著為BLACK
③ 修改顏色 & 進(jìn)行旋轉(zhuǎn)

循環(huán)過程中，w為x的兄弟結(jié)點(diǎn)，由于x處之前刪除過黑色結(jié)點(diǎn)，所以w不可能為NIL，這里分為4種情況

情況1：x的兄弟w為RED
處理：由于x為BLACK且刪除了一個BLACK結(jié)點(diǎn)，所以w必有BLACK孩子。此時(shí)將w著為BLACK，x父結(jié)點(diǎn)著為RED，對x的父結(jié)點(diǎn)左旋。x的新兄弟結(jié)點(diǎn)w是BLACK，情況1轉(zhuǎn)換為情況2、3或4

情況1

情況2：x的兄弟w為BLACK，且w的兩個孩子都為BLACK
處理：w著為RED，x上移至父結(jié)點(diǎn)

情況2

情況3：x的兄弟w為BLACK，且w的左孩子為RED，右孩子為BLACK
處理：交換w與其左孩子的color，對w進(jìn)行右旋。旋轉(zhuǎn)后x的新兄弟w是一個有RED右孩子的BLACK結(jié)點(diǎn)，轉(zhuǎn)換成情況4

情況3

情況4：x的兄弟w為BLACK，且w的右孩子為RED
處理：將w著為x父結(jié)點(diǎn)的顏色，x父結(jié)點(diǎn)著為BLACK，w右孩子著為BLACK，對x的父結(jié)點(diǎn)左旋，x設(shè)為根結(jié)點(diǎn)（結(jié)束調(diào)整）

情況4

5.2.2 過程模擬

插入過程請點(diǎn)擊這里

code:

void DeleteFixup(Tree T, Node *x) {
    //x是RED直接跳出
    while( x != T && x->color == BLACK ) {
        //x為左子樹
        if(x == x->parent->left) {
            //w為x的兄弟結(jié)點(diǎn)
            Node *w=x->parent->right;
            /*
             情況1：如果w為RED，由于x為BLACK且刪除了一個BLACK結(jié)點(diǎn)，所以w必有BLACK孩子。
             此時(shí)將w著為BLACK，x父結(jié)點(diǎn)著為RED，對x的父結(jié)點(diǎn)左旋。x的新兄弟結(jié)點(diǎn)w是BLACK，情況1轉(zhuǎn)換為情況2、3或4
            */
            if(w->color == RED){
                w->color=BLACK;
                x->parent->color=RED;
                LeftRotate(T, x->parent);
                w=x->parent->right;
            }
            /*
             情況2：如果w為BLACK，w的左右孩子為BLACK。w著為RED，x上移至父結(jié)點(diǎn)
             */
            if(w->left->color == BLACK && w->right->color == BLACK) {
                w->color=RED;
                x=x->parent;
            } else {
                /*
                 情況3：如果w為BLACK，w的左孩子為RED，右孩子為BLACK。
                 交換w與其左孩子的color，對w進(jìn)行右旋。旋轉(zhuǎn)后x的新兄弟w是一個有RED右孩子的BLACK結(jié)點(diǎn)，轉(zhuǎn)換成情況4
                 */
                if(w->right->color == BLACK) {
                    w->color=RED;
                    w->left->color=BLACK;
                    RightRotate(T, w);
                    w=x->parent->right;
                }
                /*
                 情況4：如果w為BLACK，w的右孩子為RED。
                 將w著為x父結(jié)點(diǎn)的顏色，x父結(jié)點(diǎn)著為BLACK，w右孩子著為BLACK，對x的父結(jié)點(diǎn)左旋，x設(shè)為根結(jié)點(diǎn)
                 */
                w->color=x->parent->color;
                x->parent->color=BLACK;
                w->right->color=BLACK;
                LeftRotate(T,x->parent);
                x=T;
            }
        } else {
            //與前面對稱，不再詳述
            Node *w=x->parent->left;
            if(w->color == RED) {
                w->color=BLACK;
                x->parent->color=RED;
                RightRotate(T, x->parent);
                w=x->parent->left;
            }
            if(w->left->color == BLACK && w->right->color == BLACK) {
                w->color=RED;
                x=x->parent;
            } else {
                if(w->left->color == BLACK) {
                    w->color=RED;
                    w->right->color=BLACK;
                    LeftRotate(T, w);
                    w=x->parent->left;
                }
                w->color=x->parent->color;
                x->parent->color=BLACK;
                w->left->color=BLACK;
                RightRotate(T,x->parent);
                x=T;
            }
        }
    }
    x->color=BLACK;
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

紅黑樹

紅黑樹

1 摘要

2 性質(zhì)

3 旋轉(zhuǎn)

3.1 左旋

3.2 右旋

4 插入

4.1 插入過程

4.2.調(diào)整過程

4.2.1 分析

4.2.2 過程模擬

5 刪除

5.1 刪除過程

5.2 調(diào)整過程

5.2.1 分析

5.2.2 過程模擬

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

紅黑樹

1 摘要

2 性質(zhì)

3 旋轉(zhuǎn)

3.1 左旋

3.2 右旋

4 插入

4.1 插入過程

4.2.調(diào)整過程

4.2.1 分析

4.2.2 過程模擬

5 刪除

5.1 刪除過程

5.2 調(diào)整過程

5.2.1 分析

5.2.2 過程模擬

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av