谈谈红黑树

本贴最后更新于 2134 天前,其中的信息可能已经物是人非

一、背景

    不管是在阅读 jdk 源码的过程中,还是数据结构的课程学习过程中,亦或是在程序员的面试过程中,红黑树问题都是十分常见的考察数据结构功底的一个典型问题,因此决定一探究竟!

二、二叉查找树 BST

1、定义

  • 左子树上所有结点的值均小于等于它的根结点的值
  • 右子树上所有结点的值均大于等于它的根结点的值
  • 左右子树也分别为二叉排序树

    通俗地理解,所谓的二叉查找树,就是“左边小于等于根,右边大于等于根”这样一种树构造逻辑不断递归出来的一种树结构

imagepng

2、优势

  • 在查找时,则刚好是一种对二分查找思想的应用;查找所需的最大次数等同于二叉查找树的高度
  • 插入结点时,也是类似于查找时的二分查找思想,通过一层层比较大小,最终找到新节点适合插入的位置

3、劣势

  • 但是,主要是在插入新节点的时候:假设是按照待插入的序列本身是有序的如“9,8,7,6,5”且根结点值为 10,那么该二叉查找树就会变成左子树大幅不断延长,几乎就是变成了线性的了

  • 即,二叉查找树,随着多次插入新节点而出现了不平衡

  • ==>> 重点来了,,,然后就是身为主角的“红黑树”上场了;理所当然,红黑树就是一种自平衡的二叉查找树

三、红黑树 Red Black Tree

1、定义

  • 首先红黑树是一个二叉查找树,也即满足二叉查找树的定义为前提条件,扩展的定义是为了保证其具有自平衡特性的
  • 节点是红色或黑色
  • 根节点是黑色
  • 每个叶子节点都是黑色的空节点,即 NIL 节点
  • 每个红色节点的两个子节点都是黑色(也即,从每个叶子到根的所有路径上不能有两个连续的红色节点,注意噢“没说黑色节点哈,因此可以出现两个连续的黑色节点”)
  • 从任一节点到其每个叶子的所有路径均包含着相同数目的黑色节点

imagepng

=> 也正是,上述的定义规则保证了红黑树可以具有自平衡的特性:在红黑树中,根结点到叶子结点的最大路径长度不会超过最短路径长度的 2 倍

2、调整

    但是,在一般插入或删除节点的时候,红黑树可能会被打乱,导致其不符合其定义中的规则,因此需要做一些调整(变色和旋转【左旋转、右旋转】),以继续保证其仍然符合红黑树的定义规则

3、破坏

    什么情况下会破坏红黑树的定义规则?什么情况下不会破坏红黑树的定义规则?

4、变色

    也即,试图通过将红色节点变成黑色,或者将黑色节点变成红色,使得其重新满足红黑树的定义条件,这样的一种手段称之为变色

5、旋转

  • 左旋转:逆时针旋转红黑树的两个节点,使得父节点被自己的右孩子取代,而自己成为自己的左孩子
  • 右旋转:顺时针旋转红黑树的两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子

=> 注意:红黑树的插入和删除,有很多种情况,每一种情况可能都会需要不同的处理方式(详细多种情形,可自行先维基百科中学习!后续再完善添加)

6、应用

  • TreeMap
  • TreeSet
  • HashMap(JDK8)
  • 学习

    “梦想从学习开始,事业从实践起步” —— 习近平

    169 引用 • 506 回帖
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    325 引用 • 1395 回帖
  • 数据结构
    88 引用 • 115 回帖 • 4 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...