前言

友情建议 文章非常长,建议加入喜欢或收藏分多次看

推荐一个很好用的数据结构模拟的网站,动画模拟 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
进去之后选择红黑树

select

动画模拟

目录

1. 树的简介

2. 为什么会有红黑树?

3. 红黑树的5大性质

4. 左旋和右旋

5. 红黑树的插入

6. 红黑树的遍历

7. 红黑树的删除

1. 树的简介

计算机科学中的树
在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点都只有有限个子节点或无子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；
• 树里面没有环路(cycle)

一棵树

为什么需要树
为什么要用到树呢？因为它通常结合了另外两种数据结构的优点： 一种是有序数组，另一种是链表。在树中查找数据项的速度和在有序数组中查找一样快， 并且插入数据项和删除数据项的速度也和链表一样。下面，我们先来稍微思考一下这些话题，然后 再深入地研究树的细节。

2. 为什么会有红黑树?

树的种类

树的种类有很多种,二叉树,AVL树,霍夫曼树,B树....,我们应用最多的是二叉树,但是二叉树有一种极端的情况会退化为链表 如图:

退化的树

所以,虽然树结构很高效,但是一旦退化效率就变低了,所以我们应该有一种自平衡的树,能够保证树的平衡,不至于像图上一样失衡,所以就有了平衡二叉树,常见的有AVL树,红黑树等

相比于红黑树,AVL树是这样规定的,任意一个节点,它的左右子树的高度差至多为1,所以当插入数据和删除数据之后,会调整数的结构而保持数的平衡,虽然AVL数能够很完美的保证树的平衡,但是要求有一些严格,这样就会导致我们插入数据一直会不停地调整,也会影响效率.

所以红黑树就诞生了,红黑树不是完美的平衡二叉树,因为它允许有一点不平衡,但是不会差别很大,所以不会影响查询的效率,但是插入和删除的调整又减少了,所以红黑树是一种简单而高效的数据结构.

3. 红黑树的5大性质

1. 树的节点要么是黑色要么是红色
2. 根节点为黑色
3. NIL节点为黑色(NIL节点就是叶子节点的next 空节点,如下图)
4. 红色节点的子节点为黑色
5. 任意节点到NIL节点的路径上有相同数目的黑色节点

其实还有一点,插入的节点为红色,至于为什么为红色,很简单,因为插入黑色会影响性质5(影响就要调整), 插入红色可以尽量减少不必要的调整

红黑树就是依靠这5个性质来保证树的平衡,上面也有提到,红黑树不是完美的平衡二叉树,其实从性质5也可以看出,红黑树其实可以算是黑色节点平衡的二叉树
至于为什么满足这5个性质就可以平衡,其实是 Leo J. Guibas 和 Robert Sedgewick 这两位大师研究了几年的成果,我们直接拿来用就可以了,只要保证5个性质就可以平衡,如果感兴趣可以搜下这两位的论文或者其他文献看下原理

NIL节点

4. 左旋和右旋

这里我们先介绍下左旋和右旋

• 左旋:

1. R的右子节点(T)上去变为R的父节点
2. 右子节点(T)的左子树变为R的右子树

左旋

• 右旋:

1. R的左子节点(B)上去变为R的父节点

2. 左子节点(B)的右子树变为R的左子树

   
   
   右旋

5. 红黑树的插入

其实要弄清楚红黑树的插入,那就可以按以下场景去区分,插入的情况就这么多
首先我们先来约定一下命名,如图:

子树

这是任意一颗子树,一定要记住以下定义:

• I 为要插入的节点
• P为要插入节点的父节点
• PP为要插入节点的爷爷节点
• U为要插入节点的叔叔节点
• 当前节点: 要操作的节点

那我们开始讲插入的场景

场景一: 要插入的树为空

那我们直接将节点插入即可,因为新插入节点为红色,根据性质2根为黑色,我们将新节点变为黑色

场景二: 插入节点的key已经存在

这种场景也很简单,找到我们要插入的key,将value替换即可

场景三: 插入节点的父节点为黑色

我们来看下这种情况,如图:

情景三

32要插入的地方应该是30的右子节点,我们可以发现其实插入一个红色节点不会影响性质5 (任意节点到NIL节点的路径上有相同数目的黑色节点),因为没有改变新增黑色节点,当然也不会影响性质4(红色节点的子节点为黑色)

所以插入后为:

情景三插入后

所以这种情况也不需要做调整

场景四: 插入节点的父节点为红色

也就是这种情况,因为要插入的父节点为红色,也就是P为红色,根据红黑树的性质推断出P肯定会有一个黑色的父亲,也就是PP

场景四

根据这种场景我们又可以细分为几种子情况:

场景 4.1 有叔叔节点,且为红色

也就是这种情况:

4.1

操作步骤:

• 1. 将P和U变黑
• 2. 将PP变红
• 3. 将PP做为当前节点做后续的处理

处理后为:

4.1处理后

注意: 作为当前节点做后续处理的意思是,因为这只是个子树,子树的调整有可能会影响别的节点,所以有可能还会做其他的操作比如旋转,那当前节点就是后续要操作的节点

场景 4.2 叔叔节点不存在或为黑色

也就是这种情况:

4.2

其实4.2还可以细分, P是PP的左子节点还是右子节点,也就是如下两种情况:

image.png

4.2.1 P为PP的左子节点

也就是上图中右边的情况

其实可以看出I既可以是P的左子节点,又可以是右子节点,所以分别对两种情况操作即可

• I是P的左子节点 --- 也就是 LL双红
  如下图:
  
  LL双红

操作步骤:

• 1. 将P变黑,PP变红
• 2. 对PP节点右旋

LL双红的处理步骤

• I是P的右子节点 --- 也就是 LR

如下图:

LR双红

• 1. 对P左旋
• 2. 然后以P为当前节点,变为LL
• 3. 然后处理LL

LR双红的处理步骤

4.2.2 P为PP的右子节点

image.png

也就是上图中左边的情况

• I是P的左子节点 --- 也就是 RL

如下图 :

RL双红

操作步骤:

• 1. 对P节点右旋
• 2. 将P作为当前节点,变为RR
• 3. 处理RR

RR双红的处理步骤

• I是P的右子节点 --- 也就是 RR

如下图:

RR双红

操作步骤:

• 1. 将P变黑,PP变红
• 2. 对PP节点左旋

RR双红处理步骤

总结一下插入:

不需要调整的:

• 1. 空树的插入
• 2. 节点已存在
• 3. 插入的父节点为黑色

需要调整的:

• 1. 插入的父节点为红色
  • 1.1 叔叔节点存在且为红色
  • 1.2 叔叔节点不存在或为黑色

    • 1.2.1 P为PP的左子节点

      • 1.2.1.1 LL
      • 1.2.1.1 LR

    • 1.2.2 P为PP的右子节点

      • 1.2.2.1 RR
      • 1.2.2.1 RL

6. 红黑树的遍历

红黑树的遍历和二叉树的遍历一样,分为前序遍历,中序遍历,后续遍历
具体可以看这个文章: 二叉树的四种遍历方式 里面又加了一种层序的遍历,一般为三种遍历方式

7. 红黑树的删除

具体可以详见美团的红黑树技术文章的删除的case: 红黑树深入剖析及Java实现

参考:

1. JDK1.8 源码。
2. 知乎 : Java数据结构:树（Tree）
3. 维基百科 - 红黑树
4. 美团技术: 红黑树深入剖析及Java实现

如有错误,请评论指正,万分感谢!