顶尖Java工程师的红黑技能树,如何快速点亮?

伴随着《阿里巴巴Java开发手册》影响面越来越广,影响程度越来越深,读者也越来越好奇《码出高效》背后的故事、映射的技术问题以及深层次的技术思考。

树(tree)的基本知识

姓名:罗珍    学号:17101223459

小编整理了一些java进阶学习资料和面试题,需要资料的请加JAVA高阶学习Q群:664389243
这是小编创建的java高阶学习交流群,加群一起交流学习深造。群里也有小编整理的2019年最新最全的java高阶学习资料!

一.定义

是一种抽象数据类型,或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合

图片 1

树.png

本文转自

《码出高效》源于影响了全球250万名开发工程师的《阿里巴巴Java开发手册》,涵盖计算机领域基础知识、面向对象理念、JVM核心解析、数据结构与集合、高并发多线程、异常和日志、单元测试以及如何编写可读性强、可维护性好的优雅代码等多个方面,讲解由浅入深。

二.特点

  • 每个节点有零个或多个子节点;
  • 没有父节点的节点称为根节点;
  • 每一个非根节点有且只有一个父节点;
  • 除了根节点外,每个子节点可以分为多个不相交的子树

【嵌牛导读】:红黑树是一种自平衡二叉查找树,典型的用途是实现关联数组,它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的O(logn)时间内做查找,插入和删除,这里的n是树中元素的数目。

这是走向Java高手的必经之路,但是由于数据结构相对晦涩难懂,集合类的坑比较多,有时连资深Java工程师都会失手,给工程项目带来无法预估的损失。

三.存储结构

  1. 线性存储
    /* 树节点的定义 /
    #define MAX_TREE_SIZE 100
    typedef struct
    {
    TElemType data;
    int parent; /
    父节点位置域 /
    } PTNode;
    typedef struct
    {
    PTNode nodes[MAX_TREE_SIZE];
    int n; /
    节点数 */
    } PTree;

图片 2

树-线性存储.jpg

  1. 链式存储

     /*树的孩子链表存储表示*/
     typedef struct CTNode  // 孩子节点
     { 
         int child; 
         struct CTNode *next;
      } *ChildPtr;
      typedef struct
      {
         ElemType data; // 节点的数据元素 
         ChildPtr firstchild; // 孩子链表头指针
       } CTBox;
       typedef struct 
       {
          CTBox nodes[MAX_TREE_SIZE]; 
          int n, r; // 节点数和根节点的位置
        } CTree;
    

图片 3

树-链式存储.jpg

【嵌牛鼻子】:红黑树 关联数组

除了高手进阶秘籍以外,我们还将分享《码出高效》写作背后的小故事,聊聊Java学习心得。同时,阿里妹还准备了多本作者签名版的图书,送给参与直播的小伙伴们。

红黑树(Red-black tree)的基本知识

【嵌牛提问】:什么是红黑树?是如何实现的?

图片 4

一.定义

红黑树是一种自平衡二叉查找树,典型的用途是实现关联数组,它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的O(log
n)
时间内做查找,插入和删除,这里的n是树中元素的数目。

图片 5

红黑树.png

NIL节点表示数据的结束,在wiki百科中其被当做叶子节点,画图时应该也体现出来。

【嵌牛正文】:

为什么集合与数据结构这么重要?

二.特点

  1. 任意节点的左子树不空,则左子树上所有节点的值均小于它的根结点的值;
  2. 任意节点的右子树不空,则右子树上所有节点的值均大于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点;
  5. 节点是红色或黑色;
  6. 根是黑色, 所有叶子都是黑色;
  7. 每个红色节点必须有两个黑色的子节点;(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  8. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点;

通过节点颜色,限制了二叉树的高度。
操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

图片 5

我们经常说,“程序=数据结构+算法”。假如程序是一道美味佳肴的话,那么数据结构就是食材,食材的选择对于菜的品质是至关重要的,烂菜叶、霉土豆是不可能做出极品菜肴的。

三.抛出问题

  • O(log
    n)
    的操作效率是如何得出的?为什么与高度成比例,而不是与节点数成比例?

一个由n个节点随机构成的二叉查找树的高度为(log n ).证明如下:

图片 7

红黑树高度证明.jpg

而时间复杂度是以某个基础数据操作的重复次数作为量度。红黑树的是二叉搜索树,左子树上所有节点的值均小于他的根节点的值,右子树上所有节点均大于根节点的值,左右子节树相对根节点按大小分布。如果把每次节点值的比较看成基础数据操作,那么最差的查找情况是一直查找到高度最大的根节点,那么查找的时间复杂度即与高度成正比,可表示成O(log
n)

红黑树有哪些特点呢?

我们在编码时,如果数据结构存在严重的设计缺陷,在代码层面去修正,花费的代价是极大的,甚至是不可能的。底层数据结构的缺陷也是重构的第一诱因,无端地浪费宝贵的人力资源。集合作为数据结构的载体,对元素进行加工和输出,以一定的算法实现最基本的增删改查功能,它是数据结构与算法的中间纽带,因此集合是所有编程语言的基础,非常重要。在进入高并发编程时代后,由集合引发的相关故障占比越来越高。比如,多线程共享集合时出现的脏数据问题;HashMap在数据扩容时出现节点之间的死链问题;写多读少的场景误用某些集合导致性能下降问题等。

如何生成红黑树

简单了解了红黑树的字面定义,下面动手感受下红黑树的相关操作。当你插入或者删除一个节点时,可能会破坏红黑树的性质,所以需要对树节点进行重新着色或者旋转,来保持红黑树的结构。首先看下二叉树的旋转。

     
任意节点的左子树不空,则左子树上所有节点的值均小于它的根结点的值;任意节点的右子树不空,则右子树上所有节点的值均大于它的根结点的值;任意节点的左、右子树也分别为二叉查找树;没有键值相等的节点;节点是红色或黑色;根是黑色,
所有叶子都是黑色;每个红色节点必须有两个黑色的子节点;(从每个叶子到根的所有路径上不能有两个连续的红色节点。)从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点;通过节点颜色,限制了二叉树的高度。操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

红黑树是一种熟悉而陌生的数据结构,熟悉是指“别人家的开发工程师”运用在JDK源码或各种算法中,陌生指的是理解红黑树的理论基础比较多,比较生涩而难懂。在了解红黑树之前,我们先聊聊数据结构到底是什么?

一.旋转

  • 左旋

图片 8

树左旋.jpg

假设pivot节点不为空,其右子树不为空,那么左旋即是:使pivot的右孩子Y为子树的根,pivot节点为子树根节点的左孩子,pivot左孩子、Y节点的右孩子不改变,Y节点左孩子变为pivot节点右孩子。

  • 右旋

图片 9

树右旋.jpg

假设pivot节点不为空,其左子树不为空,那么右旋:使pivot的左孩子Y为子树的根,pivot节点为子树根节点的右孩子,pivot的右孩子、Y节点的左孩子不变,Y节点的右孩子变为pivot节点的左孩子。

任意节点的左子树不空,则左子树上所有节点的值均小于它的根结点的值
任意节点的右子树不空,则右子树上所有节点的值均大于它的根结点的值

实战演练之增加、删除节点时,如何保证红黑树的性质不被破坏。

O(logn)的操作效率是如何得出的?为什么与高度成比例,而不是与节点数成比例?

图片 10

二.增加节点

往一个空的红黑树中,依次插入数据:12 1 9 2 0 11 7 19 4

  • 插入12

图片 11

+12.jpg

节点为根节点,所以为黑色,两个null节点为黑色节点。

  • 插入 1

图片 12

+1.jpg

1小于12,所以是根节点的左孩子,如果为黑色,那么违反性质:从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。所以新增节点为红色。

  • 插入 9

图片 13

+9.jpg

按照二叉搜索树的逻辑,9小于12、大于1,应该是1节点的右孩子。但,新增的两个NIL节点已经使得12,1,9,NI这条路径的黑色节点至少为两个,而12,NIL这条路径的黑色节点只有两个。所以要对1节点进行左旋,9节点变为12节点的左孩子,发现问题还是存在。继续,对12节点进行右旋,9节点为根节点,1、12分别为9节点的左右孩子。尝试着色,9节点必须为黑色,而1,12节点可以为红色,也可以为黑色。

  • 插入 2

图片 14

+2.jpg

2大于1,直接作为1的右孩子即可。2的增加必然会增加两个黑色NIL节点,所以每条路径至少有三个黑色节点。则9,12,NIL这条路径中,12节点应该变为黑色;9,1,NIL这条路径中,1应该变为黑色。9,1,2,NIL这条路径中,2为空色来使得黑色节点个数为三个。验证一下,满足从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。则颜色调整完毕。

  • 插入 0

图片 15

+0.jpg

0节点直接作为1节点的左孩子,保持跟2节点相同的颜色即可。左右子树依旧保持平衡。

  • 插入 11
![](https://upload-images.jianshu.io/upload_images/1638963-383258be7fd86254.jpg)

+11.jpg



11节点作为12节点的左子树,颜色跟同一层的0,2节点保持一致即可。
  • 插入 7

图片 16

+7.jpg

从二叉查找树的性质看,7节点作为2节点的右孩子即可。这时来分析着色问题,我们先看最短路径的黑色分布,9,12,NIL这条路径,有三个黑色节点,以此为参考,尝试改变9节点左子树的着色。目前最长的路径是9,1,2,7,NIL这条路径。保持三个黑色节点的话,9跟NIL已经为黑色节点,而红色节点又不能挨着,所以只能是1为红色节点,2为黑色节点,7为红色节点。那么9,1,0,NIIL这条路径,0就要为黑色节点。调整完毕。

  • 插入 19

图片 17

+19.jpg

19节点作为12节点的右孩子,与左孩子保持一样的红色即可。

  • 插入 4

图片 18

+4.jpg

4节点应该作为7节点的左子树,无论着什么颜色,以1节点为根节点的子树,都要破坏红黑性质。所以应该进行旋转。先以7为根节点进行一次右旋,再以2为根节点进行一次左旋。尝试着色即可。

思维误区:之前我把左右字数高度相差不能超过1加入到红黑树的性质中,这导致我的推理逻辑发生了错误。因为红黑树是用红黑着色来保证高度,我直接用使用结果来推导红黑着色,这样会忽略红黑树本身的优点,而只关注了平衡二叉树的优点。错误思维路线:我先优先保持二叉搜索树的性质,然后通过旋转使其保持平衡,然后再进行颜色调整。感觉只是在探讨平衡二叉搜索树的性质,红黑性质被弱化了,仅仅是为了构造一个红黑树而调整着色。思维调整:先从二叉搜索树的角度对节点进行插入,然后从着色的角度对树进行旋转。

一个由n个节点随机构成的二叉查找树的高度为(logn).证明如下:

数据结构是什么?

插入节点的五种情况:
  1. 新节点N位于树的根上,没有父节点。
  2. 新节点的父节点P是黑色情形。
  3. 父节点P、叔叔节点U,都为红色。
  4. 父节点P是红色,叔叔节点U是黑色或NIL;
    插入节点N是其父节点P的右孩子,而父节点P又是其父节点的左孩子。
  5. 父节点P是红色,而叔父节点U 是黑色或NIL,要插入的节点N
    是其父节点的左孩子,而父节点P又是其父G的左孩子。

这里,先不补充每种情况的操作方法,你是不是能自己动手写下呢?欢迎留言~

图片 7

数据结构是指逻辑意义上的数据组织方式及其相应的处理方式。

三.删除节点

类似插入节点的分析、总结,删除节点也可以针对每种场景找到固定的着色方法,就像玩一个游戏,有自己的推理跟玩法。我先做个PPT,这块稍后补充。

红黑树高度证明.jpg

1、什么是逻辑意义?
数据结构的抽象表达非常丰富,而实际物理存储的方式相对单一。比如,二叉树在磁盘中的存储真的是树形排列吗?并非如此。

使用场景

所有的插入、删除都是有限个情况,基于插入、删除的情况分析,即可编写算法生成红黑树,使其在固定的业务场景中发挥红黑树稳定操作效率的特色了。

  • 实现关联数组
    关联数组又称映射Map)、字典Dictionary)是一个抽象的数据结构,它包含着类似于(键,值)的有序对。C++的STL中。map和set都是用红黑树实现的。
    底层采用红黑树保存
    key-value对,Key值唯一。添加、取出都需要一些循环操作,但所有键值对都是按照key根据指定排序规则保持有序状态。
  • 著名的linux进程调度Completely Fair
    Scheduler
    CFS用红黑树管理进程控制块
    每个进程都包含运行时间,通过考虑优先级、系统负载等计算出的加权时间,作为红黑树的key。下一个执行的进程为最小运行时间的进程,对应红黑树的最左叶子。
  • epoll在内核中的实现,用红黑树管理事件块
    linux内核的可扩展I/O事件通知机制,应用于高性能网络程序场景,在内核cache中用红黑树储存事件块,保证较快的查询速度。
  • nginx中,用红黑树进行超时管理
    Nginx为网页服务器,在进行超时管理时,通过红黑树存储超时时间对象,每次找到key最小的节点,然后进行判断是否超时,超时就处理,直到取出的未超时的事件。
  • Java的TreeMap实现
    TreeMap是Java中key-value的集合,根据key值的自然顺序进行排序,或者依据比较函数。

而时间复杂度是以某个基础数据操作的重复次数作为量度。红黑树的是二叉搜索树,左子树上所有节点的值均小于他的根节点的值,右子树上所有节点均大于根节点的值,左右子节树相对根节点按大小分布。如果把每次节点值的比较看成基础数据操作,那么最差的查找情况是一直查找到高度最大的根节点,那么查找的时间复杂度即与高度成正比,可表示成O(logn)

2、什么是数据组织方式?逻辑意义上的组织方式有很多,比如树、图、队列、哈希等。树可以是二叉树、三叉树、B+
树等;图可以是有向图或无向图;队列是先进先出的线性结构;哈希是根据某种算法直接定位的数据组织方式。

二叉搜索树之间的对比

如何生成红黑树?

3、什么是数据处理方式?
简单地说就是增删改查。即在既定的数据组织方式上,以某种特定的算法实现数据的增加、删除、修改、查找和遍历。不同的数据处理方式往往存在着非常大的性能差异。

一.AVL树

在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log
n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或
-1的节点被认为是平衡的。带有平衡因子
-2或2的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。

图片 20

AVL旋转.png

红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。

简单了解了红黑树的字面定义,下面动手感受下红黑树的相关操作。当你插入或者删除一个节点时,可能会破坏红黑树的性质,所以需要对树节点进行重新着色或者旋转,来保持红黑树的结构。首先看下二叉树的旋转。

数据结构的评判

未完待续

不提问题的码农不是好程序员。自己写完了红黑树的简单剖析,感觉还是只懂皮毛,没有从触碰到算法的核心内容。所以,不妨留几个小问题,担心自己脑子生锈或者没事想玩手机的时候,再提笔研究下红黑树。

  • 举例说明红黑树如何牺牲部分平衡性来保证尽可能少的旋转操作,通过与AVL树做比较。增加节点的时候,如果是在构建AVL树,结果会怎么样。

一.旋转

那么经常有开发同学说,我的输入规模量级非常小,远没有需要考虑到数据结构时间复杂度的地步,但是,除了问题规模之外,还有一个因素需要考虑,就是调用频率,即使这个方法的算法复杂度只是快了20纳秒,在日均上亿次的调用情况下,也可能是节约了若干台服务器。

参考

教你初步了解红黑树
算法的时间复杂度和空间复杂度-总结
红黑树从头至尾插入和删除
AVL树
红黑树C源码实现与剖析

Echo
8 Nov,2016

左旋

数据结构的各种类型没有好坏之分,它只有与场景、数据量结合起来综合考虑,才有实际的意义。场景包括操作类型使用频率,数据量的大小决定它选择什么样的数据结构类型。到底是写为主,还是读为主,或者说读写均衡。其中写是以插入为主,还是删除为主;读是以遍历为主,还是查询单个元素为主。数据量的不同也会决定不同数据结构的使用效率。所以单纯地说红黑树与AVL是哪个好,哪个坏,是不对的。

图片 8

红黑树

树左旋.jpg

AVL树与红黑树之间没有从属关系,他们都是二叉查找树。AVL
树算法是以苏联数学家Adelson-Velsky
和Landis名字命名的平衡二叉树算法。红黑树是于1972
年发明的,当时称为对称二叉B 树,1978
年得到优化,正式命名为红黑树。面对频繁的插入和删除,红黑树更为合适;面对低频修改、大量查询时,AVL
树将更为合适。

假设pivot节点不为空,其右子树不为空,那么左旋即是:使pivot的右孩子Y为子树的根,pivot节点为子树根节点的左孩子,pivot左孩子、Y节点的右孩子不改变,Y节点左孩子变为pivot节点右孩子。

我们重点来说说红黑树,它广泛应用在JDK11的各种集合框架内,比如:HashMap,TreeMap等。它在二叉查找树的性质基础上,额外引入了5
个约束条件:

右旋

节点只能是红色或黑色

图片 9

根节点必须是黑色

树右旋.jpg

所有NIL 节点都是黑色的

假设pivot节点不为空,其左子树不为空,那么右旋:使pivot的左孩子Y为子树的根,pivot节点为子树根节点的右孩子,pivot的右孩子、Y节点的左孩子不变,Y节点的右孩子变为pivot节点的左孩子。

一条路径上不能出现相邻的两个红色节点

任意节点的左子树不空,则左子树上所有节点的值均小于它的根结点的值

在任何递归子树内,根节点到叶子节点的所有路径上包含相同数目的黑色节点

任意节点的右子树不空,则右子树上所有节点的值均大于它的根结点的值

扩展说明一下NIL释义,它可以形象理解为Nothing In
Leaf,是红黑树中特殊的存在,即在叶子节点上不存在的两个虚拟节点,它是红黑树旋转的假设性理论基础,默认为黑色的。

实战演练之增加、删除节点时,如何保证红黑树的性质不被破坏。

总结一下,即“有红必有黑,红红不相连”,上述5
个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为O
。如果一个树的左子节点或右子节点不存在,则均认定为黑色。红黑树的任何旋转在3
次之内均可完成。我们以实际插入节点55,56,57来看看红黑树的插入,以达到抛砖引玉的效果。

二.增加节点

图片 23

往一个空的红黑树中,依次插入数据:12 1 9 2 0 11 7 19 4

当插入57 时,由于父节点56
是红色的,出现两个连续红色节点,违反红黑树特性,需要重新着色,根据算法56这个节点是变为黑色,而根节点变为红色,这个时候并不平衡并且根节点为红色,这两条违反红黑树特性。所以必须左旋操作,结果如最右端所示。如果需要重新着色或旋转,存在三种情形总结如下:

插入12

节点的父亲是红色,叔叔是红色的,则重新着色。

图片 11

节点的父亲是红色,叔叔是黑色的,而新节点是父亲的左节点:进行右旋。

+12.jpg

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website