`
chiyx
  • 浏览: 274704 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

数据结构之-红黑树的实现(C语言版)

阅读更多
    二叉查找树的效率依赖于其高度,为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天时间,终于搞定并理解了,-_-
3
5
分享到:
评论
1 楼 oklizy 2012-09-04  
学习了,给力

相关推荐

    数据结构课程作业-基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip

    基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip数据结构课程作业-基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip数据结构课程作业-基于C语言实现了红黑树及用户测试程序...

    红黑树---c语言实现

    ### 红黑树——C语言实现 #### 红黑树简介 红黑树(Red-Black Tree)是一种自平衡二叉查找树,在计算机科学领域有着广泛的应用,尤其是在...通过对红黑树的理解和实现,可以帮助开发者更好地处理复杂的数据结构问题。

    红黑树-基于C语言实现的红黑树数据结构.zip

    在实际应用中,红黑树广泛用于各种场景,如C++标准库中的STL map和set,它们底层就是基于红黑树实现的。红黑树的高效性和自平衡特性使得它在内存管理、数据库索引、文件系统等领域都有重要应用。理解并熟练掌握红黑...

    红黑树的c语言代码实现

    根据给定的信息,本文将详细解释红黑树的C语言实现方法,...总之,这段代码提供了一个完整的红黑树的C语言实现框架,通过理解和掌握这些核心概念和实现细节,可以帮助开发者更好地理解和应用红黑树这一高效的数据结构。

    红黑树C语言代码

    通过理解并实现红黑树,我们可以创建高效的数据结构,用于数据库索引、编译器符号表管理、内存分配系统等多种场景。虽然理解红黑树的平衡策略可能有些复杂,但一旦掌握,它将成为解决许多算法和数据结构问题的强大...

    数据结构与算法分析--C语言描述_数据结构与算法_

    常见的数据结构包括数组、链表、栈、队列、树(如二叉树、AVL树、红黑树)、图等。数组是最基础的数据结构,提供随机访问但插入和删除操作相对较慢;链表则通过指针链接元素,便于动态调整但访问速度较慢;栈和队列...

    红黑树(C语言版)(基本函数)

    红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出,它的设计目标是在保持二叉查找树特性的同时,通过引入颜色属性...这个C语言版的实现提供了对红黑树核心功能的直观理解,是学习和实践红黑树算法的好起点。

    算法与数据结构-C语言版

    《算法与数据结构-C语言版》是针对计算机科学领域中至关重要的两个概念——算法和数据结构的深入学习资料。陈守孔版的课程通常以其详尽的解释和实用的示例而闻名,对于初学者和有经验的程序员来说都是宝贵的学习资源...

    LINUX红黑树的C语言实现

    在实现红黑树时,C语言提供了必要的底层操作和数据结构,使得开发者能够直接对内存进行操作,实现红黑树的各个核心功能,如旋转、颜色调整、插入和删除操作。 在"rbtree"这个压缩包中,很可能包含了一个C语言实现的...

    C语言数据结构代码-包含所有常用数据结构实现方式

    本压缩包"**C语言数据结构代码-包含所有常用数据结构实现方式**"提供了C语言实现的各种常见数据结构和算法,这对于学习和理解数据结构以及提升编程技能非常有帮助。 1. **线性表**: 线性表是最基本的数据结构之一,...

    数据结构--用C语言描述 耿国华主编.zip

    C语言是一种强大的、低级别的编程语言,适合实现这些数据结构。下面,我们将深入探讨数据结构与C语言之间的联系,以及学习这两者的重要性。 首先,让我们了解数据结构的基本概念。数据结构主要包括数组、链表、栈、...

    数据结构--c语言描述(严蔚敏版)

    综上所述,《数据结构--C语言描述》涵盖了计算机科学基础中的重要主题,对于学习和理解数据结构及其在C语言中的实现具有极高的价值。通过学习这些内容,开发者能够设计出更高效、更优化的算法和数据管理系统,从而...

    南大C语言数据结构--通俗易懂版

    《南大C语言数据结构--通俗易懂版》是一份专为C语言初学者设计的教育资源,由南京大学提供,涵盖了数据结构的基础知识。这份资料深入浅出地讲解了C语言编程中的数据组织和管理,使得学习过程更为直观和易懂。 首先...

    红黑树c语言实现

    在C语言中实现红黑树,需要对数据结构和算法有深入的理解。 首先,我们要定义红黑树的节点结构。每个节点包含键值、颜色(红色或黑色)、指向左子节点和右子节点的指针,以及一个指向父节点的指针。节点的颜色是...

    数据结构(C语言版)严蔚敏版配套实现程序

    在这个压缩包中,你将找到一系列的C语言源代码,这些代码是严蔚敏版《数据结构》书中各种数据结构和算法的实现。这些实现涵盖了线性结构(如数组、链表)、树形结构(如二叉树、堆)、图结构以及排序和查找算法等多...

    数据结构--图片演示版(c语言)---严蔚敏

    在本资源包“数据结构--图片演示版(c语言)---严蔚敏”中,作者通过动态演示的方式,生动地展示了C语言实现的数据结构算法。这种可视化的方法对于初学者理解和掌握抽象概念极其有益。 首先,我们要理解数据结构的...

    数据结构(C语言版)-严蔚敏-源代码

    《数据结构(C语言版)》是由著名计算机科学家严蔚敏教授编著的一本经典教材,这本书深入浅出地介绍了各种常用的数据结构及其在C语言中的实现。 在C语言中实现数据结构,可以更好地理解底层的内存管理和算法执行...

    红黑树和二叉搜索树的C语言实现及性能比较

    本实验探讨了两种常见的自平衡二叉查找树——红黑树(Red-Black Tree)和二叉搜索树(Binary Search Tree),并用C语言实现了这两种数据结构,同时进行了性能比较。 首先,我们要理解二叉搜索树的基本特性。二叉...

Global site tag (gtag.js) - Google Analytics