C语言-手写红黑树

左手的ㄟ右手 2023-10-02 20:53 19阅读 0赞

### 前沿 ###

写C的红黑树前建议先看我博客这篇文章`Java-红黑树` 主要看原理

### 红黑树代码 ###

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

![在这里插入图片描述][241d60d901ab468c8532f2a2d4413093.gif]

点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复在本博客学习的技术不得以任何方式直接或者间接的从事违反中华人民共和国法律,内容仅供学习、交流与参考 免责声明：本文部分素材来源于网络，版权归原创者所有，如存在文章/图片/音视频等使用不当的情况，请随时私信联系我、以迅速采取适当措施，避免给双方造成不必要的经济损失。感谢,配合,希望我的努力对你有帮助^\_^

[241d60d901ab468c8532f2a2d4413093.gif]: https://img-blog.csdnimg.cn/241d60d901ab468c8532f2a2d4413093.gif