二叉查找树的效率依赖于其高度,为O(h),普通的具有N个结点的二叉查找树树的高度落差会很大,极端情况下会出现h=n的情况(插入结点序列为排好序的情况下),这样二叉查找树就退化为一个列表了。于是就出现了平衡树的概念,它能保证树的高度h在lgn这个数量级上。
红黑树是许多“平衡树”中的一种,它确保没有一条路径比其他的路径长出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天时间,终于搞定并理解了,-_-
分享到:
相关推荐
基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip数据结构课程作业-基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip数据结构课程作业-基于C语言实现了红黑树及用户测试程序...
红黑树 红黑树_基于C语言实现的红黑树数据结构
红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。
严蔚敏《数据结构》红黑树插入的实现C代码
红黑树的c实现源码与剖析 原作者:那谁 源码剖析作者:July ===================== July说明: 由于原来的程序没有任何一行注释,我把它深入剖析,并一行一行的添加了注释, 详情请参见此文: 教你彻底实现红黑树:...
高级数据结构及其实现12.1 自顶向下伸展树12.2 红黑树12.2.1 自底向上插入12.2.2 自顶向下红黑树12.2.3 自顶向下删除12.3 确定性跳跃表12.4 AA-树12.5 treap树12.6 k-d树12.7 配对堆总结练习参考文献索引
《数据结构与算法分析:C语言描述》曾被评为20世纪顶尖的30部计算机著作之一,作者在数据结构和算法...增加了高级数据结构及其实现的内容,包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平...
在《数据结构与算法分析:C语言描述》中,作者精炼并强化了他对算法和数据结构...增加了高级数据 结构及其实现的内容,包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平均情况分析的一些新结果。
数据结构与算法分析:C语言描述全书特点如下:1...4.新开辟一章讨论高级数据结构以及它们的实现,其中包括红黑树、自顶向下伸展树。treap树、k-d树、配对堆以及其他相关内容;5.合并了堆排序平均情况分析的一些新结果。
一个红黑树的c语言完整实现,代码清晰易读。初学者可以更好地了解红黑树的性质
经典的数据结构教程,适合入门《数据结构》(C语言版)针对采用ANSI C实现数据结构进行了全面的描述和深入的讨论。书中详细讨论了栈、队列、链表以及查找结构、高级树结构等功能,对裴波那契堆、伸展树、红黑树、2-3树...
考查书中介绍的一些高级数据结构, ●新开辟一章讨论高级数据结构以及它们的实现,其中包括红黑树、自顶向下伸展树。treap树、k-d树、配对堆以及其他相关内容, ●合并了堆排序平均情况分析的一些新结果, 本书是国外...
管理系统是一种通过计算机技术实现的用于组织、监控和控制各种活动的软件系统。这些系统通常被设计用来提高效率、减少错误、加强安全性,同时提供数据和信息支持。以下是一些常见类型的管理系统: 学校管理系统: ...
《数据结构与算法分析:C语言描述》曾被评为20世纪顶尖的30部计算机著作之一,作者在数据结构和算法...增加了高级数据结构及其实现的内容,包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平...
数据结构包括:栈,队列,两个队列实现一个栈,两个栈实现一个队列,二叉树的创建,添加,平衡二叉树天界旋转等,红黑树,创建,添加节点,删除节点,调整。算法包括:10个排序(冒泡,插入,选择,快排,归并,桶排...
●新开辟一章讨论高级数据结构以及它们的实现,其中包括红黑树、自顶向下伸展树。treap树、k-d树、配对堆以及其他相关内容 ●合并了堆排序平均情况分析的一些新结果 本书是国外数据结构与算法分析方面的标准...
考查书中介绍的一些高级数据结构●新开辟一章讨论高级数据结构以及它们的实现,其中包括红黑树、自顶向下伸展树。treap树、k-d树、配对堆以及其他相关内容●合并了堆排序平均情况分析的一些新结果本书是国外数据结构...