C語言實現手寫紅黑樹的示例代碼

#ifndef STUDY_RBTREE_H
#define STUDY_RBTREE_H
#include "charkvlinked.h"
typedef int boolean;//定義一個佈爾類型
#define TRUE 1
#define FALSE 0
enum COL{RED=0,BLACK=1};
typedef struct rBNode
{
    char *key; //元素key
    void *value; //元素值
    int color; //節點顏色
    struct rBNode *left;  //左孩子
    struct rBNode *right;  //右孩子
    struct rBNode *parent;  //父結點
}RBNode;

typedef  struct  rBTree{
     RBNode *root;  //根結點
    int size;  //結點數量
} RBTree;
#define  isRed(rBNode) ((rBNode != NULL) && (rBNode->color == RED)) ? TRUE : FALSE
#define  isBlack(rBNode) ((rBNode != NULL) && (rBNode->color == BLACK)) ? TRUE : FALSE
#define  colorOf(rBNode) rBNode != NULL ? rBNode->color : BLACK
#define  parentOf(rBNode) rBNode != NULL ? rBNode->parent : NULL
#define  setBlack(rBNode) rBNode != NULL ? rBNode->color = BLACK : NULL
#define  setRed(rBNode) rBNode != NULL ? rBNode->color = RED : NULL
#define  setParent(rBNode,replace) rBNode != NULL ? rBNode->parent = replace : NULL
#define  setColor(rBNode,parent) rBNode != NULL ? rBNode->color = colorOf(parent) : NULL
CharKvLinked * getAllKeyAndValueRbTree(RBTree * tree);
RBTree *createRBTree();
RBNode *createRbTreeNode(char *key, void *value);
void insertOrUpdateRBTreeKey(RBTree *tree, RBNode *node);
void insertRBTreeKeyRepetition(RBTree *tree, RBNode *node);
boolean isExistRbTree(RBTree *pTree, char *key);
RBNode *searchRbTree(RBTree *pTree, char *key);
RBNode *iterativeSearchRbTree(RBTree *pTree, char *key);
void removeRbTree(RBTree *tree, char *key);
void destroyRbTree(RBTree *tree) ;
#endif //STUDY_RBTREE_H

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


/*
 * 打印"紅黑樹"
 *
 * key        -- 節點的鍵值
 * direction  --  0，表示該節點是根節點;
 *               -1，表示該節點是它的父結點的左孩子;
 *                1，表示該節點是它的父結點的右孩子。
 */
static void printRbTree_(RBNode *node, char *data, int direction) {

    if (node != NULL) {
        int i = isRed(node);
        if (direction == 0)    // tree是根節點
        {
            printf("%s (%s) is root  他的左節點: %s,他的右節點:%s  ,他的內存地址是:%p\n", node->key, i ? "紅" : "黑",
                   node->left == NULL ? "NULL" : node->left->key,
                   node->right == NULL ? "NULL" : node->right->key, node);
        } else                // tree是分支節點
        {
            printf("%s (%s) 是 %s' 的 %s 子節點,他的左節點:%s ,他的右節點:%s ,他的內存地址是:%p\n",
                   node->key, i ? "紅" : "黑", data,
                   direction == 1 ? "right" : "left",
                   node->left == NULL ? "NULL" : node->left->key,
                   node->right == NULL ? "NULL" : node->right->key, node);


        }
        printRbTree_(node->left, node->key, -1);
        printRbTree_(node->right, node->key, 1);
    }
}

void printRbTreeNode(RBTree *root) {
    if (root->root != NULL) {
        printRbTree_(root->root, root->root->key, 0);
    }
}


/*
    * 對紅黑樹的節點(x)進行左旋轉
    *
    * 左旋示意圖(對節點x進行左旋)：
    *      px                              px
    *     /                               /
    *    x                               y
    *   /  \      --(左旋)-.             / \
    *  lx   y                          x  ry
    *     /   \                       /  \
    *    ly   ry                     lx  ly
    *
    *      px                              px
    *        \                               \
    *         x                               y
    *        /  \      --(左旋)-.             / \
    *       lx   y                          x  ry
    *          /   \                       /  \
    *         ly   ry                     lx  ly
    *
    *   沒有父節點的情況,也就表示x是根節點的情況
    *    x                               y
    *   /  \      --(左旋)-.             / \
    *  lx   y                          x  ry
    *     /   \                       /  \
    *    ly   ry                     lx  ly
    *
    * x                 y
    *  \              /   \
    *   y            x    ry
    *    \
    *     ry
    *
    *
    *
    */
static void leftRotateRbTree(RBTree *tree, RBNode *x) {
    if (x != NULL) {

        //1.獲取x的右孩子，即y
        RBNode *y = x->right;
        //2.將y的左孩子設置為x的右孩子
        x->right = y->left;
        // 左子樹不為空，需要更新父節點
        if (y->left != NULL) {
            y->left->parent = x;
        }
        // 3. 空出節點x的父節點
        y->parent = x->parent;
        //4.父節點指向右兒子
        if (x->parent == NULL) { // 右兒子成為新的根節點
            tree->root = y;
        } else if (x == x->parent->left) { // 右兒子成為父節點的左兒子
            x->parent->left = y;
        } else { // 右兒子成為父節點的右兒子
            x->parent->right = y;
        }
        //5. 節點x成為y的左子樹
        y->left = x;
        x->parent = y;

    }

}

/*
 * 對紅黑樹的節點(y)進行右旋轉
 *
 * 右旋示意圖(對節點y進行右旋)：
 *            py                               py
 *           /                                /
 *          y                                x
 *         /  \      --(右旋)-.              /  \
 *        x   ry                           lx   y
 *       / \                                   / \
 *      lx  rx                                rx  ry
 *
 *          py                                 py
 *            \                                 \
 *             y                                x
 *            /  \      --(右旋)-.              /  \
 *           x   ry                           lx   y
 *          / \                                   / \
 *         lx  rx                                rx  ry
 *
 *          y                                x
 *         /  \      --(右旋)-.              /  \
 *        x   ry                           lx   y
 *       / \                                   / \
 *      lx  rx                                rx  ry
 *
 *
 *
 *
 */
static void rightRotateRbTree(RBTree *tree, RBNode *y) {
    if (y != NULL) {
        // 記錄p的左兒子
        RBNode *x = y->left;
        // 1. 空出左兒子的右子樹
        y->left = x->right;
        // 右子樹不為空，需要更新父節點
        if (x->right != NULL) {
            x->right->parent = y;
        }

        // 2. 空出節點p的父節點
        x->parent = y->parent;
        // 父節點指向左兒子
        if (y->parent == NULL) { // 左兒子成為整棵樹根節點
            tree->root = x;
        } else if (y->parent->left == y) { // 左兒子成為父節點左兒子
            y->parent->left = x;
        } else { // 左兒子成為父節點的右兒子
            y->parent->right = x;
        }

        // 3. 順利會師
        x->right = y;
        y->parent = x;
    }


}


//創建紅黑樹
RBTree *createRBTree() {
    RBTree *tree = (RBTree *) malloc(sizeof(RBTree));
    tree->root = NULL;
    tree->size = 0;
    return tree;
}

//創建節點
RBNode *createRbTreeNode(char *key, void *value) {
    RBNode *node = (RBNode *) malloc(sizeof(RBNode));
    node->key = key;
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->color = RED;
    return node;
}


static void insertRbTreeFixUp(RBTree *tree, RBNode *node) {
    RBNode *parent, *gparent;
    // 若“父節點存在，並且父節點的顏色是紅色”
    while (((parent = parentOf(node)) != NULL) && isRed(parent)) {
        gparent = parentOf(parent);

        //若“父節點”是“祖父節點的左孩子”
        if (parent == gparent->left) {
            // Case 1條件：叔叔節點是紅色
            RBNode *uncle = gparent->right;
            if (isRed(uncle)) {
                setBlack(uncle);//父節點
                setBlack(parent);//叔節點
                setRed(gparent);//租節點
                node = gparent;
                continue;
            }

            // Case 2條件：叔叔是黑色，且當前節點是右孩子
            if (parent->right == node) {
                RBNode *tmp;
                leftRotateRbTree(tree, parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }
            // Case 3條件：叔叔是黑色，且當前節點是左孩子。
            setBlack(parent);
            setRed(gparent);
            rightRotateRbTree(tree, gparent);
        } else {    //若當前節點的父節點是當前節點的祖父節點的右孩子
            // Case 1條件：叔叔節點是紅色
            RBNode *uncle = gparent->left;
            if (isRed(uncle)) {
                setBlack(uncle);
                setBlack(parent);
                setRed(gparent);
                node = gparent;
                continue;
            }

            // Case 2條件：叔叔是黑色，且當前節點是左孩子
            if (parent->left == node) {
                RBNode *tmp;
                rightRotateRbTree(tree, parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            // Case 3條件：叔叔是黑色，且當前節點是右孩子。
            setBlack(parent);
            setRed(gparent);
            leftRotateRbTree(tree, gparent);
        }
    }
    // 將根節點設為黑色
    setBlack(tree->root);


}


static void insertRBTree(RBTree *tree, RBNode *node, int type) {
    int cmp;
    RBNode *y = NULL;
    RBNode *x = tree->root;

    // 1. 將紅黑樹當作一顆二叉查找樹，將節點添加到二叉查找樹中。
    while (x != NULL) {
        y = x;//拿到為NULL的上一個節點
        cmp = strcmp(node->key, x->key);
        if (cmp < 0) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    node->parent = y;
    if (y != NULL) {
        cmp = strcmp(node->key, y->key);
        if (cmp < 0) {
            y->left = node;
        } else if (cmp > 0) {
            y->right = node;
        } else {
            if (type == 1) {
                // 如果key相等，則更新value
                y->value = node->value;
            } else {
                //支持重復插入
                y->right = node;
            }
        }
    } else {
        tree->root = node;
    }

    // 2. 設置節點的顏色為紅色
    node->color = RED;

    // 3. 將它重新修正為一顆二叉查找樹
    insertRbTreeFixUp(tree, node);

    tree->size++;
}

//插入節點不允許重復插入,如果重復插入，則更新value
void insertOrUpdateRBTreeKey(RBTree *tree, RBNode *node) {
    insertRBTree(tree, node, 1);
}

//插入節點允許重復插入
void insertRBTreeKeyRepetition(RBTree *tree, RBNode *node) {
    insertRBTree(tree, node, 0);
}


/*
 * (遞歸實現)查找"紅黑樹x"中鍵值為key的節點
 */
static RBNode *searchRbTree_(RBNode *x, char *key) {
    if (x == NULL) {
        return x;
    }
    int cmp = strcmp(key, x->key);
    if (cmp < 0) {
        return searchRbTree_(x->left, key);
    } else if (cmp > 0) {
        return searchRbTree_(x->right, key);
    } else {
        return x;
    }
}

RBNode *searchRbTree(RBTree *pTree, char *key) {
    return searchRbTree_(pTree->root, key);
}

//判斷節點是否存在
boolean isExistRbTree(RBTree *pTree, char *key) {
    RBNode *node = searchRbTree(pTree, key);
    if (node == NULL) {
        return FALSE;
    } else {
        return TRUE;
    }
}

/*
 * (非遞歸實現)查找"紅黑樹x"中鍵值為key的節點
 */
RBNode *iterativeSearchRbTree_(RBNode *x, char *key) {
    while (x != NULL) {
        int cmp = strcmp(key, x->key);
        if (cmp < 0) {
            x = x->left;
        } else if (cmp > 0) {
            x = x->right;
        } else {
            return x;
        }
    }

    return x;
}

RBNode *iterativeSearchRbTree(RBTree *pTree, char *key) {
    return iterativeSearchRbTree_(pTree->root, key);
}

//獲取所有的key和value
void getAllKeyAndValueRbTree_(CharKvLinked *pLinked, RBNode *node) {
    if (node != NULL) {
        insertCharKvLinkedHeadNode(pLinked, createCharKvLinkedNode(node->key, node->value));
        getAllKeyAndValueRbTree_(pLinked, node->left);
        getAllKeyAndValueRbTree_(pLinked, node->right);
    }
}

//獲取所有的key和value
CharKvLinked *getAllKeyAndValueRbTree(RBTree *tree) {
    CharKvLinked *pLinked = createCharKvLinked();
    getAllKeyAndValueRbTree_(pLinked, tree->root);
    return pLinked;
}

/*
    * 紅黑樹刪除修正函數
    *
    * 在從紅黑樹中刪除插入節點之後(紅黑樹失去平衡)，再調用該函數；
    * 目的是將它重新塑造成一顆紅黑樹。
    *
    * 參數說明：
    *     node 待修正的節點
    */
static void removeRbTreeFixUp(RBTree *tree, RBNode *node, RBNode *parent) {
    RBNode *other;

    while ((node == NULL || isBlack(node)) && (node != tree->root)) {
        if (parent->left == node) {
            other = parent->right;
            if (isRed(other)) {
                // Case 1: x的兄弟w是紅色的
                setBlack(other);
                setRed(parent);
                leftRotateRbTree(tree, parent);
                other = parent->right;
            }

            if ((other->left == NULL || isBlack(other->left)) &&
                (other->right == NULL || isBlack(other->right))) {
                // Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的
                setRed(other);
                node = parent;
                parent = parentOf(node);
            } else {

                if (other->right == NULL || isBlack(other->right)) {
                    // Case 3: x的兄弟w是黑色的，並且w的左孩子是紅色，右孩子為黑色。
                    setBlack(other->left);
                    setRed(other);
                    rightRotateRbTree(tree, other);
                    other = parent->right;
                }
                // Case 4: x的兄弟w是黑色的；並且w的右孩子是紅色的，左孩子任意顏色。
                setColor(other, parent);
                setBlack(parent);
                setBlack(other->right);
                leftRotateRbTree(tree, parent);
                node = tree->root;
                break;
            }
        } else {

            other = parent->left;
            if (isRed(other)) {
                // Case 1: x的兄弟w是紅色的
                setBlack(other);
                setRed(parent);
                rightRotateRbTree(tree, parent);
                other = parent->left;
            }

            if ((other->left == NULL || isBlack(other->left)) &&
                (other->right == NULL || isBlack(other->right))) {
                // Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的
                setRed(other);
                node = parent;
                parent = parentOf(node);
            } else {

                if (other->left == NULL || isBlack(other->left)) {
                    // Case 3: x的兄弟w是黑色的，並且w的左孩子是紅色，右孩子為黑色。
                    setBlack(other->right);
                    setRed(other);
                    leftRotateRbTree(tree, other);
                    other = parent->left;
                }

                // Case 4: x的兄弟w是黑色的；並且w的右孩子是紅色的，左孩子任意顏色。
                setColor(other, parent);
                setBlack(parent);
                setBlack(other->left);
                rightRotateRbTree(tree, parent);
                node = tree->root;
                break;
            }
        }
    }

    if (node != NULL) {
        setBlack(node);
    }
}


static void removeRbTree_(RBTree *tree, RBNode *node) {
    RBNode *child, *parent;
    boolean color;

    // 被刪除節點的"左右孩子都不為空"的情況。
    if ((node->left != NULL) && (node->right != NULL)) {
        // 被刪節點的後繼節點。(稱為"取代節點")
        // 用它來取代"被刪節點"的位置，然後再將"被刪節點"去掉。
        RBNode *replace = node;

        // 獲取後繼節點
        replace = replace->right;
        while (replace->left != NULL) {
            replace = replace->left;
        }

        // "node節點"不是根節點(隻有根節點不存在父節點)
        if (parentOf(node) != NULL) {
            if (parentOf(node) == node) {
                (parentOf(node))->left = replace;
            } else {
                (parentOf(node))->right = replace;
            }
        } else {
            // "node節點"是根節點，更新根節點。
            tree->root = replace;
        }

        // child是"取代節點"的右孩子，也是需要"調整的節點"。
        // "取代節點"肯定不存在左孩子！因為它是一個後繼節點。
        child = replace->right;
        parent = parentOf(replace);
        // 保存"取代節點"的顏色
        color = colorOf(replace);

        // "被刪除節點"是"它的後繼節點的父節點"
        if (parent == node) {
            parent = replace;
        } else {
            // child不為空
            if (child != NULL) {
                setParent(child, parent);
            }
            parent->left = child;

            replace->right = node->right;
            setParent(node->right, replace);
        }

        replace->parent = node->parent;
        replace->color = node->color;
        replace->left = node->left;
        node->left->parent = replace;

        if (color == BLACK) {
            removeRbTreeFixUp(tree, child, parent);
        }

        node = NULL;
        return;
    }

    if (node->left != NULL) {
        child = node->left;
    } else {
        child = node->right;
    }

    parent = node->parent;
    // 保存"取代節點"的顏色
    color = node->color;

    if (child != NULL) {
        child->parent = parent;
    }

    // "node節點"不是根節點
    if (parent != NULL) {
        if (parent->left == node) {
            parent->left = child;
        } else {
            parent->right = child;
        }
    } else {
        tree->root = child;
    }

    if (color == BLACK) {
        removeRbTreeFixUp(tree, child, parent);
    }
    node = NULL;


}

/*
 * 刪除結點(z)，並返回被刪除的結點
 *
 * 參數說明：
 *     tree 紅黑樹的根結點
 *     z 刪除的結點
 */
void removeRbTree(RBTree *tree, char *key) {
    RBNode *node;
    if ((node = searchRbTree(tree, key)) != NULL) {
        removeRbTree_(tree, node);
        tree->size--;
    }
}

/*
 * 銷毀紅黑樹
 */
static void destroyRbTree_(RBNode *tree) {
    if (tree == NULL) {
        return;
    }
    if (tree->left != NULL) {
        destroyRbTree_(tree->left);
    }
    if (tree->right != NULL) {
        destroyRbTree_(tree->right);
    }
    free(tree);
}

void destroyRbTree(RBTree *tree) {
    destroyRbTree_(tree->root);
    free(tree);
}

//樹結構不建議使用迭代,我們可以使用前序,中序,後續遍歷來實現 需要自己寫代碼
//前序遍歷
//void preOrder(RBNode *tree) {
//    if (tree != NULL) {
//        printf("%s ", tree->key);
//        preOrder(tree->left);
//        preOrder(tree->right);
//    }
//}

int main() {
    RBTree *pTree = createRBTree();

    for (int i = 0; i < 10; i++) {
        char *str = (char *) malloc(sizeof(char) * 10);
        sprintf(str, "%d", i);
        insertOrUpdateRBTreeKey(pTree, createRbTreeNode(str, str));
    }

    printRbTreeNode(pTree);

    destroyRbTree(pTree);

}