精华内容
下载资源
问答
  • 红黑树为什么要旋转
    千次阅读
    2020-03-13 22:38:57

    在这里插入图片描述
    特性(除了具备二叉查找树的特性外,还具备如下特性):
    (1)节点是红色或者黑色
    (2)根节点是黑色
    (3)每个叶子节点(也叫终端节点,简称“叶子”)都是黑色的空节点(NIL节点)
    (4)每个红色节点的两个子节点都是黑色。(从每个叶子节点到根节点的路径上不能有两个连续的红色节点)
    (5)从任一节点到其每个叶子的所有路劲都包含相同数目的黑色节点

    优势:
    (1)自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍,解决了二叉查找树容易不平衡的缺陷(在某些情况下会退化成一个线性结构),提高了读取性能(树越平衡,读取性能就越好)。
    (2)虽然AVL树具有更高的读取性能(因为平衡性更好),但是当插入或删除节点时,AVL树要复杂很多,红黑树在插入或删除节点方面具有更高的效率。

    在什么情况下需要变色,在什么情况下需要旋转?
    在红黑二叉树中插入节点或删除节点后,如果破坏了红黑树的规则(也就是上述的特性),则需要对修改后的红黑树进行调整,使其重新符合红黑树的规则。首先是变色(往往需要多次变色,一次改变一个节点的颜色),当变色无能为力时,就使用旋转,旋转一次之后,然后再继续多次变色,如此反复循环,直到修改后的红黑树重新符合规则。

    更多相关内容
  • 本篇主要谈谈对红黑树的理解,大家都晓得JDK8中的hashmap底层是数组+链表+红黑树实现的,当面试官问你:加上红黑树实现呢?? 那我们首先从概念来了解一下: 一、什么红黑树红黑树是一个接近平衡的二叉...

    本篇主要谈谈对红黑树的理解,大家都晓得JDK8中的hashmap底层是数组+链表+红黑树实现的,当面试官问你:为啥要加上红黑树实现呢??
    那我们首先从概念来了解一下:

    一、什么是红黑树?

    红黑树是一个接近平衡的二叉查找树,也就是说二叉查找树的特性红黑树应该都具备,那么具备哪些特性呢?

    • 左子树小于根节点
    • 右子树大于根节点
    • 左右子树也分别为二叉查找树

    换句话就是有序的。那么有什么优点呢?
    在这里插入图片描述
    比如我要插入2,该怎么插入呢?
    和5比较,<5,到左侧;和3比较,<3到左侧;和1比较,>1,到1的右侧;
    比如查询1呢?该如何查询?其实一思考,查询的过程和插入的过程是一样的,其实也就是二分查找的思想。所查询的次数也就是树的高度。其时间复杂度为logn.
    那问题来了,什么是红黑树呢?我们如上举例是一个平衡的二叉树,因为根节点是5。但是当有一个诸如这样的序列:1,4,5,7,8,9那么这个二叉树会变成什么样?
    在这里插入图片描述
    那么时间复杂度就变成了O(N),当数据量足够大的情况下,那速度就可想而知。
    所以我们便衍生出了红黑树,一个自平衡的二叉树,除了具备二叉树的特性,还具备以下特性:

    • 每个结点不是红色就是黑色
    • 不可能有两个红色结点相连,每个叶子都是空的黑结点(null),不存储数据
    • 根节点都是黑色root
    • 每个结点,从该结点到其可达叶子结点的所有路径,都包含相同数目的黑色结点

    在这里插入图片描述
    当插入或者删除的时候,红黑树的规则可能就会被打破,那么就得做出一些调整,去维持这些规则。

    二、基本操作

    1、变色(黑变红,红变黑)

    要求:

    • 父节点是红色;
    • 叔父节点也是红色;

    变更:

    • 将父节点和叔父节点变为黑色;
    • 爷爷节点变为红色;
    • 把指针指向爷爷节点,变为下一步要操作的结点;

    在这里插入图片描述
    6是想要插入的数值,发现父和叔节点都是红色,则采用变色处理:
    在这里插入图片描述

    2、左旋

    要求:

    • 当前父节点是红色;
    • 叔父节点是黑色;
    • 当前的结点是右子树;
    • 指针变化到父节点(未旋转之前的父节点)

    在这里插入图片描述
    上一步已经把指针指向了爷爷节点,我们发现12这个爷爷节点符合左旋的规则,所以进行左旋。
    12的父结点变为自己的左结点,自己的左结点给了父节点作为他的右结点。如下图:
    在这里插入图片描述

    3、右旋

    要求

    • 当前父节点是红色;
    • 叔父节点是黑色;
    • 当前的结点是左子树;
    • 以爷爷节点右旋;

    变更

    • 父节点变为黑色;
    • 爷爷变为红色;

    如上例子还未到平衡二叉树,左旋完成之后,将结点指向了操作结点5。5的父节点是红色,叔父节点是黑色,且5是左子树,满足右旋,将爷爷节点变为红色,父节点变为红色,移动位置,如下图:
    在这里插入图片描述

    如上则完成了红黑树的要求。整个变更流程如下图,
    在这里插入图片描述
    分析下来,通过插入一个节点对于红黑树的基本操作有了一个基本的了解。所以其时间复杂度都是接近于logn。

    三、为何要用红黑树?

    最熟悉的用红黑树的地方就是jdk8对应的hashmap,红黑树其实也是采用的二分法,相比于二叉查找树,可以避免单一链表,腿脚部分的特殊情况的出现。最坏的情况,时间复杂度也就是接近logn。同样的道理,这也是为何不用数组+链表,而又加入了红黑树的原因,也是为了避免链表过长,降低了效率。那为何不直接用红黑树呢?还得加上链表?因为红黑树需要进行左旋,右旋操作, 而单链表不需要。

    展开全文
  • 为什么要红黑树 想必大家对二叉树搜索树都不陌生,首先看一下二叉搜索树的定义:二叉搜索树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均...

    为什么要有红黑树

    想必大家对二叉树搜索树都不陌生,首先看一下二叉搜索树的定义:
    二叉搜索树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
    从理论上来说,二叉搜索树的查询、插入和删除一个节点的时间复杂度均为O(log(n)),已经完全可以满足我们的要求了,那么为什么还要有红黑树呢?
    我们来看一个例子,向二叉搜索树中依次插入(1,2,3,4,5,6),插入之后是这样的
    退化成链表的二叉搜索树
    可以看到,在这种情况下,二叉搜索树退化成了链表!!!这时候查询、插入和删除一个元素的时候,时间复杂度变成了O(n),显然这是不能接受的。出现这种情况情况的原因是二叉搜索树没有自平衡的机制,所以就有了平衡二叉树的概念。
    平衡二叉树(Balanced Binary Tree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
    还是刚刚的例子,假如我们用平衡二叉树来实现的话,插入完元素后应该是下面这样的(不唯一)
    自平衡的二叉树
    平衡二叉树保证了在最差的情况下,二叉树依然能够保持绝对的平衡,即左右两个子树的高度差的绝对值不超过1。但是这又会带来一个问题,那就是平衡二叉树的定义过于严格,导致每次插入或者删除一个元素之后,都要去维护二叉树整体的平衡,这样产生额外的代价又太大了。二叉搜索树可能退化成链表,而平衡二叉树维护平衡的代价开销又太大了,那怎么办呢?这就要谈到“中庸之道”的智慧了。说白了就是把平衡的定义适当放宽,不那么严格,这样二叉树既不会退化成链表,维护平衡的开销也可以接受。没错,这就是我们要谈的红黑树了。首先看一下红黑树的定义:
    红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须除了满足二叉搜索树的性质外,还要满足下面的性质:
    性质1:每个节点要么是黑色,要么是红色。
    性质2:根节点是黑色。
    性质3:每个叶子节点(NIL)是黑色。
    性质4:每个红色结点的两个子结点一定都是黑色。
    性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
    这就是红黑树的五条性质。我相信很多人都看到过,能背下来的也不在少数,但是真正理解为什么要这样定义的恐怕就不多了。下面就从2-3树的角度来谈谈红黑树的定义。

    从2-3树来看红黑树

    一般我们接触最多的是二叉树,也就是一个父节点最多有两个子节点。2-3树与二叉树的不同之处在于,一个父节点可以有两个子节点,也可以有三个子节点,并且其也满足类似二叉搜索树的性质。还有最重要的,2-3树的所有叶子节点都在同一层,且最后一层不能有空节点,类似于满二叉树。
    我们依次插入10,9,8,7,6,5,4,3,2,1来看一下2-3树是如何进行自平衡的。
    2-3树在插入元素之前首先要进行一次未命中的查找,然后将元素插入叶子节点中,之后再进行平衡操作,下面具体说明。
    首先插入10,如下图
    2-3树中插入10
    然后插入9,9小于10,2-3树在插入时要将9融入10这个叶子节点中(当然也是根节点),融合完成后如下:
    2-3树中插入9
    这是一个3节点,不用执行平衡操作。2-3树中把有两个元素,三个子节点的节点称为3节点,把有一个元素,两个子节点的的节点称为2节点。
    接着插入8,插入8的时候同样要先融入叶子节点中,如下图左侧所示
    2-3树中插入8
    8融入叶子节点后,该结点便拥有了3个元素,不满足2-3树的定义,这时就要把3节点进行分裂,即把左侧和右侧的元素分裂为2节点,而中间的元素抽出,继续融入其父节点,在这里便成为了一个根节点。
    继续插入7,如下
    2-3树中插入7
    插入后,各个节点都满足2-3树的定义,不需要进行平衡操作。
    接着插入6,还是首先找到叶子节点,然后将其融入,如下图左侧所示
    2-3树中插入6
    插入后6、7、8三个元素所在的叶子节点不再满足2-3树的定义,需要进行分裂,即抽出元素7融入父节点,6和8分裂为7的左右子节点。
    接着插入5,如下图所示,同样不需要进行平衡操作
    2-3树中插入5
    接着插入4,还是首先找到叶子节点,然后将其融入,如下图左侧所示
    2-3树中插入4
    插入后4、5、6三个元素所在的叶子节点不再满足2-3树的定义,需要进行分裂,即抽出元素5融入父节点,4和6分裂为5的左右子节点。5融入父节点后,该结点便有了5、7、9三个元素,因而需要继续分裂,元素7成为新的根节点,5和9成为7的左右子节点。
    接着插入3,3融入4所在的叶子节点中,不需要进行平衡操作
    2-3树中插入3
    接着插入2,还是首先找到叶子节点,然后将其融入,如下图左侧所示
    2-3树中插入2
    插入后2、3、4三个元素所在的叶子节点不再满足2-3树的定义,需要进行分裂,即抽出元素3融入父节点,2和4分裂为3的左右子节点,3融入5所在的父节点中。
    最后插入2,同样先找到叶子节点,然后将其融入,如下图所示
    2-3树中插入1
    至此,我们便完成了在2-3树中依次插入10,9,8,7,6,5,4,3,2,1,并且2-3树始终维护着平衡。怎么样,是不是很神奇。

    再看红黑树

    那么红黑树与2-3树有什么关系呢?现在我们对2-3树进行改造,改造成一个二叉树。怎么改造呢?对于2节点,保持不变;对于3节点,我们首先将3节点中左侧的元素标记为红色,如下图2所示。
    2-3树到红黑树的改造
    然后我们将其改造成图3的形式;再将3节点的位于中间的子节点的父节点设置为父节点中那个红色的节点,如图4的所示;最后我们将图4的形式改为二叉树的样子,如图5所示。图5是不是很熟悉,没错,这就是我们常常提到的大名鼎鼎的红黑树了。
    下面我们回过头再看下红黑树的五条性质。
    从2-3树看红黑树
    性质1:每个节点要么是黑色,要么是红色。
    2-3树中存在2节点和3节点,3节点中左侧的元素便是红色节点,而其他的节点便是黑色节点。
    性质2:根节点是黑色。
    在2-3树中,根节点只能是2节点或者3节点,2节点与3节点在红黑树中的等价形式,如下图所示
    2节点与3节点在红黑树中的等价形式
    显然,无论是哪种情况,根节点都是黑色的。
    性质3:每个叶子节点(NIL)是黑色。
    这里的叶子节点不是指左右子树为空的那个叶子节点,而是指节点不存在子节点或者为空节点被称作叶子节点。在性质2中我们讨论的根节点是黑色的都是讨论根节点不为空的情况,若红黑树是一个空树,那么根节点自然也是空的叶子节点,这时候叶子节点便必然是黑色的。
    性质4:每个红色结点的两个子结点一定都是黑色。
    还是从2-3树的角度来理解,红色节点对应2-3树中3节点左侧的元素,那么它的子节点要么是2节点,要么是3节点。无论是2节点还是3节点对应的节点颜色都是黑色的,这在性质2时已经讨论了。
    性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
    性质5应该是红黑树最重要的一条性质了。2-3树是一颗绝对平衡的树,即2-3树中任意一个节点出发,到达叶子节点后所经过的节点数都是一样的。那么对应到红黑树呢?2-3树中2节点对应到红黑树便是一个黑色的节点,而3节点对应到红黑树是一个红色节点和一个黑色节点。所以,无论是2节点还是3节点,在红黑树中都会对应一个黑色节点。那么2-3树中的绝对平衡,在红黑树中自然就是任意一结点到每个叶子结点的路径都包含数量相同的黑结点了。
    相信大家现在已经对红黑树的五条性质有了更加深刻的体会了。那么我们再看下红黑树维持平衡的三种操作,即变色、左旋、右旋怎么理解呢?
    首先看一下变色,以下图为例,
    红黑树的变色
    在2-3树中插入节点3后,便不再满足2-3树的定义,需要进行分解,将元素2抽出作为1和3的父节点,然后2继续向上融合。
    对应到红黑树中就是,首先插入节点3,在红黑树中新插入的节点默认为红色,然后不满足定义,所以需要进行分解,分解后各个节点都为2节点,所以变为黑色。而2节点需要继续向上融合,故要变成红色。
    接着看一下右旋转,以下图为例,
    红黑树的右旋转
    插入元素1后,进行右旋转操作,首先把2节点与3节点断开连接,同时把2与2的右子树断开连接,然后把2的右子树连接至3的左子树位置,不会违背二分搜索树的性质,然后再把3连接至2的右子树位置。最后还要改变对应节点的颜色,即把2节点的颜色改为原来3节点的黑色,把3节点的颜色改为原来2节点的红色。
    接着看一下左旋转,与右旋转类似,以下图为例,
    红黑树的左旋转
    插入元素3后,进行左旋转操作,首先把2节点与3节点断开连接,同时把3与3的左子树断开连接,然后把3的左子树连接至2的右子树位置,不会违背二分搜索树的性质,然后再把2连接至3的左子树位置。最后还要改变对应节点的颜色,即把2节点的颜色改为原来3节点的红色,把3节点的颜色改为原来2节点的黑色。

    写在最后

    最后需要说的是,本文中提到的红黑树是一种特殊的红黑树——左倾红黑树,即红色节点都是父节点的左子树,其实按照红黑树的定义不必这样。只要满足红黑树的五条性质,就是红黑树,比如完全可以实现右倾红黑树等等,希望大家不要有误解。

     

    展开全文
  • 最后,通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。详细描述如下: 第一步: 将红黑树当作一颗二叉查找树,将节点插入。 红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉...

    一、红黑树的简介 

    R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

    红黑树的特性:

    (1)每个节点或者是黑色,或者是红色。
    (2)根节点是黑色。
    (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
    (4)如果一个节点是红色的,则它的子节点必须是黑色的。 [注意:可以出现父节点和子节点都是黑色]
    (5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

    注意
    (01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
    (02) 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

    红黑树的应用:

    红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。

    • 广泛用于C++的STL中,map和set都是用红黑树实现的.
    • 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.
    • IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查.
    • ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
    • Java集合中的TreeSetTreeMap和hashMap树化为红黑树,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。

    二、红黑树插入删除

    1.红黑树插入最多旋转两次,删除最多旋转三次,为啥之后说。

    2.深入理解五条性质

    (1)每个节点或者是黑色,或者是红色。
    (2)根节点是黑色。
    (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
    (4)如果一个节点是红色的,则它的子节点必须是黑色的。 [注意:可以出现父节点和子节点都是黑色]
    (5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

    1).从第五条我们得知不能直接插入一个黑色节点,会造成黑色节点个数多一,所以插入操作我们都是插入的红色节点,插入后有问题再进行变色或者旋转

    2).如果在一个黑色节点上插入一个红色节点,不会破坏红黑树。在任何节点上插入一个红色节点只会违背性质4,不会直接违背性质5。

    3).最长路径的节点个数不会超过最短路径的节点个数的二倍?

    最短路径是全黑,最长路径是从根节点开始黑、红相间,黑红相间会使红节点和黑节点的数量一样多,就是最短全黑的2倍。

     3.红黑树插入

    我们得知不能直接插入一个黑色节点,会造成黑色节点个数多一,所以插入操作我们都是插入的红色节点,插入后有问题再进行变色或者旋转

    插入红色节点有这几种情况:

    (1).父亲是黑色节点,直接插入,不会破坏红黑树

    (2).父亲是红色节点氛围三种情况:

    1).父红叔红

    插入节点8时,父亲节点15和叔叔节点35都是红色的,处理方法:

    (01) 将父节点设为黑色。 红变黑只需要关心黑色节点的数量问题
    (02) 将叔叔节点设为黑色。
    (03) 将祖父节点设为红色。祖父节点开始肯定是黑色,因为父亲节点是红色
    (04) 将祖父节点设为红色,再看祖父节点的父节点是不是红色,如果是需要把祖父节点看作刚插入的节点继续处理。

    为什么这样处理:  先声明问题是插入的节点和父节点都是红色,处理方式就是变色,可能有的同学会问那为什么不是旋转呢?其实旋转也是为了变色,如果不能直接通过变色维持红黑树的时候,才需要通过旋转后再变色来维持这棵红黑树

    那变色如何变呢?

    首先肯定是把父亲节点变黑色,这样就不违背性质4,但是带来一个问题,只要包含父亲节点的路径上黑色节点数量都增加了1(最多两条最多有两个孩子),为了解决这个问题我们把祖父节点变成红色,这样包含祖父节点的路径黑色节点数量都减少了1,包含祖父节点的也是最多两条路径分别是父亲、叔叔这两条,父亲这条路径上黑色节点数量相当于没有变化(抵消了),但是叔叔这条路径减少了1,那只能把叔叔节点变成黑色来抵消黑色节点数量少1。

    变色完成后如图:

    变化完后,需要再把祖父节点当作新插入的节点再去判断红黑树是否平衡,因为如果祖父的父亲节点也是红色就违背了性质4,上图经过变换后祖父节点25违背了性质4,需要继续:

    2). 父红叔不红,插入的子节点和父节点在同一边

    把变换后的祖父节点25当作新插入节点,父节点50是红色,叔叔节点150是黑色节点。

    这时仅仅变换颜色是不能达到平衡的,这种情形需要经过一次旋转,然后变色可以达到把多的红色分到另一边的目的,因为另一边是黑色,加一个红色节点不会破坏性质

    为什么会想到这么做?上面我们提到解决这个问题的本质就是变色,旋转也是为了更好的变色,变色肯定变的是插入节点的父节点,按照我们的方式1上图中的父亲节点50变为黑色,祖父节点100变成红色,这样叔叔节点那一路径会少一个黑色节点,方式1中叔叔节点是红色的我们直接变黑就维护了红黑树,但是这次叔叔是黑的咋办?变换颜色后的场景不平衡点在于叔叔这一方的路径会比父亲这一方的路径黑色节点少一,根本原因父节点变黑了,叔叔节点没变,我们以父节点50(现在是黑色)为轴旋转一下,这样使得叔叔这条路径的黑色节点加1,原父亲路径上的黑色节点没变,正好解决了这个问题。

    以上是我自己的理解,这样可以帮助理解为啥会旋转然后变色的。

    变化完后:

     还有一个疑问75节点这颗子树,100节点变成红色后,直接把75节点变成100的孩子不会造成红黑树的不平衡吗,主要是性质5黑色节点的个数。

    不会首先我们要明白,不平衡的关键在于50节点变成了黑色,父亲这一路径多了这个50的黑节点,75这颗子树在小范围内,是和其它不包含50这个节点的路径的黑色节点的数量一致例如以25为节点的子树、150为节点的子树,所以在100节点变成红色后,直接把75节点变成100的孩子不会造成红黑树的不平衡。

    3). 父红叔不红,插入的子节点和父节点不在同一边

    75节点当作新插入的节点,和父亲节点50都是红色违背了性质4。

    这种情况思路是把这边多余红色分到另一边去,再同一边时可旋转改变,所以需要把插入子节点旋转到和父亲节点在同一边

    我还用自己理解的那一套,先变色,把父亲50节点变成黑色,祖父100节点变成红色,叔叔节点是黑色,那就以50节点为轴旋转,发现转不了,学过AVL树我们就知道类似LR旋转,需要把插入子节点旋转到和父亲节点在同一边然后再LL旋转,这个是一样的道理。

    如图:

    先把插入子节点75旋转到和父亲节50点在同一边 

     然后在按照方式2的方式最终变成:

     以上就是红黑树插入的所有情况,可以看到最多就旋转两次。

     4.红黑树删除

    (1).无子节点时,删除节点可能为红色或黑色

    1).如果为红色,直接删除即可,不会破坏红黑树的性质

    2).如果为黑色,则需要进行删除平衡的操作(后面详细分析)

    (2).如果只有一个子节点时,我们要删除的这个节点一定是黑色节点,它的那个子节点一定是红色的。 为什么这么说?

    假设我们要删除的这个节点是红色节点,那他的那个子节点一定是黑色的(性质4)如图:

     如上图,A的左孩子只有一个null黑节点,而右子树至少有两个黑节点一个是B另一个是null,也就是说A的右子树永远至少比左子树多一个黑节点,违背了性质5,其实我发现主要是B这个节点必须是红色的,因为只要B是黑色的就一定会造成A的左边的黑色节点永远至少比右边少一,所以B必须是红色的,如果B是红色的那A必须是黑色的(性质4),所以红黑树中只有一个子节点的一定是黑色,而那个子节点一定是红色。

    我们接着说只有一个子节点时怎么处理:只有一个子节点时,要删除的节点一定是黑色,它的子节点一定是红色,此时我们用这个子节点直接替换父节点,并且将子节点颜色涂黑,保证黑色数量。

    父节点是黑色的,删除后,子节点直接提上去,染成黑色,这样既不会使黑色节点的个树发生变化,更不可能违背性质4。

    (3).如果有两个子节点,用要删除节点的前驱或者后继节点代替它,这样就转变成删除它的前驱或者后继节点,而因为前驱或者后继节点的特性,前驱和后继节点一定不会有两个子节点,问题被转换为了有一个子节点或没有子节点也就是上面的两种情况。

    (4).无子节点时,删除节点可能为红色或黑色,如果为黑色,则需要进行删除平衡的操作详细分析:

    注意我们后面讨论的删除黑色叶子结点均为非null叶子结点

    删除黑色的叶子结点,会直接破坏性质5,我们要根据不同的情况,通过旋转和染色来维持红黑树

    先看流程图:

    1).如果是根结点,删除了就变为了一颗空树,啥也不用干。

    2).如果不是根结点,那要删除的这个黑色叶子结点一定有兄弟节点(如果没有兄弟节点那它总比兄弟那条路径多一个黑色节点违背了性质5)。

    下面就要围绕兄弟节点的情况来处理:

    2.1).兄弟节点为黑色

    2.1.1).兄弟节点为黑色,兄弟节点的子节点都是黑色

    2.1.1.1).兄弟节点为黑色,兄弟节点的子节点都是黑色,父亲节点是红色

    把兄弟节点染成红色,因为兄弟节点的子节点都是黑色,兄弟节点染成红色后不会违背性质4,但是违背了性质5,和被删除黑色叶子结点一样,兄弟节点这边少了一个黑色节点,,把父亲节点染成黑色,这样两兄弟路径上的黑色节点都加1如图:

    2.1.1.2).兄弟节点为黑色,兄弟节点的子节点都是黑色,父亲节点是黑色

    把兄弟节点染红,和上面2.1.1.1不同的是父节点本来就是黑色的,这样兄弟和被删除节点这两条路径都会少一个黑色节点,需要自平衡,进行递归处理。

    2.1.2) .兄弟节点为黑色,兄弟节点的子节点不全为黑色

    2.1.2.1) .兄弟节点为黑色,兄弟节点在左边,兄弟的左孩子是红的。

    父亲节点的颜色不用关心,兄弟的右孩子颜色也不用关心,不关心的用白色表示。

    先明确目的删除C后,少一个黑色节点,想办法让兄弟节点给匀一个过来,还得保证排序树的特性,交换父节点和兄弟节点的颜色,然后把父节点旋转到删除节点这一边,这么做的效果就是删除节点这一边补齐了一个黑色节点,兄弟节点那一边少了一个黑色节点,兄弟节点的子节点正好是红色的,直接把这个兄弟节点的红色子节点染成黑色这样就维持了红黑树的平衡

    2.1.2.2).兄弟节点为黑色,兄弟节点在右边,兄弟的右孩子是红的

    和2.1.2.1是对称的:

     2.1.2.3)兄弟节点为黑色,兄弟节点在左边,兄弟的左子节点是黑的

    兄弟的右子节点一定是红的,因为我们的前提是兄弟节点的子节点不是全黑。不能像前面2.1.2.1那样做,因为兄弟节点在左边,兄弟的右子节点E是红色,如果向右旋转的话,红色的节点就会跑到右边。我们考虑变成2.1.2.1那种情况即红色节点在兄弟节点的左边,因为要保证二叉排序树的特性,我们只能通过旋转来完成,单纯的以B为支点向左旋转,红色节点E变成了C的兄弟节点,这不是我们想要的,我们要红色节点是C的兄弟的左孩子,所以先交换兄弟节点B和兄弟节点的右孩子的颜色,再旋转正好能达到我们的目的,同时也没有破坏红黑树的性质。之后就可以按照2.1.2.1那种情况去处理了

    2.1.2.4)兄弟节点为黑色,兄弟节点在右边,兄弟的右子节点是黑的

    和2.1.2.3是对称的:

    2.2)兄弟节点为红色

    2.2.1)兄弟节点为红色,兄弟节点是左子节点时

    如果被删除节点的兄弟节点是红色,没法弄,就得想办法通过旋转变色把被删除节点的兄弟变成黑色

    父亲节点一定是黑色,兄弟节点一定有两个孩子而且都是黑色的(性质5),父亲节点和兄弟节点颜色互换,以父亲节点为支点右旋,之后就变成了父亲节点是红色,兄弟为黑色E,但是注意一点E节点只可以有红色的孩子,也可以没有孩子,当没有孩子的时候就是2.1.1.1那种情况,有孩子的时候分为有没有左孩子,有左孩子就是2.1.2.1,没有左孩子只有右孩子就是2.1.2.3

    2.2.1.1).旋转完后类似2.1.1.1:

    2.2.1.2).旋转完后类似2.1.2.1:

    2.2.1.3).旋转完后类似2.1.2.3:

     2.2.2)兄弟节点为红色,兄弟节点是右子节点时

    和上面2.2.1对称: 

    2.2.2.1).旋转完后类似2.1.1.1:

    2.2.2.2).旋转完后类似2.1.2.2: 

    注意下图中第一段话是错的改为:父亲节点一定是黑色,父亲节点和兄弟节点颜色互换,以父亲节点A为支点左旋,之后变成了兄弟节点E为黑色,E的右子节点为红色

     2.2.2.3).旋转完后类似2.1.2.4: 

    注意下图中第一段话是错的改为:父亲节点一定是黑色,父亲节点和兄弟节点颜色互换,以父亲节点A为支点左旋,之后变成了兄弟节点E为黑色,E的左子节点为红色,右子节点为null是黑色

     到这里删除就讲完了,可以看到,删除最多旋转三次,2.2.1.2、2.2.1.3、2.2.2.2、2.2.2.3这四种情况会旋转三次。

    展开全文
  • 最简单的Java红黑树的变色、旋转与自平衡原理。红黑树的定义性质与原理,红黑树自平衡的原子操作,权威最简单红黑树的新增操作。
  • 在满足红黑树性质的前提下,旋转的次数远小于AVL树。C++的map、set的底层数据结构就是红黑树红黑树特点: 树的每一个节点不是黑色就是红色, null是黑色 root是黑色 从根节点到每一个叶子节点的所有路径上,...
  • 红黑树的变色与旋转

    2021-03-12 16:24:10
    红黑树是自平衡的二叉查找树,所以了解红黑树之前我们需要先了解什么是二叉查找树。 二叉查找树 1.某节点的左子树节点值仅包含小于该节点的值 2.某节点的右子树节点值仅包含大于该节点的值 3.左右子树也...
  • 树是数据结构中经典的结构之一,也是面试中常问的面试题之一,最近复习了一个红黑树的知识,做一下整理 文章目录 前言 一、pandas是什么? 二、使用步骤 1.引入库 2.读入数据 总结 前言 提示:这里...
  • 什么是红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。...为什么需要红黑树红黑树的使用极大的提高了搜索效率,传统的二叉树和二
  • HashMap为什么要使用红黑树

    千次阅读 2022-02-24 22:23:39
    HashMap为什么要使用红黑树
  • 红黑树的一些基本概念 在讲TreeMap前还是先说一下红黑树的一些基本概念,这样可以更好地理解之后TreeMap的源代码。 二叉查找树是在生成的时候是非常容易失衡的,造成的最坏情况就是一边倒(即只有左子树/右子树)...
  • 我们在MySQL中的数据一般是放在磁盘中的,读取数据...那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候远远大于电子运动的时间。当大规模数据存储到磁...
  • 红黑树详解

    2017-09-02 15:45:29
    红黑树详解(带目录源码) 本文适合那些有对二叉树有一定的基础,并且熟悉C语言的读者。本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。
  • 红黑树-1 介绍与旋转

    2020-09-20 23:07:33
    红黑树是基于二叉树的一种非常重要的数据结构,它在二叉树的基础上加上了一下五点的限制,这也是红黑树的...红黑树存在左旋和右旋两种,在插入节点和删除节点的时候需要进行旋转来调整红黑树使其始终满足上面介绍的五条
  • 红黑树旋转

    2021-01-05 23:07:07
    如果对红黑树还不了解的,建议看上一篇博客。 https://blog.csdn.net/weixin_37909391/article/details/112252930 首先回顾以下红黑树的性质: 结点必须是红色或者黑色。 根节点必须是黑色。 叶节点(NIL)必须是...
  • 为什么红黑树的效率比较高

    千次阅读 2020-12-19 19:15:42
    红黑树属于平衡二叉树。它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n)。红黑树(red-black tree)是一棵满足下述性质的二叉查找树...
  • 红黑树和平衡树的旋转机制,LL,RR,LR,RL型
  • 对于红黑树在插入节点时最多经过两次旋转能达到平衡,在删除节点时最多经过三次节点能达到平衡.... 为什么在百度avl树和红黑树的区别的时候却都说红黑树对于avl树来说降低了插入和删除节点再平衡时的旋转开销呢?
  • 数据结构 红黑树的详解 红黑树是具有下列着色性质的二叉查找树: 1.每一个节点或者着红色,或者着黑色。 2.根是黑色的。 3.如果一个节点是红色的,那么它的子节点必须是黑色。 4.从一个节点到一个NULL指针的每一条...
  • 红黑树可以实现自平衡,主要依靠于它的旋转和变色的特性 //红黑树节点 typedef struct RBTreeNode { unsigned char color; Type key; struct RBTreeNode* left; struct RBTreeNode* right; struct RBTreeNode* ...
  • 为什么要红黑树想必大家对二叉树搜索树都不陌生,首先看一下二叉搜索树的定义:二叉搜索树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不...
  • 红黑树插入时的自平衡 红黑树实质上是一棵自平衡的二叉查找树,引入带颜色的节点也是为了方便在进行插入或删除操作时,如果破坏了二叉查找树的平衡性能通过一系列变换保持平衡。 红黑树的性质 每个节点要么是红色,...
  • 第1~第5步都没有什么问题,红黑树最核心的应当是第6步插入数据之后进行的修复工作,对应的Java代码是TreeMap中的fixAfterInsertion方法,下面看一下put每个数据之后TreeMap都做了什么操作,借此来理清TreeMap的实现...
  • 但是提出了节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多...
  • 下面这个blog有动图可以生动形象的描绘出红黑树左右旋转的特性,安利 红黑树左右旋转操作
  • 一、红黑树性质 结点必须是红色或者黑色。 根节点必须是黑色。...如果插入结点的父节点黑色,就不需要进行旋转变色调整,其他情况都需要根据实际选择合适的处理策略进行调整,使其符合红黑树性...
  • 红黑树旋转与变色

    千次阅读 多人点赞 2019-01-27 22:55:23
    缘起 在此之前,笔者写过一篇关于TreeMap工作原理的简单...为什么红黑树要旋转和变色 这需要从红黑树的特效说起,红黑树发明之初就定义了以下5个特性,因为这几个特性,使得红黑树成为一个相对平衡的二叉树,也就...
  • 红黑树其实是由2-3树演变来的,如果想理解红黑树,可以先看看2-3树 2-3树插入逻辑: 先找插入结点,若结点有空(即2-结点),则直接插入。如结点没空(即3-结点),则插入使其临时容纳这个元素,然后分裂此结点,把...
  • 红黑树的双旋转

    2017-06-02 23:51:43
    红黑树的双旋转
  • HashMap为什么选择红黑树

    千次阅读 2021-10-12 15:20:15
    红黑树不追求"完全平衡",即不像AVL那样要求节点的 |balFact| <= 1,它只要求部分达到平衡,但是提出了节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,227
精华内容 8,890
热门标签
关键字:

红黑树为什么要旋转