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>



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);
    }
}



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;

    }

}


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);
}



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;
    }
}


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;
}


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;


}


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);

}