精华内容
下载资源
问答
  • 红黑树看不懂你找我

    千次阅读 2020-03-26 21:27:20
    文章目录一:什么是红黑树二:关于红黑树的一般操作1.查找操作2. 插入操作2.1 新节点:我是红色的,我爹是红色的,我叔叔是黑色的2.2 新节点:我是红色的,我爹是红色的,我叔叔也是红色的3.删除操作3.1替代点是红色...

    一:什么是红黑树

    红黑树是AVL树的一种流行变种,是具有以下五个特点的二叉查找树

    1. 每一个节点或者着成红色,或者着成黑色
    2. 根是黑色
    3. 每个叶节点Nil是黑色
    4. 如果一个节点是红色的,那么它的子节点必须是黑色的
    5. 每一条从某节点到某Nil指针的路径必须包含相同数目的黑色节点

    二:关于红黑树的一般操作

    对红黑树操作,最困难的就是保持上述的红黑树性质中的红色标记部分。

    1.查找操作

    红黑树是二叉查找树,所以其查找操作与一般的二叉查找树相同

    • 令根节点为当前节点
    • 当前节点为Nil,返回Nil
    • 要找的值等于当前节点,返回当前节点
    • 要找的值大于当前节点, 令右儿子为当前节点,重复步骤2
    • 要找的值小于当前节点,令左儿子为当前节点,重复步骤2

    操作的时间复杂度O(logN)

    2. 插入操作

    当我们想向树中插入一个新节点时,通常把这个节点作为叶节点插入。

    Part1:
    假设把这个点涂成黑色,那完了,肯定违反了条件5,因为本来任意的节点到某Nil指针的路径中黑色节点数是相同的,现在加上黑色节点的这条路径黑色节点数度肯定会+1,于是原来的条件被破坏了,因此,新加的节点必须被涂成红色

    Part2:
    如果新插入的节点的父节点是黑色的,那么直接插入新的红节点就完事了

    Part3:
    如果新插入的节点的父节点是红色,那么条件4就被破坏了,这种情况下,我们必须在保持条件5不被破坏的同时,利用改变节点颜色以及树的旋转来满足所有条件。

    2.1 新节点:我是红色的,我爹是红色的,我叔叔是黑色的

    在这里插入图片描述

    • 设置P为黑色
    • 设置G为红色
    • 进行右单旋转

    在这里插入图片描述

    • 设置X为黑色
    • 设置G为红色
    • 进行右双旋转

    还有对称的两种情况,操作也是对称的

    2.2 新节点:我是红色的,我爹是红色的,我叔叔也是红色的

    在这里插入图片描述

    • 把G节点设置为红色
    • 把P节点设置为黑色
    • 把S节点设置为黑色
      在这里插入图片描述
    • 把G节点设置为红色
    • 把P节点设置为黑色
    • 把S节点设置为黑色

    这时候,如果G的父节点也是红的,那么G的颜色翻转的操作就会影响性质4,于是我们对G节点以及其父节点GP和父节点的兄弟节点GPS进行2.1所示的旋转操作

    注意如果G的父节点GP为红色,G父节点的兄弟节点GPS肯定不能为红色,只能为黑色,因为在红黑树中,不可能出现出现深度小于树的总深度且双兄弟都为红的情况,这种情况在其他的插入或删除过程中已经消除了。
    在这里插入图片描述

    GP刚好为根结点时,那么根据性质2,我们必须把GP重新设为黑色,那么树的红黑结构变为:黑黑红。换句话说,从根结点到叶子结点的路径中,黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。

    还有对称的两种情况,操作也是对称的

    伪代码

    RB-INSERT(T, z)
    	//红黑树插入
    	y = T.nil
    	x = T.root
    	while x != T.nil
    		y = x
    		if z.key<x.key
    		x = x.left
    		else x = x.right
    	z.p = y
    	if y == T.nil
    		T.root = z
    	else if z.key < y.key
    		y.left = z
    	else y.right = z
    	z.left = T.nil
    	z.right = T.nil
    	z.color = RED
    	//对红黑树的性质进行恢复
    	RB-INSERT-FIXUP(T, z)
    
    RB-INSERT-FIXUP(T, z)
    	//插入红色子节点,破坏了性质4时
    	while z.p.color = RED
    		//父节点为左子树
    		if z.p == z.p.p.left
    		 	//获取叔叔结点y
    			y = z.p.p.right
    			//叔叔结点为红色
    			if y.color = RED
    				z.p.color = BLACK
    				y.color = BLACK
    				z.p.p.color = RED
    				z = z.p.p
    			//叔叔结点为黑色
    			else 
    				//新插入的结点为父节点的右孩子,先来个父子调换,先进行一次左旋转
    				if z == z.p.right
    					z = z.p
    					LEFT-ROTATE(T,z)
    				//化成了叔叔结点黑色的一般情况
    				z.p.color  = BLACK
    				z.p.p.color = RED
    				RIGHT-ROTATE(T, z.p.p)
    		//对称情况
    		else (same as then clause with "right" and "left" exchanged)
    	T.root.color = BLACK			
    

    难点来了,难点来了!!


    其实不难

    3.删除操作

    删除操作一直一来是树这种ADT的难点所在

    一般二叉搜索树的删除操作:

    • 该节点为叶节点的情况:可以直接删除,将其父节点的儿子指针设为Nil
    • 该节点只有一个非空子节点:可以直接删除,将其父节点的儿子指针指向其唯一儿子
    • 该节点有两个非空子节点:用该节点左子树的最大节点或者右子树的最小节点替换该节点,然后删除对应的左子树最大节点或者右子树最小节点,最终可以回到前两种情况。

    好,到这里你肯定还是明白的对吧

    现在考虑红黑树的删除操作。

    注意:
    根据一般二叉搜索树的删除操作来看,我们要删除的节点其实不一定是最终从图中移出去的节点,称最终从图中移出去的节点为替代点,我们先从右子树的最小节点(或左子树的最大节点)找到我们的替代点,与删除点的值交换,但是颜色都不变,然后再删除替代点,然后对树的性质进行恢复。而现在这些替代点都是一些树的末节点(区别于叶节点,我们现在将Nil节点视为黑色叶节点),删除操作便会简化许多,并可以归纳为像插入那样的几个类别。当然了替代点和我们要删除的点也有可能是同一点,但处理方法是一样的。

    我们虽然删除了替代点,但是我们对树进行恢复时,还是会将该替代点放在树中参与恢复,恢复完成后再移掉。

    在本文中,示例都默认是选择右子树的最小节点作为真正删除点,也可以选择左子树的最大节点

    在这里插入图片描述

    3.1替代点是红色的

    直接从树中去掉即可,不会影响红黑树的性质,算法直接结束

    不会出现替代点为红色且有儿子为非叶子节点的情况,所以这种情况是最简单的
    在这里插入图片描述

    3.2替代点是黑色的

    替代点是黑色,那么删除之后树的性质就被破坏了,需要进行修复

    3.2.1 有一个儿子为且必须为红色时

    当替代节点只有一个儿子且为红色时
    直接用它的红色儿子节点取代它,并将颜色改为黑色,这样所有经过替代节点的路径都将经过他的儿子,黑色高度不变。

    在这里插入图片描述
    注意这跟上面图不一样,这张图D节点是替代节点

    不可能存在只有一个儿子且儿子为黑色的情况,那样本身就是不平衡的

    3.2.2 有两个黑色儿子

    当替代点是黑色的且有两个黑色儿子(可以为叶节点Nil)时,那他肯定有兄弟,那么又可以分为其他几类

    • 替代点是黑色,其兄弟节点是红色
    • 替代点是黑色,其兄弟节点是黑色
    3.2.2.1 替代点的兄弟节点是红色

    在这里插入图片描述

    • 将G节点也就是替代点的父节点设置为红色,
    • 兄弟节点S设置为黑色
    • 然后进行向左单旋转,

    现在可以直接删掉D了吗?(以下都默认标识D为替代点) 不 行 , t a n 90 ° \hspace4ex 不行,tan90\degree tan90°

    这个操作不改变任何路径的黑色高度,这时候删去D肯定会变的不平衡,我们只是把情况变为了兄弟节点为黑色的情况,也就是下面将要叙述的情况,我们接下来需要重新进入算法,进一步处理

    3.2.2.2 替代点的兄弟节点是黑色

    替代点D与其兄弟节点S都是黑色的,所以D的父节点颜色是不确定的,用绿色表示

    又分为以下几种情况

    3.2.2.2.1 当兄弟节点的两个儿子也都是黑色

    在这里插入图片描述
    PS:C1、C2可为Nil

    • S节点颜色变为红
    • G节点颜色变黑
    • 把G作为新的替代点进行下一轮操作

    假设G一开始是黑色的,这个操作过后,所有一开始经过S节点的路径黑色高度-1,那么在删除D节点后,所有经过D节点的路径黑色高度也会-1,这棵子树大家黑色高度都减一,结局竟该死的甜美,但是经过G的比不经过G的黑色高度减一了,所以再在G上重新平衡处理

    假设G一开始是红色的,这个操作后,所有一开始经过S节点的路径黑色高度不变,经过D的路径黑色高度+1,那么在删除D后,所有经过D节点的路径黑色高度又变回来了,结局竟还是该死的甜美,经过G为根的子树已经平衡了,再在G上重新平衡处理

    注意当G是树的根时,就表示我们已经做完了,我们从所有路径去除了一个黑色节点,所有性质在上溯过程中都保持着。

    3.2.2.2.2 当兄弟节点的左儿子是红色的,右儿子是黑色

    在这里插入图片描述

    • C1设置为黑色
    • S设置为红色
    • 对S进行向右单旋转

    这样的操作不改变任何路径的黑色高度,本来的平衡状态不变,所以删除D之后就破坏了原先的条件,还要进行自平衡变换,此时成了下面一种情况继续处理

    3.2.2.2.3 当兄弟节点的右儿子是红色的,左儿子随意

    在这里插入图片描述

    • 交换G和S的颜色
    • 设置兄弟节点的右儿子C2为黑色
    • 进行向左单旋转

    该操作使所有变化前经过S节点的路径黑色高度都不变,经过D的路径黑色高度+1,在删除D后,所有经过G节点的路径都不变,达到平衡

    说白了删除就是不断递归变换直到满足替代点的删除条件。

    例子:删除30根节点
    在这里插入图片描述

    在这里插入图片描述
    练习一下吧,这里有个在线红黑树工具,戳

    三:渐进边界的证明

    包含n个内部节点的红黑树的高度是 O ( l o g n ) O(logn) O(logn)

    定义:

    h ( v ) 表 示 以 节 点 v 为 根 的 子 树 的 高 度 。 {\displaystyle h(v)}表示以节点{\displaystyle v}为根的子树的高度。 h(v)v
    b h ( v ) 表 示 从 v 到 子 树 中 任 何 叶 子 的 黑 色 节 点 的 数 目 {\displaystyle bh(v)}表示从{\displaystyle v}到子树中任何叶子的黑色节点的数目 bh(v)v
    ( 如 果 v 是 黑 色 则 不 计 数 它 , 也 叫 做 黑 色 高 度 ) 。 (如果{\displaystyle v}是黑色则不计数它,也叫做黑色高度)。 v

    引 理 : 以 节 点 v 为 根 的 子 树 有 至 少 2 b h ( v ) − 1 个 内 部 节 点 。 引理:以节点{\displaystyle v}为根的子树有至少2^{bh(v)}-1个内部节点。 v2bh(v)1
    引 理 的 证 明 ( 通 过 归 纳 高 度 ) : 引理的证明(通过归纳高度):

    归 纳 假 设 : 归纳假设:
    如 果 v 的 高 度 是 零 则 它 必 定 是 N I L , 因 此 b h ( v ) = 0 b h ( v ) = 0 。 所 以 : 2 b h ( v ) − 1 = 2 0 − 1 = 0 如果v的高度是零则它必定是NIL,因此{\displaystyle bh(v)=0}{\displaystyle bh(v)=0}。所以:2^{{bh(v)}}-1=2^{{0}}-1=0 vNILbh(v)=0bh(v)=02bh(v)1=201=0

    如 果 h ( v ) = k , 有 2 b h ( v ) − 1 个 内 部 节 点 成 立 如果h(v)=k,有2^{bh(v)}-1个内部节点成立 h(v)=k2bh(v)1
    于 是 h ( v ′ ) = k + 1 于是h(v')=k+1 h(v)=k+1
    因 为 v ′ 有 h ( v ′ ) > 0 所 以 它 是 个 内 部 节 点 。 同 样 的 它 有 的 两 个 儿 子 , 其 黑 色 高 度 要 么 是 b h ( v ′ ) 要 么 是 b h ( v ′ ) − 1 ( 依 据 v ′ 是 红 色 还 是 黑 色 ) 。 通 过 归 纳 假 设 每 个 儿 子 都 有 至 少 2 b h ( v ′ ) − 1 − 1 个 内 部 接 点 , 所 以 v ′ 有 : 因为v'有h(v')>0 \\所以它是个内部节点。同样的它有的两个儿子,其黑色高度要么是bh(v')要么是bh(v')-1(依据v'是红色还是黑色)。通过归纳假设每个儿子都有至少2^{{bh(v')-1}}-1个内部接点,所以v'有: vh(v)>0bh(v)bh(v)1v2bh(v)11v
    2 b h ( v ′ ) − 1 − 1 + 2 b h ( v ′ ) − 1 − 1 + 1 = 2 b h ( v ′ ) − 1 个 内 部 节 点 。 2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1个内部节点。 2bh(v)11+2bh(v)11+1=2bh(v)1

    使 用 这 个 引 理 我 们 现 在 可 以 展 示 出 树 的 高 度 是 对 数 性 的 。 因 为 在 从 根 到 叶 子 的 任 何 路 径 上 至 少 有 一 半 的 节 点 是 黑 色 ( 根 据 红 黑 树 性 质 4 ) , 根 的 黑 色 高 度 至 少 是 h ( r o o t ) 2 通 过 引 理 我 们 得 到 : 使用这个引理我们现在可以展示出树的高度是对数性的。\\ 因为在从根到叶子的任何路径上至少有一半的节点是黑色(根据红黑树性质4),\\根的黑色高度至少是 {\frac {h(root)}{2}}通过引理我们得到: 使(4)2h(root)

    n ⩾ 2 h ( r o o t ) 2 − 1 ↔    log ⁡ ( n + 1 ) ⩾ h ( r o o t ) 2 ↔    h ( r o o t ) ⩽ 2 log ⁡ ( n + 1 ) n ⩾ 2 h ( r o o t ) 2 − 1 ↔    log ⁡ ( n + 1 ) ⩾ h ( r o o t ) 2 ↔    h ( r o o t ) ⩽ 2 log ⁡ ( n + 1 ) {\displaystyle n\geqslant 2^{\frac {h(root)}{2}}-1\leftrightarrow \;\log {(n+1)}\geqslant {\frac {h(root)}{2}}\leftrightarrow \;h(root)\leqslant 2\log {(n+1)}}n\geqslant 2^{{{\frac {h(root)}{2}}}}-1\leftrightarrow \;\log {(n+1)}\geqslant {\frac {h(root)}{2}}\leftrightarrow \;h(root)\leqslant 2\log {(n+1)} n22h(root)1log(n+1)2h(root)h(root)2log(n+1)n22h(root)1log(n+1)2h(root)h(root)2log(n+1)

    因 此 根 的 高 度 是 O ( log ⁡ n ) 因此根的高度是{\displaystyle {\text{O}}(\log n)} O(logn)

    在这里插入图片描述

    展开全文
  • 三分钟看懂红黑树

    2020-01-03 18:00:22
    一、在理解红黑树之前,先一些二叉查找树 二叉查找树特性:左字数上所有的节点的值都小于或等于他的根节点上的值 右子树上所有节点的值均大于或等于他的根节点的值 左、右子树也跟别为平衡二叉树 举个...

    一、在理解红黑树之前,先看一些二叉查找树

    二叉查找树特性:左字数上所有的节点的值都小于或等于他的根节点上的值

                                 右子树上所有节点的值均大于或等于他的根节点的值

                                 左、右子树也跟别为平衡二叉树

          举个二叉树的例子:

                

          可以看到如果要查询10的话,10>9

                

          因此到他的右子树,右子树根节点为13,10<13

                

          因此到其左子树,左子树根节点为11>10

                

          到其左子树,为10,找到相应的节点

                

          不过二叉查找树有一些问题,可能会出现不平横的情况,即如下图所示的情况

                

          从这种情况可以看出,明显存在左子树和右子树深度相差过多,在使用平衡情况下的二叉查找树是时间复杂度为logn,而出现这种极端情况的话,想要查9的位置就需要每一次都遍历下一个右子树,很有可能时间复杂度变为n(与数组普通查询的时间复杂度相同)

          基于上述情况,引入了平衡二叉树,红黑树即为平衡二叉树的一种

    二、红黑树

    特性:节点是红色或黑色

               根节点一定是黑色

               每个叶节点都是黑色的空节点(NIL节点)

              每个红节点的两个子节点都是黑色的(从每个叶子到跟的所有路径上不能有两个连续的红节点)(即对于层来说除了NIL节点,红黑节点是交替的,第一层是黑节点那么其下一层肯定都是红节点,反之一样)

              从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

     

          正是由于这些原因使得红黑树是一个平衡二叉树

    红黑树的例子

                

    向红黑树中插入节点14(一般默认插入节点是红色的)

                

    在原树上插入20

                

          可以看到,插入以后树已经不是一个平衡的二叉树,而且并不满足红黑树的要求,因为20和21均为红色,这种情况下就需要对红黑树进行变色,21需要变为黑色,22就会变成红色,如果22变成红色,则需要17和25都变成黑色

                

          而17变成黑色显然是不成立的,因为如果17变为黑色,那么13就会变为红色,不满足二叉树的规则,因此此处需要进行另一个操作---------左旋操作

          左旋:下图就是一个左旋的例子,一般情况下,如果左子树深度过深,那么便需要进行左旋操作以保证左右子树深度差变小

                

          对于上图由于右子树中17变为黑色以后需要把13变成红色,因此进行一次左旋,将17放在根节点,这样既可保证13为红色,左旋后结果

                

          而后根据红黑树的要求进行颜色的修改

                

          进行左旋后,发现从根节点17,到1左子树的叶子节点经过了两个黑节点,而到6的左叶子节点或者右叶子节点要经历3个黑节点,很显然也不满足红黑树,因此还需要进行下一步操作,需要进行右旋操作

          右旋:与左旋正好相反

                

          由于是从13节点出现的不平衡,因此对13节点进行右旋,得到结果

                

          而后再对其节点进行变色,得到结果

                

    这便是红黑树的一个变换,它主要用途有很多,例如java中的TreeMap以及JDK1.8以后的HashMap在当个节点中链表长度大于8时都会用到。

    展开全文
  • 红黑树

    2016-11-23 17:59:40
    很多人认为红黑树很难,其实红黑树并没有我们想象中的那么难 首先我们先看红黑树到底是干什么的 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联...

    很多人认为红黑树很难懂,其实红黑树并没有我们想象中的那么难

    首先我们先看红黑树到底是干什么的

    红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。
    红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。
    它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

    我们看到,关于二叉树基本上都是干这样的事,每次排除一个子树,递归另一个子树,使其时间复杂度为O(log n),然后以一种特殊的方法去维护他

    比如说  

               50

          25      60

    13    30   55   88

    这样的树,他的左孩子总是比父节点小,右孩子总是比父节点大,假设我们搜索55,其实就相当于我们先询问

    节点1(50)   发现55比他大,然后去其右孩子问

    节点3(60)   发现55比他小,然后去其左孩子问

    节点6(55)   找到了~


    就是这样。但如果我现在要插入一些数怎么办呢?比如说我要加一个31,很显然我应该放在30的右孩子

    那么就变成了

               50

          25      60

    13    30   55   88

               31

    我要再来一个32呢,还得往下,再来一个33呢? 所以我们看出,如果我不改变整个树的结构,那么我很难构造出真正实现O(log n)的二叉树

    因为随着插入、删除等操作,其父节点不会再是一组数列的中心点了。那么到底要怎么改变树的结构,成为了不同查找树算法的区分。


    好了,现在我们大概明白它要干什么事了,然后我们再看看红黑树为什么要分红和黑

    这里我们要引用一下2-3树的知识。

    2-3树是最简单的B-树(或-树)结构,其每个非叶节点都有两个或三个子女,而且所有叶都在统一层上。2-3树不是二叉树,其节点可拥有3个孩子。不过,2-3树与满二叉树相似。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数,即至少有2^h-1个节点。

    就是说,为了保证查找树的平衡性,我们需要一些灵活性,因此在这里我们允许树中的一个结点保存多个键。
    2-结点:含有一个键(及值)和两条链接,左链接指向的2-3树中的键都小于该结点,右链接指向的2-3树中的键都大于该结点。
    3-结点:含有两个键(及值)和三条链接,左链接指向的2-3树中的键都小于该结点,中链接指向的2-3树中的键都位于该结点的两个键之间,右链接指向的2-3树中的键都大于该结点。

    看了上篇博客线段树的同学可能会明白一些       http://blog.csdn.net/sm9sun/article/details/53302873

    说白了,就是2-3树,他的值可以是某个点,也可以是一个线段。也就是说:

    2叉:

               【a】

    【小于a】【大于a】


    3叉:

                     【a,b】

    【小于a】【ab之间】【大于b】


    好了,那么红黑树和2-3树有什么联系呢??

    红黑树的本质:
    红黑树是对2-3查找树的改进,它能用一种统一的方式完成所有变换。

    替换3-结点
    红黑树背后的思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。
    我们将树中的链接分为两种类型:红链接将两个2-结点连接起来构成一个3-结点,黑链接则是2-3树中的普通链接。确切地说,我们将3-结点表示为由一条左斜的红色链接相连的两个2-结点。这种表示法的一个优点是,我们无需修改就可以直接使用标准二叉查找树的get()方法。对于任意的2-3树,只要对结点进行转换,我们都可以立即派生出一颗对应的二叉查找树。我们将用这种方式表示2-3树的二叉查找树称为红黑树。



    *以下内容转载于http://blog.csdn.net/yang_yulei/article/details/26066409





    所以我们看一下红黑树的性质到底在说些什么:

    性质1. 节点是红色或黑色。(2-3树变型)
    性质2. 根节点是黑色。
    性质3 每个叶节点(NIL节点,空节点)是黑色的。
    性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)(一个节点不可能与两条红链接相连
    性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。(黑链接(2叉)平衡)


    接下来我们说一下为什么左旋、右旋,其实特别简单,就如上文说的一样,

    父节点无法保证自己处于平衡状态,那么就必须通过旋转来保证树的平衡性

    比如:

               50

          25      60

    13    30   

    当我插入一个10时,左边的深度比右边深2层,那么就必须需要旋转

    那么就变成了

               25

          13     50

      10      30    60


    所以具体的着色、旋转操作要看我们插入删除不同的情况而定

    *以下内容转载于http://blog.csdn.net/v_JULY_v/article/details/6105630

    红黑树插入的几种情况:
    情况1,z的叔叔y是红色的。
    情况2:z的叔叔y是黑色的,且z是右孩子
    情况3:z的叔叔y是黑色的,且z是左孩子
    红黑树删除的几种情况。
    情况1:x的兄弟w是红色的。
    情况2:x的兄弟w是黑色的,且w的俩个孩子都是黑色的。
    情况3:x的兄弟w是黑色的,且w的左孩子是红色,w的右孩子是黑色。
    情况4:x的兄弟w是黑色的,且w的右孩子是红色的。


    设:要插入的节点为N,父亲节点P,祖父节点G,叔叔节点U,兄弟节点S


    如下图所示,找一个节点的祖父和叔叔节点:
    node grandparent(node n)     //祖父
    {
         return n->parent->parent;
     }
     node uncle(node n)              //叔叔
    {
         if (n->parent == grandparent(n)->left)
             return grandparent(n)->right;
         else
             return grandparent(n)->left;
     }



    红黑树插入的几种情况
    情形1: 新节点N位于树的根上,没有父节点
    void insert_case1(node n) {
         if (n->parent == NULL)
             n->color = BLACK;
         else
             insert_case2(n);
     }


    情形2: 新节点的父节点P是黑色
    void insert_case2(node n) {
         if (n->parent->color == BLACK)
             return; /* 树仍旧有效 */
         else
             insert_case3(n);
     }
    情形3:父节点P、叔叔节点U,都为红色,
    void insert_case3(node n) {
         if (uncle(n) != NULL && uncle(n)->color == RED) {
             n->parent->color = BLACK;
             uncle(n)->color = BLACK;
             grandparent(n)->color = RED;
             insert_case1(grandparent(n));   //因为祖父节点可能是红色的,违反性质4,递归情形1.
         }
         else
             insert_case4(n);   //否则,叔叔是黑色的,转到下述情形4处理。
    情形4: 父节点P是红色,叔叔节点U是黑色或NIL; 
    插入节点N是其父节点P的右孩子,而父节点P又是其父节点的左孩子。
    void insert_case4(node n) {
         if (n == n->parent->right && n->parent == grandparent(n)->left) {
             rotate_left(n->parent);
             n = n->left;
         } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
             rotate_right(n->parent);
             n = n->right;
         }
         insert_case5(n);    //转到下述情形5处理。
    情形5: 父节点P是红色,而叔父节点U 是黑色或NIL,
    要插入的节点N 是其父节点的左孩子,而父节点P又是其父G的左孩子。
    void insert_case5(node n) {
         n->parent->color = BLACK;
         grandparent(n)->color = RED;
         if (n == n->parent->left && n->parent == grandparent(n)->left) {
             rotate_right(grandparent(n));
         } else {
             /* 反情况,N 是其父节点的右孩子,而父节点P又是其父G的右孩子 */
             rotate_left(grandparent(n));
         }
     }


    红黑树删除的几种情况
    上文我们约定,兄弟节点设为S,我们使用下述函数找到兄弟节点:
    struct node * sibling(struct node *n)  //找兄弟节点
    {
            if (n == n->parent->left)
                    return n->parent->right;
            else
                    return n->parent->left;
    }

    情况1: N 是新的根。
    void
    delete_case1(struct node *n)
    {
            if (n->parent != NULL)
                    delete_case2(n);
    }
    情形2:兄弟节点S是红色
    void delete_case2(struct node *n)
    {
            struct node *s = sibling(n);
     
            if (s->color == RED) {
                    n->parent->color = RED;
                    s->color = BLACK;
                    if (n == n->parent->left)
                            rotate_left(n->parent);  //左旋
                    else
                            rotate_right(n->parent);
            } 
            delete_case3(n);
    }


    情况 3: 兄弟节点S是黑色的,且S的俩个儿子都是黑色的。但N的父节点P,是黑色。
    void delete_case3(struct node *n)
    {
            struct node *s = sibling(n);
     
            if ((n->parent->color == BLACK) &&
                (s->color == BLACK) &&
                (s->left->color == BLACK) &&
                (s->right->color == BLACK)) {
                    s->color = RED;
                    delete_case1(n->parent);
            } else
                    delete_case4(n);
    }


    情况4: 兄弟节点S 是黑色的、S 的儿子也都是黑色的,但是 N 的父亲P,是红色。
    void delete_case4(struct node *n)
    {
            struct node *s = sibling(n);
     
            if ((n->parent->color == RED) &&
                (s->color == BLACK) &&
                (s->left->color == BLACK) &&
                (s->right->color == BLACK)) {
                    s->color = RED;
                    n->parent->color = BLACK;
            } else
                    delete_case5(n);
    }
    情况5: 兄弟S为黑色,S 的左儿子是红色,S 的右儿子是黑色,而N是它父亲的左儿子。
    //此种情况,最后转化到下面的情况6。
    void delete_case5(struct node *n)
    {
            struct node *s = sibling(n);
     
            if  (s->color == BLACK) 
                    if ((n == n->parent->left) &&
                        (s->right->color == BLACK) &&
                        (s->left->color == RED)) { 
                            // this last test is trivial too due to cases 2-4.
                            s->color = RED;
                            s->left->color = BLACK;
                            rotate_right(s);
                    } else if ((n == n->parent->right) &&
                               (s->left->color == BLACK) &&
                               (s->right->color == RED)) {
                           // this last test is trivial too due to cases 2-4.
                            s->color = RED;
                            s->right->color = BLACK;
                            rotate_left(s);
                    }
            }
            delete_case6(n);  //转到情况6


    情况6: 兄弟节点S是黑色,S的右儿子是红色,而 N 是它父亲的左儿子。
    [对应我第二篇文章中,情况4:x的兄弟w是黑色的,且w的右孩子时红色的。]
    void delete_case6(struct node *n)
    {
            struct node *s = sibling(n);
     
            s->color = n->parent->color;
            n->parent->color = BLACK;
     
            if (n == n->parent->left) {
                    s->right->color = BLACK;
                    rotate_left(n->parent);
            } else {
                    s->left->color = BLACK;
                    rotate_right(n->parent);
            }
    }

    红黑树完整代码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef int DataTypedef;
    typedef struct RBTREENODE
    {
    	int data;
    	char color;
    	struct RBTREENODE *left;
    	struct RBTREENODE *right;
    	struct RBTREENODE *p;
    }rbtreeNode;
    
    typedef struct RBTREE
    {
    	rbtreeNode *root;
    	rbtreeNode *nil;
    }rbTree;
    
    #define OK 1
    #define ERR -1
    
    void rbtree_free_node(rbTree *T, rbtreeNode *p)
    {
        if(p != T->nil)
        {
            rbtree_free_node(T, p->left);
            rbtree_free_node(T, p->right);
            free(p);
        }
    }
    
    void rbtree_show_node(rbTree *T, rbtreeNode *p)
    {
        if(p != T->nil)
        {
            printf("%02d ", p->data);
            p->color == 'R' ? printf(" R\n") : printf(" B\n");
            rbtree_show_node(T, p->left);
            rbtree_show_node(T, p->right);
        }
    }
    
    void left_rotate(rbTree *T, rbtreeNode * x)
    {
    	rbtreeNode *y = x->right;
    
    	x->right = y->left;
    	if(y->left != T->nil)
    		y->left->p = x;
    	y->p = x->p;
    	if(x->p == T->nil)
    		T->root = y;
    	else if(x == x->p->left)
    		x->p->left = y;
    	else
    		x->p->right = y;
    
    	y->left = x;
    	x->p = y;
    }
    
    void right_rotate(rbTree *T, rbtreeNode *x)
    {
    	rbtreeNode * y = x->left;
    
    	x->left = y->right;
    	if(y->right != T->nil)
    		y->right->p = x;
    	y->p = x->p;
    	if(x->p == T->nil)
    		T->root = y;
    	else if(x == x->p->left)
    		x->p->left = y;
    	else
    		x->p->right = y;
    
    	y->right = x;
    	x->p = y;
    }
    
    int rbtree_fixup(rbTree *T, rbtreeNode *z)
    {
        rbtreeNode *y = NULL;
    
        /*
        * while循环在每次迭代的开头都保持3个部分的不变式
        * 1 节点z是红色节点
        * 2 如果z.p是根节点,则z.p是黑节点
        * 3 如果有任何红黑性质被破坏,则至多只有一条被破坏,或是性质2(根为黑色节点),或是性质4(如果一个节点是红色的,
        *   则它的两个子节点都是黑色的)
        */
        while(z->p->color == 'R')
        {
            if(z->p == z->p->p->left)//在所有的情况中,z的祖父节点z.p.p是黑色的,以为z.p是红色的
            {
                y = z->p->p->right;
                // Case1: z uncle node y is red
                if(y->color == 'R')
                {
                    z->p->color = 'B';
                    y->color = 'B';
                    z->p->p->color = 'R';
                    z = z->p->p;
                }
                else
                {
                    // Case2: z uncle node y is black, but z is right node
                    if(z == z->p->right)
                    {
                        z = z->p;
                        left_rotate(T, z);
                    }
                    // Case3: z uncle node y is black, but z is left node
                    z->p->color = 'B';
                    z->p->p->color = 'R';
                    right_rotate(T, z->p->p);
                }
            }
            else
            {
                y = z->p->p->left;
                if(y->color == 'R')
                {
                    z->p->color = 'R';
                    y->color = 'B';
                    z->p->p->color = 'R';
                    z = z->p->p;
                }
                else
                {
                    if(z == z->p->left)
                    {
                        z = z->p;
                        right_rotate(T, z);
                    }
    
                    z->p->color = 'B';
                    z->p->p->color = 'R';
                    left_rotate(T, z->p->p);
    
                }
            }
        }
        T->root->color = 'B';
    
        return OK;
    }
    
    /*
    * blow funtion is used in other file
    */
    
    rbTree * rbtree_init()
    {
    	rbTree *T = NULL;
    
    	T = (rbTree *)malloc(sizeof(rbTree));
    	if(T == NULL)
    	{
    		printf("T no space\n");
    	}
    		
    
    	T->nil = (rbtreeNode *)malloc(sizeof(rbtreeNode));
    	if(T->nil == NULL)
    	{
    		printf("T->nil no space\n");
    	}
    		
    	T->root = T->nil;
    
    	T->nil->data = (1<<31);
    	T->nil->color = 'B';
    	T->nil->left = T->nil;
    	T->nil->right = T->nil;
    	T->nil->p = T->nil;
    
    	return T;
    }
    
    int rbtree_in(rbTree *T, DataTypedef x)
    {
        rbtreeNode *p = T->root;
    
        while(p != T->nil)
        {
            if(x < p->data)
                p = p->left;
            else if(x > p->data)
                p = p->right;
            else
                return OK;
        }
    
        return ERR;
    }
    
    int rbtree_insert(rbTree *T, DataTypedef num)
    {
        rbtreeNode *y = T->nil;
        rbtreeNode *x = T->root;
        rbtreeNode *z = NULL;
    
        if(!rbtree_in(T, num))
        {
            z = (rbtreeNode *)malloc(sizeof(rbtreeNode));
            if(z == NULL)
            {
            	 printf("no space for z in rbtree\n");
    		}        
            z->data = num;
        }
        else
            return ERR;
    
        while(x != T->nil) //y is parent point of x
        {
            y = x;
            if(z->data < x->data)
                x = x->left;
            else
                x = x->right;
        }
        z->p = y;
        if(y == T->nil)
            T->root = z;
        else if(z->data < y->data)
            y->left = z;
        else
            y->right = z;
    
        z->left = T->nil;
        z->right = T->nil;
        z->color = 'R';
    
        if( rbtree_fixup(T, z) )
            return OK;
        else
            return ERR;
    }
    
    rbtreeNode *rbtree_find(rbTree *T, DataTypedef x)
    {
        rbtreeNode *p = T->root;
    
        while(p != T->nil)
        {
            if(x < p->data)
                p = p->left;
            else if(x > p->data)
                p = p->right;
            else
                return p;
        }
    
        return T->nil;
    }
    rbtreeNode *rbtree_findmin(rbTree *T, rbtreeNode *p)
    {
        rbtreeNode *q = p;
    
        while(p != T->nil)
        {
            q = p;
            p = p->left;
        }
    
        return q;
    }
    void rbtree_transplant(rbTree *T, rbtreeNode *u, rbtreeNode *v)
    {
        if(u->p == T->nil)
        {
            T->root = v;
        }
        else if(u == u->p->left)
        {
            u->p->left = v;
        }
        else
        {
            u->p->right = v;
        }
    
        v->p = u->p;
    }
    void rbtree_delete_fixup(rbTree *T, rbtreeNode *x)
    {
        rbtreeNode *w;
    
        while(x != T->root && x->color == 'B')//while循环中,x总是指向一个具有双重黑色的非根界节点
        {
            if(x == x->p->left)
            {
                w = x->p->right;
                if(w->color == 'R') //情况1:x的兄弟节点w是红色
                {
                    w->color = 'B';
                    x->p->color = 'R';
                    left_rotate(T, x->p);
                    w = x->p->right;
                }
    
                if(w->left->color == 'B' && w->right->color == 'B') //情况2:x的兄弟节点w是黑色,而且w的两个子节点都是黑色的
                {
                    w->color = 'R';
                    x = x->p;
                }
                else
                {
                    if(w->right->color == 'B') //情况3:x的兄弟节点w是黑色的,w的左孩子是红色的,w的右孩子是黑色的
                    {
                        w->left->color = 'B';
                        w->color = 'R';
                        right_rotate(T, w);
                        w = x->p->right;
                    }
                    w->color = x->p->color;     //情况4:x的兄弟节点w是黑色的,且w的右孩子是红色的
                    x->p->color = 'B';
                    w->right->color = 'B';
                    left_rotate(T, x->p);
                    x = T->root;
                }
            }
            else//x = x->p->right
            {
                w = x->p->left;
                if(w->color == 'R')
                {
                    w->color = 'B';
                    x->p->color = 'R';
                    right_rotate(T, x->p);
                    w = x->p->left;
                }
    
                if(w->left->color == 'B' && w->right->color == 'B')
                {
                    w->color = 'R';
                    x = x->p;
                }
                else
                {
                    if(w->left->color == 'B')
                    {
                        w->right->color = 'B';
                        w->color = 'R';
                        left_rotate(T, w);
                        w = x->p->left;
                    }
                    w->color = x->p->color;
                    x->p->color = 'B';
                    w->left->color = 'B';
                    right_rotate(T, x->p);
                    x = T->root;
                }
            }
        }
        x->color = 'B';
    }
    void rbtree_delete(rbTree *T, DataTypedef data)
    {
        rbtreeNode *z = rbtree_find(T, data);
        rbtreeNode *y;
        rbtreeNode *x;
        char y_oldcolor;
    
        if(z == T->nil)
        {
            printf("the rbtree hasn't %d\n", data);
            return;
        }
    
        y = z;
        y_oldcolor = y->color;
        if(z->left == T->nil)
        {
            x = z->right;
            rbtree_transplant(T, z, z->right);
        }
        else if(z->right == T->nil)
        {
            x = z->left;
            rbtree_transplant(T, z, z->left);
        }
        else
        {
            y = rbtree_findmin(T, z->right);
            y_oldcolor = y->color;
            x = y->right;
    
            if(y->p == z)
            {
                x->p = y;
            }
            else
            {
                rbtree_transplant(T, y, y->right);
                y->right = z->right;
                y->right->p = y;
            }
    
            rbtree_transplant(T, z, y);
            y->left = z->left;
            y->left->p = y;
            y->color = z->color;
        }
    
        if(y_oldcolor == 'B')
            rbtree_delete_fixup(T, x);
    
        free(z);
        //printf("free the node is ok\n\n");
    }
    void rbtree_show(rbTree *T)
    {
        if(T->root != T->nil)
        {
            rbtree_show_node(T, T->root);
            printf("\n");
        }
        else
            printf("This rbtree is empty.\n");
    }
    
    int rbtree_free(rbTree *T)
    {
        if(T->root != T->nil)
        {
            rbtree_free_node(T, T->root);
        }
        free(T->nil);
        free(T);
    
        return OK;
    }
    
    
    int main(void)
    {
        rbTree *T = NULL;
    
        T = rbtree_init();
        int n,value;
        while(~scanf("%d",&n)&&n)
    		{
    			switch(n)
    			{
    				case 1:scanf("%d",&value);rbtree_insert(T, value);break;
    				case 2:rbtree_show(T);break;
    				case 3:scanf("%d",&value); rbtree_delete(T, value);break;
    				default:break;
    			}
            }
        rbtree_free(T);
        return 0;
    }


    最后,推荐本人认为两个比较不错的博客,强烈建议大家去看一下

    http://blog.csdn.net/v_JULY_v/article/details/6105630         含多篇关于红黑树的讲解,内容详细。

    http://blog.csdn.net/yang_yulei/article/details/26066409        直接说明红黑树与2-3树的联系,思路清晰。

    展开全文
  • 红黑树你搞了没

    2019-10-06 17:44:13
    红黑树的定义比较简单,无非是在插入和删除的过程中自平衡规则多了一些,不过再多也只是个位数而已 Linux虚拟内存管理,Java中的TreeMap和TreeSet,以及JDK1.8之后的HashMap也有用到红黑树数据结构 红黑树是一种 ...

    红黑树的定义比较简单,无非是在插入和删除的过程中自平衡规则多了一些,不过再多也只是个位数而已

    Linux虚拟内存管理,Java中的TreeMap和TreeSet,以及JDK1.8之后的HashMap也有用到红黑树数据结构


    红黑树是一种 自平衡 的二叉树,所谓的自平衡是指在插入和删除的过程中,红黑树会采取一定的策略对树的组织形式进行调整,以尽可能的减少树的高度,从而节省查找的时间。

    红黑树的特性如下:

    1.结点是红色或黑色
    2.根结点始终是黑色
    3.叶子结点(NIL 结点)都是黑色
    4.红色结点的两个直接孩子结点都是黑色(即从叶子到根的所有路径上不存在两个连续的红色结点)
    5.从任一结点到每个叶子的所有简单路径都包含相同数目的黑色结点


    以上性质保证了红黑树在满足平衡二叉树特征的前提下,还可以做到 从根到叶子的最长路径最多不会超过最短路径的两倍 ,这主要是考虑两个极端的情况,由性质 4 和 5 我们可以知道在一棵红黑树上从根到叶子的最短路径全部由黑色结点构成,而最长结点则由红黑结点交错构成(始终按照一红一黑的顺序组织),又因为最短路径和最长路径的黑色结点数目是一致的,所以最长路径上的结点数是最短路径的两倍。

    自平衡策略
    对于一棵红黑树的操作最基本的无外乎增删改查,其中查和改都不会改变树的结构,所以与普通平衡二叉树操作无异。剩下的就是增删操作,插入和删除都会破坏树的结构,不过借助一定的平衡策略能够让树重新满足定义。

    平衡策略可以简单概括为三种: 左旋转 、 右旋转 ,以及 变色 。

    在插入或删除结点之后,只要我们沿着结点到根的路径上执行这三种操作,就可以最终让树重新满足定义。

    左旋转
    对于当前结点而言,如果右子结点为红色,左子结点为黑色,则执行左旋转,如下图:

     

    https://github.com/plotor/algorithm-design

    演示的网站:

    https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

     

     再说一说二叉树

     https://www.processon.com/view/5b3b413ee4b056f7f0beae42

     

     

     

     

     

     

     

     

     

     

     

     

     

    转载于:https://www.cnblogs.com/qianjinyan/p/11151790.html

    展开全文
  • 红黑树能保持高效的查找,一般取时间复杂度为O(log2n),由于高效,这个结构也比较复杂,所以很多人(包括我自己)都一直搞不懂红黑树到底是怎么插入、删除节点的。此篇博客,博主将图文并茂的一层一层揭开红黑树神秘...
  • 自制的红黑树教程与实验平台:https://github.com/Jinzhe-Zhang/Red_Black_Tree 界面: 命令台操作(动图,可能会卡): 查看每一步操作的讲解(动图,可能...几个月前,红黑树给我的感觉就是: 听说过一百次 但就是
  • 懂红黑树

    2020-05-09 23:04:42
    要搞懂红黑树需要的知识 对二叉树有一定的了解 红黑树的特性 使用红黑树的好处 左旋和右旋 java中的传值引用(个人觉得有必要了解,不然会懵) …大概就这么多吧 二叉树 这是一颗完全二叉树。 二叉树跟普通的树的...
  • 终于搞懂红黑树!--红黑树的原理及操作

    千次阅读 多人点赞 2019-07-30 15:17:04
    红黑树( Red black tree)是种自平衡二叉查找树,在计算机科学中用到的一种数据结构。 它是在1972年由 Rudolf Bayer发明的当时被称为平衡二叉B树( symmetric binary B-trees)。后来,在1978年被 Leo. guibas和 ...
  • 前言 红黑树,对很多童鞋来说,是既熟悉又陌生。熟悉是因为在校学习期间,准备...那么我将带领大家重新认识下红黑树,用简单的语言,搞懂红黑树。 在学习红黑树之前,咱们需要先来理解下二叉查找树(BST)。 二...
  • 前戏红黑树,对很多童鞋来说,是既熟悉又陌生。...那么我将带领大家重新认识下红黑树,用简单的语言,搞懂红黑树。在学习红黑树之前,咱们需要先来理解下二叉查找树(BST)。二叉查找树要想了解...
  • 红黑树简介红黑树是一种自平衡的二叉查找树,是一种高效的查找树。它是由 Rudolf Bayer 于1972年发明,在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick ...
  • 彻底弄懂红黑树

    2021-01-15 23:26:14
    红黑树的插入和删除操作红黑树的插入和删除操作概述从2-3-4树开始讲起插入操作删除操作 红黑树的插入和删除操作 概述 我们知道二叉搜索树在一些特定的情况下会退化成链表,比如插入有序的数据的时候。为了解决这个...
  • 红黑树性质  1、每个结点或是红色的,或是黑色的   2、根节点是黑色的   3、每个叶结点(NIL)是黑色的   4、如果一个节点是红色的,则它的两个儿子都是黑色的。   5、对于每个结点,从该结点到其叶子结点...
  • 红黑树详解---彻底搞懂红黑树

    千次阅读 2017-03-05 20:23:09
    红黑树有以下五个性质: 1.根节点为黑色 2.节点为红色或者黑色 3.每个叶子节点NIL为黑色 4.节点为红色,则两个孩子都为黑色(即每条路径上能有连续两个红色) 5.任意一个节点到其所有子孙节点的NIL的路径上包含相同...
  • 17张图带你解析红黑树的原理!保证你能看懂

    万次阅读 多人点赞 2019-11-20 16:02:38
    由于红黑树本质上就是一棵二叉查找树,所以在了解红黑树之前,咱们先来下二叉查找树。 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空...
  • 红黑树详细分析(图文详解),了都说好

    万次阅读 多人点赞 2019-10-15 17:39:05
    文章目录红黑树简介红黑树的性质红黑树操作旋转操作插入情况一情况二情况三情况四情况五插入总结删除情况一情况二情况三情况四情况五情况六删除总结总结 红黑树简介 红黑树是一种自平衡的二叉查找树,是一种高效的...
  • 前言 红黑树,对不少人来说是个比较头疼的名字,在网上搜资料也很少有讲清楚其演变来源的,多数一... 本文介绍红黑树,暂时涉及任何代码,只是帮助你理解红黑树的演变来源,树结构中红黑色具体含义,保证你理解了过

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,121
精华内容 5,248
关键字:

红黑树看不懂