算法导论第十三章：红黑树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法导论第十三章：红黑树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7664字，纯文字阅读大概需要11分钟。

内容图文

红黑树（red-black tree）是一种“平衡”查找树，它能保证最坏情况下，基本的动态集操作时间为O(lgn).

性质：

1)每个节点要么是红的，要么是黑的

2)根节点和叶子节点（NIL）是黑色的

3)若一个节点是红色的，则他的两个孩子节点是黑色的

4)对于每一个节点x，从该节点到其子酸节点的所有路径上包含相同数目的黑节点（#black nodes = black-height(x)）

引理：

一棵有n个内节点的红黑树的高度至多为 2 lg(n+1)

红黑树上插入删除的完整代码如下：

#include<iostream>
#include<iomanip>
using namespace std;

#define BLACK 0
#define RED 1

typedef struct RBTNode{
	int key;
	bool color;
	RBTNode *parent;
	RBTNode *left;
	RBTNode *right;
	}RBTNode;

typedef struct RBTree{
	RBTNode *root;
	}RBTree;

RBTNode NILL={-1,BLACK,NULL,NULL,NULL};
RBTNode *NIL=&NILL;          //init sentinel NIL

void RBT_InorderWalk(RBTNode *x)
{
	if(x!=NIL)
	{
		RBT_InorderWalk(x->left);
		cout<<setw(3)<<x->key;
		if(x->color==1)
			cout<<"     Red"<<endl;
		else
			cout<<"     Black"<<endl;
		RBT_InorderWalk(x->right);
 		}
	}
RBTNode *RBT_Search(RBTNode *x,int key)
{
	if(x->key == key || x==NIL)
		return x;
	if(key < x->key)
		RBT_Search(x->left,key);
	else
		RBT_Search(x->right,key);
		}
RBTNode *RBT_Minimum(RBTNode *x)
{
	while(x->left != NIL)
		x=x->left;
	return x;
	
	}
void Left_Rotate(RBTree *T,RBTNode *x)
{
	RBTNode *y=x->right;    //set y

	x->right=y->left;       //turn y's left subtree into x's right subtree
	if(y->left!=NIL)
		y->left->parent=x;

	y->parent=x->parent;     //link x's parent to y;
	if(x->parent == NIL)
		T->root=y;
	else if(x==x->parent->left)
		x->parent->left=y;
	else
		x->parent->right=y;

	y->left=x;               //put x on y's left
	x->parent=y;
	}

void Right_Rotate(RBTree *T,RBTNode *x)
{
	RBTNode *y=x->left;      //set y
	
	x->left=y->right;   //link x's left tree into y's right subtree;
	if(y->right !=NIL)
		y->right->parent=x;
	
	y->parent=x->parent;    //link x's parent to y
	if(x->parent == NIL)
		T->root=y;
	else if(x == x->parent->left)
		x->parent->left=y;
	else
		x->parent->right=y;
	
	y->right=x;         //put x on y's right
	x->parent=y;

	}
void RBT_InsertFixup(RBTree *T,RBTNode *z)
{
	while(z->parent->color==RED)
	{
		if(z->parent == z->parent->parent->left)    
		{
			RBTNode *y=z->parent->parent->right;   
			if(y->color==RED)
			{  
				z->parent->color=BLACK;            //case 1
				y->color=BLACK;                    //case 1
				z->parent->parent->color=RED;      //case 1
				z=z->parent->parent;               //case 1
				}
			else
			{
			   	if(z==z->parent->right)
				{ 
					z=z->parent;                    //case 2
					Left_Rotate(T,z);               //case 2
				 	}
				z->parent->color=BLACK;             //case 3
				z->parent->parent->color=RED;       //case 3
				Right_Rotate(T,z->parent->parent);  //case 3
		 		} 
		 	}
		else
		{//ame as then clause with "right" and "left" exchanged  
			RBTNode *y=z->parent->parent->left;
			if(y->color==RED)
			{
				z->parent->color==BLACK;
				y->color=BLACK;
				z->parent->parent->color=RED;
				z=z->parent->parent;
		 		}
			else
			{
				if(z==z->parent->left)
				{
					z=z->parent;
					Right_Rotate(T,z);
				 	}
				z->parent->color=BLACK;
				z->parent->parent->color=RED;
				Left_Rotate(T,z->parent->parent);
			 	} 
			} 
		} 
	T->root->color=BLACK;      //turn the root to BLACK
	}
void RBT_Insert(RBTree *T,int value)
{
	RBTNode *z=new RBTNode();
	z->key=value;
	z->color =RED;   
	z->parent=NIL;
	z->left=NIL;
	z->right=NIL;

	RBTNode *y=NIL;        //y is the parent of x
	RBTNode *x=T->root;
	while(x != NIL)
	{
		y=x;
		if(z->key < x->key)
			x=x->left;
		else
			x=x->right;
		}  
	z->parent=y;   //link new node's parent node to y(y's child is NIL)
	if(y==NIL)
		T->root=z;
	else if(z->key < y->key)
		y->left=z;
	else
		y->right =z;
	RBT_InsertFixup(T,z);
	}

void RBT_Transplant(RBTree *T,RBTNode *u,RBTNode *v)
{
	if(u->parent==NIL)
		T->root=v;
	else if(u==u->parent->left)
		u->parent->left=v;
	else
		u->parent->right=v;
	v->parent=u->parent;
	}
void RBT_DeleteFixup(RBTree *T,RBTNode *x)
{
	RBTNode *w;
	while(x!=T->root && x->color==BLACK)
	{
		if(x==x->parent->left)
	 	{
			w=x->parent->right;  //set w to x's sibling
			if(w->color==RED)      //case 1:x's sibling w is red
			{
				w->color=BLACK;
				x->parent->color=RED;
				Left_Rotate(T,x->parent);
				w=x->parent->right;
	 			}
			if(w->left->color==BLACK && w->right->color==BLACK)  
			{ //case 2:x's sibling w is black and both of w's children are black
				w->color=RED;
				x=x->parent;
				}
			else
			{ 
				if(w->right->color==BLACK)     
				{//case 3:x's sibling w is black,w's left child is red, and w's right child is black
					w->left->color=BLACK;
					w->color=RED;
					Right_Rotate(T,w);
					w=x->parent->right;
			 		}
				w->color=x->parent->color;      //case 4: x's sibling w is black,and w's right child is red
				x->parent->color=BLACK;         //.
				w->right->color=BLACK;         // .
				Left_Rotate(T,x->parent);      // .
				x=T->root;                     //case 4
				}
			}
		else
		{//Same as then clause with "right" and "left" exchanged
			w=x->parent->left;
			if(w->color==RED)
			{
				w->color=BLACK;
				x->parent->color=RED;
				Right_Rotate(T,x->parent);
				w=x->parent->left;
				} 
			if(w->left->color==BLACK && w->right->color==BLACK)
			{ 
				w->color=RED;
				x=x->parent;
				}
			else
			{
				if(w->left->color==BLACK)
				{
					w->right->color=BLACK;
					w->color=RED;
					Left_Rotate(T,w);
					w=x->parent->left;
			 	 	}
				w->color=x->parent->color;
				x->parent->color=BLACK;
				w->left->color=BLACK;
				Right_Rotate(T,x->parent);
				x=T->root;
	 			} 
	 		}
  		}
 	x->color=BLACK;
	}
/*RBTNode *RBT_Successor(RBTNode *x){
     RBTNode *r = x;
     if(r->right != NIL)
         return RBT_Minimum(r->right);
     RBTNode *y = r->parent;
     while(y != NIL && r  == y->right){
         r = y;
         y = y->parent;
     }
     return y;
 }*/
void RBT_Delete(RBTree *T,RBTNode *z)
{
	RBTNode *x=NULL,*y=NULL;
	bool y_origin_color;

	y=z;
	y_origin_color=y->color;
	if(z->left == NIL)
	{
		x=z->right;
		RBT_Transplant(T,z,z->right);
	 	}
	else if(z->right ==NIL)
	{ 
		x=z->left;
		RBT_Transplant(T,z,z->left);
	  	}
	else
	{ 
		y=RBT_Minimum(z->right);
		y_origin_color=y->color;
		x=y->right;

		if(y->parent==z)
			x->parent=y;
		else
		{
			RBT_Transplant(T,y,y->right);
			y->right=z->right;
			y->right->parent=y;
	 		}
		RBT_Transplant(T,z,y);
		y->left=z->left;
		y->left->parent=y;
		y->color=z->color;
	  	}
	if(y_origin_color==BLACK)
		RBT_DeleteFixup(T,x);
		}

int main()
{
	int A[]={41,38,31,12,19,8};
	int n=sizeof(A)/sizeof(int);
	
	cout<<"/*--------------------Ceate Red-Black tree------------------*/"<<endl;
	RBTree *T=new RBTree();
	T->root=NIL;
	for(int i=0;i<n;i++)
		RBT_Insert(T,A[i]);
	cout<<"The Red-Black tree is:"<<endl;
	RBT_InorderWalk(T->root);
	cout<<"The root of the RBT is:"<<T->root->key<<endl;
	cout<<"/*----------------------------------------------------------*/"<<endl;

	cout<<"/*----------------------RBT Insertion-----------------------*/"<<endl;
	int ikey;
	cout<<"Please input the inserting key:";
	cin>>ikey;
	RBT_Insert(T,ikey);
	cout<<"After insertion,the RBT is:"<<endl;
	RBT_InorderWalk(T->root);
	cout<<"The root of the RBT is:"<<T->root->key<<endl;
	cout<<"/*-----------------------------------------------------------*/"<<endl;

	cout<<"/*---------------------RBT Deletion-------------------------*/"<<endl;
	int dkey;
	cout<<"Please input the deleting key:";
	cin>>dkey;
	RBTNode *dNode=NULL;
	dNode=RBT_Search(T->root,dkey);
	if(dNode==NULL)
		cout<<"The deleting key doesn't exist."<<endl;
	else
	{
		RBT_Delete(T,dNode);
		cout<<"After deletion,the RBT is:"<<endl;
		RBT_InorderWalk(T->root);
		cout<<"The root of the RBT is:"<<T->root->key<<endl;
		}

	return 0;
	}

运行结果如下：

技术分享

原文：http://blog.csdn.net/u010183397/article/details/46914789

内容总结

以上是互联网集市为您收集整理的算法导论第十三章：红黑树全部内容，希望文章能够帮你解决算法导论第十三章：红黑树所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1328382.html

来源：【匿名】

【上一篇】算法学习#03--详解最小二乘法原理和代码【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【算法导论第十三章：红黑树】教程文章相关的互联网学习教程文章

红黑树（red-black tree）是一种“平衡”查找树，它能保证最坏情况下，基本的动态集操作时间为O(lgn).性质：1)每个节点要么是红的，要么是黑的2)根节点和叶子节点（NIL）是黑色的3)若一个节点是红色的，则他的两个孩子节点是黑色的4)对于每一个节点x，从该节点到其子酸节点的所有路径上包含相同数目的黑节点（#black nodes = black-height(x)）引理：一棵有n个内节点的红黑树的高度至多为 2 lg(n+1)红黑树上插入删除的完整代码...

算法导论学习-binary search tree【代码】【图】

1. 概念：Binary-search tree（BST）是一颗二叉树，每个树上的节点都有<=1个父亲节点，ROOT节点没有父亲节点。同时每个树上的节点都有[0,2]个孩子节点(left child AND right child)。每个节点都包含有各自的KEY值以及相应的satellite data。其中KEY是几种BST基本操作的主要操作对象。 2. BST的特别性质：BST任何一颗子树上的三个节点left, parent, right. 满足条件left.key<parent.key<=right.key一颗典型的BST如下图所示：观察之...

第15章动态规划------算法导论【代码】

15.1钢条切割#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<ctime> #include<string> using namespace std; int p[1000]{ 0,1,5,8,9,10,17,17,20,24,30 };//钢条价格。长度i的价格为p[i] int ordinary(int *p, int n)//递归法 {if (n == 0)return 0;else{int q = -1;for (int i = 1; i <= n; ++i){q = max(p[i] + ordinary(p, n - i), q);}return q;} } int top_down_memory(int *p, int n)/...

算法导论——拓扑排序【代码】

package org.loda.graph;import org.loda.structure.Stack; import org.loda.util.In;/*** * @ClassName: Topological * @Description: 拓扑排序是所有节点dfs的逆后序，也就是每个节点任务完成的时间的逆序排序 * @author minjun * @date 2015年5月24日下午7:17:53 **/ public class Topological {/*** 由于拓扑排序是df获取所有节点的逆后序排序* 这里利用Stack后序存储元素，那么获取出来就是反向（逆）后序排列的拓顺序*/...

算法导论学习---红黑树详解之插入(C语言实现)【代码】【图】

前面我们学习二叉搜索树的时候发现在一些情况下其高度不是很均匀，甚至有时候会退化成一条长链,所以我们引用一些”平衡”的二叉搜索树。红黑树就是一种”平衡”的二叉搜索树，它通过在每个结点附加颜色位和路径上的一些约束条件可以保证在最坏的情况下基本动态集合操作的时间复杂度为O(nlgn).下面会总结红黑树的性质，然后分析红黑树的插入操作，并给出一份完整代码。先给出红黑树的结点定义：#define RED 1#define BLACK 0///红黑...

【听课笔记】算法导论

课程地址http://v.163.com/special/opencourse/algorithms.html今天课程地址:http://open.163.com/movie/2010/12/G/F/M6UTT5U0I_M6V2T1JGF.html讨论performanceAnalysis of Algorithms: the study of computer program performance ans resource usage.Thinking: What is more important than performance?Functionality, modularity, user-friendliness, security...Then why study algs and perf?performance is like the "money...

算法导论——斐波那契堆【代码】【图】

斐波那契堆是具有最小堆序的有根树的集合，也就是集合中的每棵树都具有父结点的关键字小于或等于子结点的关键字。对于每一个结点x，主要有以下属性：名称说明记作关键字结点存储的值x.key父结点结点的父亲x.p左兄弟结点的左兄弟x.left右兄弟结点的右兄弟x.right孩子结点的一个儿子结点x.child度结点的儿子数量，不包括孙子及下层x.degree标记结点是否有儿子被删除x.mark堆H本身属性：名称说明记作最小结点最小的根结点H.min结点数...

《算法导论》中动态规划求解钢条切割问题【代码】

动态规划算法概述动态规划（dynamic programming）1是一种与分治方法很像的方法，都是通过组合子问题的解来求解原问题。不同之处在于，动态规划用于子问题重叠的情况，比如我们学过的斐波那契数列。在斐波那契数列的求解问题中，我们经常要对一个公共子问题进行多次求解，而动态规划算法，则对每个子问题只求解一次，将其解保存在一个表格中，从而避免了大量的冗余计算量。动态规划算法常用于寻找最优解问题（optimization pro...

算法导论第11章散列表

散列表是主要支持动态集合的插入、搜索和删除等操作，其查找元素的时间在最坏情况下是O(n)，但是在是实际情况中，散列表查找的期望是时间是O(1)，散列表是普通数组的推广，因为可以通过元素的关键字对数组进行直接定位，所以能够在O(1)时间内访问数组的任意元素。1、直接寻址表当关键字的全域较小，即所有可能的关键字的量比较小时，可以建立一个数组，为所有可能的关键字都预留一个空间，这样就可以很快的根据关键字直接找到对应元...

读书笔记 -- 算法导论 (序言+第一部分)

什么是基础呢？就是要把我们大学所学的离散数学，算法与数据结构，操作系统，计算机体系结构，编译原理等课程学好。对计算机的体系，CPU本身，操作系统内核，系统平台，面向对象编程，程序的性能等要有深层次的掌握。要编写出优秀的代码同样要扎实的基础，如果数据结构和算法学的不好，怎么对程序的性能进行优化，怎样从类库中选择合适的数据结构。如果不了解操作系统，怎样能了解这些开发工具的原理，它们都是基于操作系统的。不...

【算法导论学习-015】数组中选择第i小元素（Selection in expected linear time）

1、算法思想问题描述：从数组array中找出第i小的元素（要求array中没有重复元素的情况），这是个经典的“线性时间选择（Selection in expected linear time）”问题。思路：算法导论215页9.2 Selection in expect linear time 2、java实现思路：算法导论216页伪代码/*期望为线性时间的选择算法，输入要求，array中没有重复的元素*/public static int randomizedSelect(int[] array,int start,int end,int i) {if (start==end) {...

【算法导论之七】动态规划求解最长公共子序列

一、动态规划的概念动态规划（Dynamic Programming）是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原始问题的解，与此不同，动态规划适用于子问题不是独立的情况，也就是各个子问题包含公共的子问题。在这种情况下，采用分治法会做许多不必要的工作，即重复地求解公共地子问题。动态规划算法对每个子问题只求解一次，将其结果保存在一张...

算法导论-求x的n次方【代码】【图】

目录 1、分治求x的n次方思路 2、c++代码实现内容 1、分治求x的n次方思路T(n)=Θ(lgn) 为了计算乘方数a^n，传统的做法（所谓的Naive algorithm）就是循环相乘n次，算法效率为Θ(n)。但是如果采用分治法的思想，算法效率可以提高到Θ(lgn)，如...

【算法导论学习笔记】第3章：函数的增长【图】

原创博客，转载请注明：http://www.cnblogs.com/wuwenyan/p/4982713.html 　　当算法的输入n非常大的时候，对于算法复杂度的分析就显得尤为重要，虽然有时我们能通过一定的方法得到较为精确的运行时间，但是很多时候，或者说绝大多数时候，我们并不值得去花精力求得多余的精度，因为精确运行时间中的倍增常量和低阶项已经被输入规模本身的影响所支配。我们需要关心的是输入规模无限增加，在极限中，运行时间是如何随着输入规模增大...

算法导论第七章快速排序（python）【代码】

用的最多的排序平均性能：O(nlogn){随机化nlogn}原地址排序稳定性：不稳定思想：分治（切分左右）学习方式：自己在纸上走一遍 def PARTITION(A,p,r):x = A[r] # 锚点主元{大于它放一边，小于的放另一边}i = p - 1for j in range(p,r):if A[j] <= x:i += 1A[i],A[j] = A[j],A[i]A[i+1],A[r] = A[r],A[i+1]return i + 1def QUICKSORT(A,p,r):if p < r: #分治q = PARTITION(A,p,r)QUICKSORT(A,p,q-1)QUICKSORT(A,q+1,r)if__name__ ...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...