C++實現(xiàn)紅黑樹應(yīng)用實例代碼

更新時間：2021年11月01日 15:03:41 作者：去偽存真

紅黑樹它一種特殊的二叉查找樹,這意味著它滿足二叉查找樹的特征,但是也有許多自己的特性,這篇文章主要給大家介紹了關(guān)于C++實現(xiàn)紅黑樹的相關(guān)資料,需要的朋友可以參考下

紅黑樹的應(yīng)用：

1、利用key_value對，快速查找，O(logn)

socket與客戶端id之間，形成映射關(guān)系(socket, id)
內(nèi)存分配管理
1. 一整塊內(nèi)存，不斷分配小塊
2. 每分配一次，就加入到紅黑樹
3. 釋放的時候，在紅黑樹找到相應(yīng)的塊，然后去釋放

2、利用紅黑樹中序遍歷是順序的特性

進程的調(diào)度
1. 進程處于等待狀態(tài)，每個進程都有等待的時間，在未來某個時刻會運行，將這些進程利用紅黑樹組織起來
2. 在某個時刻，找到對應(yīng)時刻的節(jié)點，然后中序遍歷，就可以把該節(jié)點之前的節(jié)點全部運行到。

3、nginx定時器

為什么使用紅黑樹不使用哈希表？

極少情況下，需要key是有序的，如定時器

二叉排序樹（bstree）

左子樹 < 根 < 右子樹
中序遍歷結(jié)果是順序的
極端情況下，如果順序插入，結(jié)果就成了鏈表
1. 為了解決這個問題，引入了紅黑樹

紅黑樹性質(zhì)

每個節(jié)點是紅色的或黑色的
根節(jié)點是黑色的
葉子節(jié)點是黑色的
紅色節(jié)點的兩個子節(jié)點必須是黑色的
對每個節(jié)點，該節(jié)點到其子孫節(jié)點的所有路徑上的包含相同數(shù)目的黑節(jié)點（黑高相同）
1. 最短路徑就是全黑
2. 最長路徑就是黑紅相間

如何證明紅黑樹的正確性？

采用歸納法

左旋與右旋

改變?nèi)齻€方向，六根指針

紅黑樹的插入：

插入節(jié)點的時候，原先的樹是滿足紅黑樹性質(zhì)的
插入節(jié)點的顏色是紅色更容易滿足紅黑樹的性質(zhì)
插入的節(jié)點是紅色，且其父節(jié)點也是紅色的時候，需要調(diào)整

插入有三種情況：

叔父節(jié)點是紅色
叔父節(jié)點是黑色，且祖父節(jié)點，父節(jié)點和插入節(jié)點不是一條直線
叔父節(jié)點是黑色，且祖父節(jié)點，父節(jié)點和插入節(jié)點是一條直線

平衡二叉樹：

內(nèi)部不是color，而是一個high記錄高度，如果左右子樹高度相差超過1，就需要調(diào)整。

紅黑樹的刪除：

什么是刪除節(jié)點? y-> y是z的后繼節(jié)點
什么是軸心節(jié)點? x是y的右子樹
1. 如果x是紅色，把x變成黑色
2. 如果x是黑色，需要進行調(diào)整

刪除y節(jié)點，是什么顏色的時候需要調(diào)整？

黑色需要調(diào)整，刪除黑色破壞了黑高

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

#define RED                1
#define BLACK             2

typedef int KEY_TYPE;

typedef struct _rbtree_node {
    unsigned char color;
    struct _rbtree_node *right;
    struct _rbtree_node *left;
    struct _rbtree_node *parent;
    KEY_TYPE key;
    void *value;
} rbtree_node;

typedef struct _rbtree {
    rbtree_node *root;
    rbtree_node *nil;
} rbtree;

rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {
    while (x->left != T->nil) {
        x = x->left;
    }
    return x;
}

rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) {
    while (x->right != T->nil) {
        x = x->right;
    }
    return x;
}

rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {
    rbtree_node *y = x->parent;

    if (x->right != T->nil) {
        return rbtree_mini(T, x->right);
    }

    while ((y != T->nil) && (x == y->right)) {
        x = y;
        y = y->parent;
    }
    return y;
}


void rbtree_left_rotate(rbtree *T, rbtree_node *x) {

    rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right

    x->right = y->left; //1 1
    if (y->left != T->nil) { //1 2
        y->left->parent = x;
    }

    y->parent = x->parent; //1 3
    if (x->parent == T->nil) { //1 4
        T->root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }

    y->left = x; //1 5
    x->parent = y; //1 6
}


void rbtree_right_rotate(rbtree *T, rbtree_node *y) {

    rbtree_node *x = y->left;

    y->left = x->right;
    if (x->right != T->nil) {
        x->right->parent = y;
    }

    x->parent = y->parent;
    if (y->parent == T->nil) {
        T->root = x;
    } else if (y == y->parent->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }

    x->right = y;
    y->parent = x;
}

void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {

    while (z->parent->color == RED) { //z ---> RED
        if (z->parent == z->parent->parent->left) {
            rbtree_node *y = z->parent->parent->right;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent; //z --> RED
            } else {

                if (z == z->parent->right) {
                    z = z->parent;
                    rbtree_left_rotate(T, z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_right_rotate(T, z->parent->parent);
            }
        }else {
            rbtree_node *y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent; //z --> RED
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rbtree_right_rotate(T, z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_left_rotate(T, z->parent->parent);
            }
        }
        
    }

    T->root->color = BLACK;
}


void rbtree_insert(rbtree *T, rbtree_node *z) {

    rbtree_node *y = T->nil;
    rbtree_node *x = T->root;

    while (x != T->nil) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else if (z->key > x->key) {
            x = x->right;
        } else { //Exist
            return ;
        }
    }

    z->parent = y;
    if (y == T->nil) {
        T->root = z;
    } else if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }

    z->left = T->nil;
    z->right = T->nil;
    z->color = RED;

    rbtree_insert_fixup(T, z);
}

void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {

    while ((x != T->root) && (x->color == BLACK)) {
        if (x == x->parent->left) {

            rbtree_node *w= x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;

                rbtree_left_rotate(T, x->parent);
                w = x->parent->right;
            }

            if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {

                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rbtree_right_rotate(T, w);
                    w = x->parent->right;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rbtree_left_rotate(T, x->parent);

                x = T->root;
            }

        } else {

            rbtree_node *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rbtree_right_rotate(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->right->color = BLACK;
                    w->color = RED;
                    rbtree_left_rotate(T, w);
                    w = x->parent->left;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rbtree_right_rotate(T, x->parent);

                x = T->root;
            }

        }
    }

    x->color = BLACK;
}

rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {

    rbtree_node *y = T->nil;
    rbtree_node *x = T->nil;

    if ((z->left == T->nil) || (z->right == T->nil)) {
        y = z;
    } else {
        y = rbtree_successor(T, z);
    }

    if (y->left != T->nil) {
        x = y->left;
    } else if (y->right != T->nil) {
        x = y->right;
    }

    x->parent = y->parent;
    if (y->parent == T->nil) {
        T->root = x;
    } else if (y == y->parent->left) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }

    if (y != z) {
        z->key = y->key;
        z->value = y->value;
    }

    if (y->color == BLACK) {
        rbtree_delete_fixup(T, x);
    }

    return y;
}

rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {

    rbtree_node *node = T->root;
    while (node != T->nil) {
        if (key < node->key) {
            node = node->left;
        } else if (key > node->key) {
            node = node->right;
        } else {
            return node;
        }    
    }
    return T->nil;
}


void rbtree_traversal(rbtree *T, rbtree_node *node) {
    if (node != T->nil) {
        rbtree_traversal(T, node->left);
        printf("key:%d, color:%d\n", node->key, node->color);
        rbtree_traversal(T, node->right);
    }
}

int main() {

    int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};

    rbtree *T = (rbtree *)malloc(sizeof(rbtree));
    if (T == NULL) {
        printf("malloc failed\n");
        return -1;
    }
    
    T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));
    T->nil->color = BLACK;
    T->root = T->nil;

    rbtree_node *node = T->nil;
    int i = 0;
    for (i = 0;i < 20;i ++) {
        node = (rbtree_node*)malloc(sizeof(rbtree_node));
        node->key = keyArray[i];
        node->value = NULL;

        rbtree_insert(T, node);
        
    }

    rbtree_traversal(T, T->root);
    printf("----------------------------------------\n");

    for (i = 0;i < 20;i ++) {

        rbtree_node *node = rbtree_search(T, keyArray[i]);
        rbtree_node *cur = rbtree_delete(T, node);
        free(cur);

        rbtree_traversal(T, T->root);
        printf("----------------------------------------\n");
    }
  
}

總結(jié)

到此這篇關(guān)于C++實現(xiàn)紅黑樹的文章就介紹到這了,更多相關(guān)C++實現(xiàn)紅黑樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: