谈谈红黑树

一、背景

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

二、二叉查找树 BST

1、定义

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

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

2、优势

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

3、劣势

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

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

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

三、红黑树 Red Black Tree

1、定义

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

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

2、调整

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

3、破坏

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

4、变色

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

5、旋转

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

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

6、应用

  • TreeMap
  • TreeSet
  • HashMap(JDK8)