数据结构之-红黑树的实现(C语言版)
程序员文章站
2024-01-09 22:03:40
...
二叉查找树的效率依赖于其高度,为O(h),普通的具有N个结点的二叉查找树树的高度落差会很大,极端情况下会出现h=n的情况(插入结点序列为排好序的情况下),这样二叉查找树就退化为一个列表了。于是就出现了平衡树的概念,它能保证树的高度h在lgn这个数量级上。
红黑树是许多“平衡树”中的一种,它确保没有一条路径比其他的路径长出2倍左右,因而是接*衡的。
红黑树的数据结构和操作定义如下:
红黑树的操作中,只有插入和查找需不同于普通2二叉树,此处给出插入和查找的实现:
测试代码如下:
完整的代码见附件,写实现花了2天时间,终于搞定并理解了,-_-
红黑树是许多“平衡树”中的一种,它确保没有一条路径比其他的路径长出2倍左右,因而是接*衡的。
红黑树的数据结构和操作定义如下:
/*file:RBTree.h*/ #ifndef CHIYX_RBTREE_ #define CHIYX_RBTREE_ #ifndef NULL #define NULL 0 #endif #define BOOL int #define TRUE 1 #define FALSE 0 /* * 红黑树是满足如下性质的一棵二叉查找树: * (1) 每个结点只能是红黑或者黑色结点中的一种 * (2) 根结点是黑色的 * (3) 叶子结点是黑色的(具体实现可以定义个空结点或者NULL默认表示为叶子结点) * (4) 如果一个结点是红色的,则它的孩子结点为黑色 * (5) 对每个结点而言,从这个结点到叶子结点的任意路径上具有相同数目的黑色结点 */ /* * 红黑树的特点(也是红黑树是一棵好的二叉查找树的原因): * 一棵具有n个内结点(即真正的数据结点)的红黑树的黑高度bh至多为2lg(n+1) * 证明: 先求证:一棵以x的根的红黑树中至少包含2(hb(x))(指数) - 1 个内结点 * (1) 如果x的高度为0,则 x至少包含 2的0次方 - 1 = 0 个内结点,成立。 * (2) 若x有子树,则其子树的黑高度为 bh(x) (孩子节点为黑色时),或者bh(x) -1(孩子结点为红色或者黑色时) * (3) 因为x的孩子的黑高度小于x的黑高度,利用归纳假设,可以得出每个孩子至少包含2的 bh(x) -1 次方 - 1 * (4) 于是以x为根的子树至少包含 2 (bh(x) -1 次方) - 1 + 2 (bh(x) -1 次方) - 1 + 1 = 2 (bh(x)次方) - 1 个内结点 * 又根据性质(4),树的黑高度至少为 h / 2 , 所以 n >= 2 (h / 2 次方) - 1 => h <= 2 lg (n - 1) */ /*定义颜色类型*/ typedef enum color_t { RED = 0, BLACK = 1 }color_t; //定义数据类型 typedef int data_t; //定义红黑树的节点结构 typedef struct RBTreeNode { data_t data; color_t color; RBTreeNode *left; RBTreeNode *right; RBTreeNode *parent; }RBTreeNode, *RBTree; //查找操作,不存在返回NULL RBTreeNode *rbSearch(RBTree *rbTree, data_t key); //返回最小结点 RBTreeNode *rbMinImum(RBTree *rbTree); //返回最大结点 RBTreeNode *rbMaxImum(RBTree *rbTree); //返回x的后继结点 RBTreeNode *rbSuccessor(RBTreeNode *x); //返回x的前驱结点 RBTreeNode *rbPredecessor(RBTreeNode *x); //插入结点 BOOL rbInsertNode(RBTree *rbTree, data_t data); //删除第一个值为data的结点 BOOL rbDeleteNode(RBTree *rbTree, data_t data); //中序遍历 void rbInorderTraversal(RBTree *rbTree, void (*visitor)(RBTreeNode *node)); #endif
红黑树的操作中,只有插入和查找需不同于普通2二叉树,此处给出插入和查找的实现:
/* * 二叉查找树的左旋操作,该操作要求x的右子树不为空 */ static void rbTreeLeftRotate(RBTree *rbTree, RBTreeNode *x); /* * 二叉查找树的右旋操作,该操作要求x的左子树不为空 */ static void rbTreeRightRotate(RBTree *rbTree, RBTreeNode *x); /* * 当插入一个节点后,用此过程来保持红黑树的性质 */ static void rbTreeInsertFixup(RBTree *rbTree, RBTreeNode *x); /* * 当删除一个结点时,通过此过程保持红黑树的性质 */ static void rbTreeDeleteFixup(RBTree *rbTree, RBTreeNode *parent, RBTreeNode *x); //插入操作 //1. 新创建的结点,颜色为红色 //2. 插入一个结点后,有可能破坏红黑树的性质,则必须对树作相应的调整,以便保持红黑树的性质 BOOL rbInsertNode(RBTree *rbTree, data_t data) { //1. 创建一个新结点 RBTreeNode *node, *p, *curNode; node = (RBTreeNode *)malloc(sizeof(RBTreeNode)); if (node == NULL) return FALSE; node->data = data; node->color = RED; node->left = NULL; node->right = NULL; curNode = *rbTree; //找到新结点的插入位置, p保存着待插入结点的父结点 p = NULL; while (curNode != NULL) { p = curNode; if (data < curNode->data) { curNode = curNode->left; } else { curNode = curNode->right; } } //空树 if (p == NULL) { *rbTree = node; } else { if (data < p->data) { p->left = node; } else { p->right = node; } } node->parent = p; //关键:调整红黑树,以保持性质 rbTreeInsertFixup(rbTree, node); return TRUE; } BOOL rbDeleteNode(RBTree *rbTree, data_t data) { RBTreeNode *target, *realDel, *child; target = rbSearch(rbTree, data); if (target != NULL) { //找到待删除的真正结点位置 if (target->left == NULL || target->right == NULL) { realDel = target; } else { realDel = rbSuccessor(target); } //将待删除节点的子树链接到其父节点上,待删除的节点最多只有一个子树 if (realDel->left != NULL) { child = realDel->left; } else { child = realDel->right; } if (child != NULL) { child->parent = realDel->parent; } if (realDel->parent == NULL) { *rbTree = child; } else { if (realDel->parent->left == realDel) { realDel->parent->left = child; } else { realDel->parent->right = child; } } if (target != realDel) { target->data = realDel->data; } //删除的重新结点是黑色的才需要调整 if (realDel->color == BLACK) { rbTreeDeleteFixup(rbTree, realDel->parent, child); } free(realDel); return TRUE; } else { return FALSE; } } /* * 插入一个结点时。可能被破坏的性质为(4)如果一个结点是红色的,则它的孩子结点是黑色的 * (2)根结点是黑色的 */ static void rbTreeInsertFixup(RBTree *rbTree, RBTreeNode *x) { RBTreeNode *p, *gparent, *uncle; //纠正性质2 while ((p = x->parent) != NULL && p->color == RED){ gparent = p->parent; //如果父结点是祖父结点的左孩子(因为父结点是红色结点,所以肯定有祖父结点) if (p == gparent->left) { uncle = gparent->right; //情况1:如果存在叔父结点,并且叔父结点颜色为红色,则可以通过改变祖父,父亲和叔父结点的颜色 //使得当前存在破坏性质的结点沿树上升,由x变为其祖父 if (uncle != NULL && uncle->color == RED) { gparent->color = RED; p->color = BLACK; uncle->color = BLACK; x = gparent; } //叔父不存在或者存在但是颜色是黑色的,则必须通过寻转来配合改变颜色来保持性质2 else { // 情况2:x为其父结点的右孩子,通过左旋转换为情况3 if (x == p->right) { //基于x的父结点做左旋,记原x结点位x‘ x = p; rbTreeLeftRotate(rbTree, x); //旋转后,重置x,使其仍未x节点的父结点(也即x’) p = x->parent; } //情况三:x为其父结点的左孩子,调整父结点和祖父结点的颜色,以纠正性质4,但是破坏了性质5 p->color = BLACK; gparent->color = RED; //基于祖父结点右旋以保持性质5 rbTreeRightRotate(rbTree, gparent); //此时x->parent->color = BLACK, 循环结束 } } // 父结点是祖父结点的右孩子 else { uncle = gparent->left; //情况1:如果存在叔父结点,并且叔父结点颜色为红色,则可以通过改变祖父,父亲和叔父结点的颜色 //使得当前存在破坏性质的结点沿树上升,由x变为其祖父 if (uncle != NULL && uncle->color == RED) { gparent->color = RED; p->color = BLACK; uncle->color = BLACK; x = gparent; } //情况2和情况3 else { // 情况2:x为其父结点的左孩子,通过旋转换为右情况3 if (x == p->left) { x = p; rbTreeRightRotate(rbTree, x); p = x->parent; } //情况三:x为其父结点的左孩子,调整父结点和祖父结点的颜色,以纠正性质4,但是破坏了性质5 p->color = BLACK; gparent->color = RED; //基于祖父结点左旋以保持性质5 rbTreeLeftRotate(rbTree, gparent); //此时x->parent->color = BLACK, 循环结束 } } } //保持性质2 (*rbTree)->color = BLACK; } /* * 删除一个黑结点会导致如下三个问题: * (1)如果被删除结点y是根结点,而y的一个红色孩子成为了新的根,则违反了性质2 * (2)如何y的父结点和其孩子结点都是红色的,则违反了性质4 * (3)删除y将导致先前包含y的任何路径上的黑结点树少一个,破坏了性质5。 * 解决方案是:被删除的结点黑色属性下移到其孩子结点x上。此时性质5都得以保持,于是存在2种情况: * (1)x原来为红色,此时孩子结点属性是红黑,此时破坏了性质(1),(4),如果x还是树根则,破坏了性质(2) * 处理方式为:将x重新着色为黑色(此操作同时去除其多余的黑色属性),处理完毕,红黑树性质得以保持 * (2)x原来为黑色,此时x的属性为双重黑色,破坏了性质(1),若x为树根,则可以只是简单的消除x多余的黑色属性 * 否则需要做必要的旋转和颜色修改 */ static void rbTreeDeleteFixup(RBTree *rbTree, RBTreeNode *parent, RBTreeNode *x) { RBTreeNode *brother; while ((x == NULL || x->color == BLACK) && x != *rbTree) { if (x == parent->left) { brother = parent->right; //因为被删除结点为黑色,其必然有兄弟结点,也即是现在x的兄弟结点(由性质5保证) //情况1:如果兄弟结点为红色,则parent颜色比为黑色,此时调整颜色,并左旋,使得brother和 //parent位置调换,此操作不破坏别的性质,并将情况1变化为情况2,3,4 if (brother->color == RED) { brother->color = BLACK; parent->color = RED; //左旋调整brother和parent的位置 rbTreeLeftRotate(rbTree, parent); //重置brother,转换到情况2,3,4 brother = parent->right; //此时brohter颜色肯定为黑色,并且不为NULL } //情况2: brother有两个黑色结点(NULL也为黑色结点):将x和brother抹除一重黑色 //具体操作为,brother的颜色变为红,x结点上移到其父结点 if ((brother->left == NULL || brother->left->color == BLACK) && (brother->right == NULL || brother->right->color == BLACK)) { brother->color = RED; x = parent; parent = parent->parent; } else { //情况3: brother左孩子为红色结点,右孩子为黑色结点 if (brother->right == NULL || brother->color == BLACK) { brother->left->color = BLACK; brother->color = RED; //右旋使情况3变化为情况4 rbTreeRightRotate(rbTree, brother); //重置brother brother = parent->right; } //情况4:brother的右孩子为红色结点: //交换brother和parent的颜色和位置,使得x的2重黑色属性中的一重转移到其parent上 //此时到brother的右孩子的黑结点数少一,于是将右结点的颜色置黑,红黑树性质得以保持 brother->color = parent->color; parent->color = BLACK; brother->right->color = BLACK; rbTreeLeftRotate(rbTree, parent); //至x为树根,结束循环 x = *rbTree; } } else { brother = parent->left; //情况1 if (brother->color == RED) { brother->color = BLACK; parent->color = RED; rbTreeRightRotate(rbTree, parent); brother = parent->left; } //情况2 if ((brother->left == NULL || brother->left->color == BLACK) && (brother->right == NULL || brother->right->color == BLACK)) { brother->color = RED; x = parent; parent = parent->parent; } else { //情况3:: brother右孩子为红色结点,左孩子为黑色结点 if (brother->left == NULL || brother->left->color == BLACK) { brother->right->color = BLACK; brother->color = RED; rbTreeLeftRotate(rbTree, brother); //重置brother brother = parent->left; } //情况4: brother的左孩子为红色结点 brother->color = parent->color; parent->color = BLACK; brother->left->color = BLACK; rbTreeRightRotate(rbTree, parent); x = *rbTree; } } } if (x != NULL) { x->color = BLACK; } } static void rbTreeLeftRotate(RBTree *rbTree, RBTreeNode *x) { RBTreeNode *y; y = x->right; x->right = y->left; if (y->left != NULL) { y->left->parent = x; } y->parent = x->parent; //x为树根 if (x->parent == NULL) { *rbTree = y; } else { if (x->parent->left == x) { x->parent->left = y; } else { x->parent->right = y; } } y->left = x; x->parent = y; } static void rbTreeRightRotate(RBTree *rbTree, RBTreeNode *x) { RBTreeNode *y; y = x->left; x->left = y->right; if (y->right != NULL) { y->right->parent = x; } y->parent = x->parent; if (x->parent == NULL) { *rbTree = y; } else { if (x->parent->left == x) { x->parent->left = y; } else { x->parent->right = y; } } y->right = x; x->parent = y; }
测试代码如下:
#include <stdio.h> #include <stdlib.h> #include "RBTree.h" #define N 11 void printRBNode(RBTreeNode *node); int main() { //数据 int a[N] = {1, 2, 4, 5, 7, 8, 11, 14, 15, 9, 3}, i; RBTreeNode *root; //树根 root = NULL; //测试插入 for (i = 0; i < N; i++) { if (!rbInsertNode(&root, a[i])) { break; } } rbInorderTraversal(&root, printRBNode); //测试查找,后继 RBTreeNode *fn, *fin, *sn, *tn; fn = rbSearch(&root, 4); sn = rbSearch(&root, 2); fin = rbSuccessor(fn); tn = rbSuccessor(sn); printf("%d, %d, %d, %d\n", fn->data, fin->data, sn->data, tn->data); //前驱 fn = rbPredecessor(fin); sn = rbPredecessor(tn); printf("%d, %d, %d, %d\n", fn->data, fin->data, sn->data, tn->data); //测试删除: 删除红色结点 rbDeleteNode(&root, 14); rbInorderTraversal(&root, printRBNode); printf("\n"); //测试删除: 删除黑色结点 rbDeleteNode(&root, 15); rbInorderTraversal(&root, printRBNode); printf("\n"); //测试删除: 删除根结点 rbDeleteNode(&root, 5); rbInorderTraversal(&root, printRBNode); } void printRBNode(RBTreeNode *node) { if (node != NULL) { printf("data: %d, color: %s, parent: %d\n", node->data, (node->color == RED ? "RED" : "BLACK"), (node->parent != NULL) ? node->parent->data : -1); } }
完整的代码见附件,写实现花了2天时间,终于搞定并理解了,-_-