本篇内容介绍了“怎么用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); }
“怎么用C语言实现手写红黑树”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。