二叉樹 -- 平衡二叉搜索樹

AVL樹

一、概念

AVL樹，也稱平衡二叉搜索樹，AVL樹是一棵二叉搜索樹，并且能通過一定的平衡處理機(jī)制保證二叉搜索樹的平衡，使得查詢效率更高。

特點(diǎn)：

  • AVL樹是一棵二叉搜索樹。
  • AVL樹的左右子結(jié)點(diǎn)也是AVL樹。
  • 每個結(jié)點(diǎn)的左右子結(jié)點(diǎn)的高度之差的絕對值最多為1，即平衡因子的范圍為[-1,1]。

平衡處理機(jī)制：
采用旋轉(zhuǎn)進(jìn)行平衡處理，一共有四種形式的旋轉(zhuǎn)：右單旋、左單旋、左右雙旋和右左雙旋。

AVL樹

二、數(shù)據(jù)結(jié)構(gòu)

struct AVLTreeNode {
    int value;
    int height;
    AVLTreeNode *left;
    AVLTreeNode *right;
};

三、相關(guān)操作

  • 插入
  • 刪除
  • 查找

AVL樹相關(guān)操作

四、實(shí)現(xiàn)

#include<stdio.h>
#include<malloc.h>

struct AVLTreeNode {
    int value;
    int height;
    AVLTreeNode *left;
    AVLTreeNode *right;
};

AVLTreeNode* makeEmpty(AVLTreeNode* T) {
    if (T != NULL) {
        makeEmpty(T->left);
        makeEmpty(T->right);
        free(T);
    }
    return NULL;
}

int height(AVLTreeNode* P) { //計算AVL結(jié)點(diǎn)高度
    if (P == NULL) {
        return -1;
    } else {
        return P->height;
    }
}

int max(int a, int b) { //獲取最大值
    return a > b ? a : b;
}

int absMinus(int a, int b) { //獲取相減后的絕對值
    int result;
    if(a >= b) {
        result = a - b;
    } else {
        result = b - a;
    }
    return result;
}

/* 左邊的結(jié)點(diǎn)單旋（即向右旋轉(zhuǎn)） */
AVLTreeNode* singleRotateWithLeft(AVLTreeNode* K2) {
    AVLTreeNode* K1;

    K1 = K2->left;
    K2->left = K1->right;
    K1->right = K2;

    K2->height = max(height(K2->left), height(K2->right)) + 1;
    K1->height = max(height(K1->left), K2->height) + 1;

    return K1;
}

/* 右邊的結(jié)點(diǎn)單旋（即向左旋轉(zhuǎn)） */
AVLTreeNode* singleRotateWithRight(AVLTreeNode* K2) {
    AVLTreeNode* K1;

    K1 = K2->right;
    K2->right = K1->left;
    K1->left = K2;

    K2->height = max(height(K2->left), height(K2->right)) + 1;
    K1->height = max(K2->height, height(K1->right)) + 1;

    return K1;
}

/* 左邊的結(jié)點(diǎn)雙旋（即先向左旋轉(zhuǎn)再向右旋轉(zhuǎn)） */
AVLTreeNode* doubleRotateWithLeft(AVLTreeNode* K3) {
    K3->left = singleRotateWithRight(K3->left);

    return singleRotateWithLeft(K3);
}

/* 右邊的結(jié)點(diǎn)雙旋（即先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)） */
AVLTreeNode* doubleRotateWithRight(AVLTreeNode* K3) {
    K3->right = singleRotateWithLeft(K3->right);

    return singleRotateWithRight(K3);
}

AVLTreeNode* insertALV(int X, AVLTreeNode* T) { //遞歸插入，返回根結(jié)點(diǎn)
    if (T == NULL) {
        T = (AVLTreeNode*)malloc(sizeof(AVLTreeNode));
        if (T == NULL) {
            printf("out of memory\n");
        } else {
            T->value = X;
            T->height = 0;
            T->left = T->right = NULL;
        }
    } else if (X < T->value) { /* 左子樹插入新結(jié)點(diǎn) */
        T->left = insertALV(X, T->left); //遞歸插入左子樹，返回根結(jié)點(diǎn)
        if (absMinus(height(T->left), height(T->right)) == 2)
            if (X < T->left->value)
                T = singleRotateWithLeft(T);
            else
                T = doubleRotateWithLeft(T);
    } else if (X > T->value) { /* 右子樹插入新結(jié)點(diǎn) */
        T->right = insertALV(X, T->right); //遞歸插入右子樹，返回根結(jié)點(diǎn)
        if (absMinus(height(T->left), height(T->right)) == 2)
            if (X > T->right->value)
                T = singleRotateWithRight(T);
            else
                T = doubleRotateWithRight(T);
    } else {
        printf("already exist\n");
    }

    T->height = max(height(T->left), height(T->right)) + 1; //更新根結(jié)點(diǎn)高度，左右子節(jié)點(diǎn)高度的最大值加1
    return T; //返回根結(jié)點(diǎn)
}

AVLTreeNode* deleteAVL(int X, AVLTreeNode* T) { //遞歸刪除，返回根結(jié)點(diǎn)
    if(T == NULL) {
        printf("find null\n");
    } else if (X < T->value) {
        T->left = deleteAVL(X, T->left); //遞歸刪除左子樹，返回根結(jié)點(diǎn)（當(dāng)前結(jié)點(diǎn)的右子樹結(jié)點(diǎn)高度比較大）
        if(absMinus(height(T->left), height(T->right)) == 2) {
            AVLTreeNode *p = T->right;
            if(height(p->left) > height(p->right)) { //當(dāng)前結(jié)點(diǎn)的右子樹結(jié)點(diǎn)的左子樹結(jié)點(diǎn)高度比較大，對右邊的結(jié)點(diǎn)雙旋
                T = doubleRotateWithRight(T);
            } else { //當(dāng)前結(jié)點(diǎn)的右子樹結(jié)點(diǎn)的右子樹結(jié)點(diǎn)高度比較大，對右邊的結(jié)點(diǎn)單旋
                T = singleRotateWithRight(T);
            }
        }
    } else if (X > T->value) { //遞歸刪除右子樹，返回根結(jié)點(diǎn)（當(dāng)前結(jié)點(diǎn)的左子樹結(jié)點(diǎn)高度比較大）
        T->right = deleteAVL(X, T->right);
        if(absMinus(height(T->left), height(T->right)) == 2) {
            AVLTreeNode *p = T->left;
            if(height(p->left) < height(p->right)) { //當(dāng)前結(jié)點(diǎn)的左子樹結(jié)點(diǎn)的右子樹結(jié)點(diǎn)高度比較大，對左邊的結(jié)點(diǎn)雙旋
                T = doubleRotateWithLeft(T);
            } else { //當(dāng)前結(jié)點(diǎn)的左子樹結(jié)點(diǎn)的左子樹結(jié)點(diǎn)高度比較大，對左邊的結(jié)點(diǎn)單旋
                T = singleRotateWithLeft(T);
            }
        }
    } else {
        if(T->left != NULL && T->right != NULL) { //待刪除的結(jié)點(diǎn)有兩個孩子結(jié)點(diǎn)
            if(height(T->left) > height(T->right)) { //當(dāng)前結(jié)點(diǎn)的左子樹結(jié)點(diǎn)高度比較大
                AVLTreeNode *p = T->left;
                while(p->right != NULL) { //尋找當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，用于刪除
                    p = p->right;
                }
                T->value = p->value;
                T->left = deleteAVL(p->value, T->left);
            } else { //當(dāng)前結(jié)點(diǎn)的右子樹結(jié)點(diǎn)高度比較大
                AVLTreeNode *p = T->right;
                while(p->left != NULL) { //尋找當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)，用于刪除
                    p = p->left;
                }
                T->value = p->value;
                T->right = deleteAVL(p->value, T->right);
            }
        } else if(T->left == NULL && T->right == NULL){ //待刪除的結(jié)點(diǎn)無孩子結(jié)點(diǎn)
            T = NULL;
        } else if(T->right == NULL) { //待刪除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)
            AVLTreeNode *p = T;
            T = T->left;
            free(p);
        } else { //待刪除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)
            AVLTreeNode *p = T;
            T = T->right;
            free(p);            
        }
    }

    if(T != NULL) {
        T->height = max(height(T->left), height(T->right)) + 1; //更新根結(jié)點(diǎn)高度，左右子節(jié)點(diǎn)高度的最大值加1
    }
    return T;
}

/* 查找X元素所在的位置 */
AVLTreeNode* findAVL(int X, AVLTreeNode* T) {
    if (T == NULL) {
        return NULL;
    } else if (X < T->value) {
        return findAVL(X, T->left);
    } else if (X > T->value) {
        return findAVL(X, T->right);
    } else {
        return T;
    }
}

/* 前序遍歷二叉樹 */
void preorderTravel(AVLTreeNode* T) {
    if (T != NULL) {
        printf("%d ", T->value);
        preorderTravel(T->left);
        preorderTravel(T->right);
    }
}

/* 中序遍歷二叉樹 */
void inorderTravel(AVLTreeNode* T) {
    if (T != NULL) {
        inorderTravel(T->left);
        printf("%d ", T->value);
        inorderTravel(T->right);
    }
}

/* 后序遍歷二叉樹 */
void postorderTravel(AVLTreeNode* T) {
    if (T != NULL) {
        postorderTravel(T->left);
        postorderTravel(T->right);
        printf("%d ", T->value);
    }
}

AVLTreeNode* findMin(AVLTreeNode* T) { //查找最小值
    if (T == NULL) {
        return NULL;
    } else if (T->left == NULL) {
        return T;
    } else {
        return findMin(T->left);
    }
}

AVLTreeNode* findMax(AVLTreeNode* T) { //查找最大值
    if (T == NULL) {
        return NULL;
    } else if (T->right == NULL) {
        return T;
    } else {
        return findMax(T->right);
    }
}

/* 先序遍歷打印二叉樹信息 */
void printTree(AVLTreeNode* T, int value, int direction) { 
    if (T != NULL) {
        if (direction == 0) {
            printf("%2d is root\n", T->value);
        } else {
            printf("%2d is %2d's %6s child\n", T->value, value, direction == 1 ? "right" : "left");
        }
        printTree(T->left, T->value, -1);
        printTree(T->right, T->value, 1);
    }
}

void main() {
    AVLTreeNode* T;

    T = makeEmpty(NULL);

    T = insertALV(5, T);
    T = insertALV(4, T);
    T = insertALV(7, T);
    T = insertALV(2, T);
    T = insertALV(6, T);
    T = insertALV(3, T);
    T = insertALV(8, T);
    T = insertALV(1, T);
    T = insertALV(9, T);
    T = insertALV(11, T);
    T = insertALV(10, T);

    printf("Root: %d\n", T->value);

    printf("樹的詳細(xì)信息: \n");
    printTree(T, T->value, 0);

    printf("前序遍歷二叉樹: ");
    preorderTravel(T);
    printf("\n");

    printf("中序遍歷二叉樹: ");
    inorderTravel(T);
    printf("\n");

    printf("后序遍歷二叉樹: ");
    postorderTravel(T);
    printf("\n");

    printf("最大值: %d\n", findMax(T)->value);
    printf("最小值: %d\n", findMin(T)->value);

    AVLTreeNode *node = findAVL(11, T);
    if(node == NULL) {
        printf("find null\n");
    } else {
        printf("find %d\n", node->value);
    }

    T = deleteAVL(10, T);
    T = deleteAVL(1, T);
    T = deleteAVL(2, T);
    T = deleteAVL(4, T);
    printf("樹的詳細(xì)信息: \n");
    printTree(T, T->value, 0);
}

紅黑樹

一、概念

紅黑樹（Red Black Tree）是一種自平衡二叉搜索樹。

特點(diǎn)：

  • 紅黑樹是一棵二叉搜索樹。
  • 每個結(jié)點(diǎn)是紅色或黑色。
  • 根結(jié)點(diǎn)是黑色。
  • 葉子結(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色。
  • 紅色結(jié)點(diǎn)的兩個子結(jié)點(diǎn)都是黑色（如果子結(jié)點(diǎn)是紅色，那么父結(jié)點(diǎn)一定是黑色）。
  • 從任意結(jié)點(diǎn)到其每個葉子結(jié)點(diǎn)的路徑包含相同數(shù)目的黑色結(jié)點(diǎn)。

平衡處理機(jī)制：
通過變色及旋轉(zhuǎn)保持黑結(jié)點(diǎn)平衡。

紅黑樹

二、數(shù)據(jù)結(jié)構(gòu)

struct RBTreeNode {
    int value;           //value
    bool isRed;          //結(jié)點(diǎn)顏色
    RBTreeNode *parent;  //父結(jié)點(diǎn)
    RBTreeNode *left;    //左子樹
    RBTreeNode *right;   //右子樹
};

三、相關(guān)操作

  • 插入
  • 查找
  • 刪除

紅黑樹相關(guān)操作-1
紅黑樹相關(guān)操作-2

四、實(shí)現(xiàn)

#include <stdio.h>
#include <malloc.h>

struct RBTreeNode {
    int value;          //value
    bool isRed;         //結(jié)點(diǎn)顏色
    RBTreeNode *parent; //父結(jié)點(diǎn)
    RBTreeNode *left;   //左子樹
    RBTreeNode *right;  //右子樹
};

/*定義葉子結(jié)點(diǎn)*/
RBTreeNode *nil;

/*獲取祖父結(jié)點(diǎn)*/
RBTreeNode* getAncestor(RBTreeNode* node) {
    if (node->parent == nil) {
        return NULL;
    } else {
        return node->parent->parent;
    }
}

/*獲取叔父結(jié)點(diǎn)*/
RBTreeNode* getUncle(RBTreeNode* node) {
    RBTreeNode* ancestor = getAncestor(node);
    if(ancestor == NULL || ancestor == nil) {
        return NULL;
    } else if (ancestor->left == node->parent) {
        return ancestor->right;
    } else {
        return ancestor->left;
    }
}

/*左旋*/
RBTreeNode* rotateLeft(RBTreeNode* root, RBTreeNode* node) {
    if(node->right != nil) {
        //當(dāng)前結(jié)點(diǎn)的右結(jié)點(diǎn)
        RBTreeNode* right = node->right;
        node->right = right->left;
        if (right->left != nil) {
            right->left->parent = node;
        }
        right->parent = node->parent;

        if (node->parent == nil) {
            //node本來為根結(jié)點(diǎn)，此時變化為原來node的右結(jié)點(diǎn)
            root = right;
        } else {
            if (node == node->parent->left) {
                node->parent->left = right;
            } else {
                node->parent->right = right;
            }
        }
        right->left = node;
        node->parent = right;
    }
    return root;
}

/*右旋*/
RBTreeNode* rotateRight(RBTreeNode* root, RBTreeNode* node) {
    if (node->left != nil) {
        //當(dāng)前結(jié)點(diǎn)的左結(jié)點(diǎn)
        RBTreeNode* left = node->left;
        node->left = left->right;
        if (left->right != nil) {
            left->right->parent = node;
        }
        left->parent = node->parent;
        if (node->parent == nil) {
            //node本來為根結(jié)點(diǎn)，此時變化為原來node的左結(jié)點(diǎn)
            root = left;
        } else {
            if (node == node->parent->left) {
                node->parent->left = left;
            } else {
                node->parent->right = left;
            }
        }
        left->right = node;
        node->parent = left;
    }
    return root;
}

/*插入修復(fù)*/
RBTreeNode*  fixInsert(RBTreeNode* root, RBTreeNode* node) {
    RBTreeNode* uncle;
    while(node->parent->isRed == true) {
        RBTreeNode* ancestor = getAncestor(node);
        if(node->parent == ancestor->left) {
            uncle = ancestor->right; //獲取叔父結(jié)點(diǎn)
            if (uncle->isRed == true) { //case 1 如果叔父結(jié)點(diǎn)為紅色(此時祖父結(jié)點(diǎn)一定為黑),則把父結(jié)點(diǎn)和叔父結(jié)點(diǎn)著黑,祖父結(jié)點(diǎn)著紅,node上移到祖父結(jié)點(diǎn)
                uncle->isRed = false;
                node->parent->isRed = false;
                ancestor->isRed = true;
                node = ancestor;
            } else {
                if (node == node->parent->right) { //case 3 如果叔父結(jié)點(diǎn)為黑色, node為右結(jié)點(diǎn), 循環(huán)變量node變?yōu)閚ode的父親結(jié)點(diǎn),左旋轉(zhuǎn)變化后的node結(jié)點(diǎn), 變?yōu)閏ase2的情況
                    node = node->parent;
                    root = rotateLeft(root, node);
                }
                //case 2 叔父結(jié)點(diǎn)為黑色,且node為左結(jié)點(diǎn),node的父結(jié)點(diǎn)著黑,node的祖父著紅,然后旋轉(zhuǎn)node的祖父結(jié)點(diǎn)
                node->parent->isRed = false;
                ancestor->isRed = true;
                root = rotateRight(root, ancestor);
            }
        } else { //對稱 修復(fù)同上
            uncle = ancestor->left;
            if (uncle->isRed == true) {
                uncle->isRed = false;
                node->parent->isRed = false;
                ancestor->isRed = true;
                node = ancestor;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    root = rotateRight(root, node);
                }
                node->parent->isRed = false;
                ancestor->isRed = true;
                root = rotateLeft(root, ancestor);
            }
        }
    }
    //case 1中可能會把node變?yōu)閞oot，并將node設(shè)置成紅色，故需要此步確保正確
    root->isRed = false;
    return root;
}

/*通過value插入一個結(jié)點(diǎn)*/
RBTreeNode* addNodeByValue(RBTreeNode* root, int value) {
    if (root == NULL) {
        root = (RBTreeNode*)malloc(sizeof(RBTreeNode));
        //初始化nil結(jié)點(diǎn)
        nil = (RBTreeNode*)malloc(sizeof(RBTreeNode));
        nil->isRed = false;
        //設(shè)置結(jié)點(diǎn)的指向
        root->parent = nil;
        root->left = nil;
        root->right = nil;
        //設(shè)置結(jié)點(diǎn)屬性,value 和color
        root->value = value;
        root->isRed = false;
    } else {
        RBTreeNode* node = root;
        /*插入結(jié)點(diǎn)的父結(jié)點(diǎn)*/
        RBTreeNode* p = nil;
        while (node != nil) {
            p = node;
            if(value > node->value) {
                node = node->right;
            } else if (value < node->value) {
                node = node->left;
            } else {
                return root;
            }
        }
        node = (RBTreeNode*)malloc(sizeof(RBTreeNode));
        node->parent = p;
        node->left = nil;
        node->right = nil;

        node->value = value;
        node->isRed = true;
        if (value < p->value) {
            p->left = node;
        } else {
            p->right = node;
        }
        root = fixInsert(root, node);
    }
    return root;
}

/*查找實(shí)際要刪除的結(jié)點(diǎn)*/
RBTreeNode* getRealRemoveNode(RBTreeNode* root, RBTreeNode* node) {
    //查找右結(jié)點(diǎn)的最小結(jié)點(diǎn)
    RBTreeNode* p = node->right;
    while (p->left != nil) {
        p = p->left;
    }
    return p;
}

/*查找某個結(jié)點(diǎn)*/
RBTreeNode* findNodeByValue(RBTreeNode* node, int value) {
    if (node == nil) {
        return NULL;
    }

    if (node->value < value) {
        return findNodeByValue(node->right, value);
    } else if (node->value > value) {
        return findNodeByValue(node->left, value);
    } else {
        return node;
    }
}

/*刪除修復(fù)*/
RBTreeNode* fixRemove(RBTreeNode* root, RBTreeNode* node) {
    while (node != root && node->isRed == false) { //循環(huán)結(jié)束條件為：node為根結(jié)點(diǎn)或者node結(jié)點(diǎn)為紅色
        if (node == node->parent->left) {
            RBTreeNode* brother = node->parent->right; //brother為node的兄弟結(jié)點(diǎn)
            if (brother->isRed == true) { //case 1 兄弟結(jié)點(diǎn)為紅色（先讓兄弟結(jié)點(diǎn)變黑色）
                brother->isRed = false;
                node->parent->isRed = true;
                root = rotateLeft(root, node->parent);
                brother = node->parent->right; //brother一定為黑色，因?yàn)閚ode->parent為紅色
            }

            //brother一定為黑色
            if (brother == nil) { //兄弟結(jié)點(diǎn)為葉子結(jié)點(diǎn)，說明當(dāng)前結(jié)點(diǎn)也為葉子結(jié)點(diǎn)，循環(huán)結(jié)束。
                break;
            } else if (brother->left->isRed == false && brother->right->isRed == false) { //case2 兄弟結(jié)點(diǎn)的兩個子結(jié)點(diǎn)都為黑
                brother->isRed = true;
                node = node->parent;
            } else if (brother->left->isRed == true) { //case3 兄弟結(jié)點(diǎn)的左子樹為紅色,右子樹為黑色
                brother->isRed = true;
                brother->left->isRed = false;
                root = rotateRight(root, brother);
                brother = node->parent->right;
            } else {
                //case 4 兄弟結(jié)點(diǎn)的右子樹為紅色
                brother->isRed = node->parent->isRed;
                node->parent->isRed = false;
                brother->right->isRed = false;
                root = rotateLeft(root, node->parent);
                node = root; //循環(huán)的出口
            }
        } else { //對稱 修復(fù)同上
            RBTreeNode* brother = node->parent->left;
            if (brother->isRed == true) { //case 1
                brother->isRed = false;
                node->parent->isRed = true;
                root = rotateRight(root, node->parent);
                brother = node->parent->left;
            }

            if (brother == nil) {
                break;
            } else if (brother->left->isRed == false && brother->right->isRed == false) { //case 2
                brother->isRed = true;
                node = node->parent;
            } else if (brother->right->isRed == true) { //case 3
                brother->isRed = true;
                brother->right->isRed = false;
                root = rotateLeft(root, brother);
                brother = node->parent->left;
            } else { //case 4
                brother->isRed = node->parent->isRed;
                node->parent->isRed = false;
                brother->left->isRed = false;
                root = rotateRight(root, node->parent);
                node = root; //循環(huán)的出口
            }
        }
    }

    //case 2中，當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的兩個子結(jié)點(diǎn)都為黑色，將兄弟結(jié)點(diǎn)設(shè)置為紅色（即兄弟結(jié)點(diǎn)所在子樹黑色結(jié)點(diǎn)數(shù)減1，與當(dāng)前結(jié)點(diǎn)所在子樹黑色結(jié)點(diǎn)數(shù)保持平衡），此時還需要將當(dāng)前結(jié)點(diǎn)上升到父結(jié)點(diǎn)繼續(xù)處理黑色結(jié)點(diǎn)數(shù)的平衡。
    //當(dāng)前結(jié)點(diǎn)上升到父結(jié)點(diǎn)后，如果該結(jié)點(diǎn)為紅色，則結(jié)束循環(huán)，并將該結(jié)點(diǎn)設(shè)置為黑色即可（當(dāng)前結(jié)點(diǎn)所在子樹黑色結(jié)點(diǎn)數(shù)加1，與刪除時減1保持了平衡）。
    node->isRed = false; 
    return root;
}

RBTreeNode* removeNode(RBTreeNode* root, RBTreeNode* node) {
    if (node == NULL) {
        return root;
    }

    RBTreeNode* y; //實(shí)際要刪除的結(jié)點(diǎn)
    RBTreeNode* x; //實(shí)際要刪除結(jié)點(diǎn)的子結(jié)點(diǎn)
    if (node->left == nil || node->right == nil) {
        y = node;
    } else {
        y = getRealRemoveNode(root, node);
    }

    if (y->left != nil) {
        x = y->left;
    } else {
        x = y->right;
    }
    //注意：當(dāng)結(jié)點(diǎn)y無左右子結(jié)點(diǎn)時，其子結(jié)點(diǎn)x為葉子結(jié)點(diǎn)nil

    //刪除結(jié)點(diǎn)y
    //if(x != nil) { 
    //注意：該判斷條件需要去掉。
    //雖然葉子結(jié)點(diǎn)nil無父結(jié)點(diǎn)，但是對于刪除操作，需要通過被刪除結(jié)點(diǎn)（y）的子結(jié)點(diǎn)（x）,找到結(jié)點(diǎn)（y）被刪除后，子結(jié)點(diǎn)（x）的兄弟結(jié)點(diǎn)。
    //而子結(jié)點(diǎn)（x）的兄弟結(jié)點(diǎn)是通過子結(jié)點(diǎn)（x）的父結(jié)點(diǎn)查找的，因此即使子節(jié)點(diǎn)（x）為葉子結(jié)點(diǎn)（nil），也需要有父指針。
        x->parent = y->parent; 
    //}
    if (y->parent == nil) { //刪除的是根結(jié)點(diǎn)
        if(x == nil) { //根結(jié)點(diǎn)無子結(jié)點(diǎn)
            free(root);
            free(nil);
            return NULL;
        } else { //根結(jié)點(diǎn)有子結(jié)點(diǎn)
            root = x;
        }
    } else { //刪除的不是根結(jié)點(diǎn)
        if (y == y->parent->left) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }
    }

    if (y != node) {
        //替換node和y的value
        //由于本來要刪除node，現(xiàn)在轉(zhuǎn)換為刪除node右結(jié)點(diǎn)的最小結(jié)點(diǎn)y，再把node的value換為y的value即可
        node->value = y->value;
    }

    //如果刪除的結(jié)點(diǎn)是黑色,違法了性質(zhì)5,要進(jìn)行刪除修復(fù)
    if (y->isRed == false) {
        root = fixRemove(root, x);
    }

    free(y);
    return root;
}

RBTreeNode* removeNodeByValue(RBTreeNode* root, int value) {
    //root為指向根結(jié)點(diǎn)的指針
    root = removeNode(root, findNodeByValue(root, value));
    return root;
}

/*打印結(jié)點(diǎn)，先序遍歷*/
void printRBTree(RBTreeNode* root) {
    if (root != nil && root != NULL) {
        printf("%d (%s)\n", root->value, root->isRed ? "紅" : "黑");
        printRBTree(root->left);
        printRBTree(root->right);
    }
}

void main() {
    RBTreeNode* root = NULL;
    
    root = addNodeByValue(root, 5);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 4);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 7);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 2);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 6);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 3);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 8);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 1);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 9);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 11);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 10);
    printRBTree(root);
    printf("\n");

    root = removeNodeByValue(root, 1);
    printRBTree(root);
    printf("\n");
    root = removeNodeByValue(root, 2);
    printRBTree(root);
    printf("\n");
    root = removeNodeByValue(root, 9);
    printRBTree(root);
    printf("\n");
    root = removeNodeByValue(root, 7);
    printRBTree(root);
    printf("\n");
    root = removeNodeByValue(root, 8);
    printRBTree(root);
    printf("\n");
    

    /*
    root = addNodeByValue(root, 5);
    printRBTree(root);
    printf("\n");
    root = addNodeByValue(root, 6);
    printRBTree(root);
    printf("\n");
    root = removeNodeByValue(root, 5);
    printRBTree(root);
    printf("\n");
    root = removeNodeByValue(root, 6);
    printRBTree(root);
    printf("\n");
    */
}

紅黑樹與AVL樹的比較

  • AVL樹要求任意結(jié)點(diǎn)的左右子樹的高度差的絕對值小于等于1，插入和刪除結(jié)點(diǎn)時通過結(jié)點(diǎn)旋轉(zhuǎn)保持樹的平衡。而紅黑樹則要求黑色結(jié)點(diǎn)數(shù)保持平衡，插入和刪除結(jié)點(diǎn)時通過結(jié)點(diǎn)旋轉(zhuǎn)和變色保持樹的平衡。
  • AVL樹的最大高度為1.44logn。而紅黑樹的最大高度為2log(n+1)，對于給定的黑色高度為N的紅黑樹，從根到葉子節(jié)點(diǎn)的最短路徑長度為N-1，最長路徑長度為2*(N-1)。
  • 對于插入結(jié)點(diǎn)導(dǎo)致樹失衡的情況，紅黑樹和AVL樹都是最多2次結(jié)點(diǎn)旋轉(zhuǎn)來實(shí)現(xiàn)復(fù)衡，旋轉(zhuǎn)的量級是O(1)。
  • 對于刪除結(jié)點(diǎn)導(dǎo)致樹失衡的情況，AVL樹需要維護(hù)從被刪除結(jié)點(diǎn)到根節(jié)點(diǎn)這條路徑上所有結(jié)點(diǎn)的平衡，旋轉(zhuǎn)的量級為O(logn)。而紅黑樹最多只需要旋轉(zhuǎn)3次實(shí)現(xiàn)復(fù)衡，旋轉(zhuǎn)的量級為O(1)。
  • 在實(shí)際應(yīng)用中，如果搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除的次數(shù)，那么選擇AVL樹。如果搜索、插入和刪除的次數(shù)幾乎差不多，那么選擇紅黑樹。
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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