Java 集合框架 - 红黑树前置知识

1.概述

**数据结构的基石，我认为只有2个：数组和链表。几乎所有的数据结构都可以通过二者演变出来 **

数据结构 [Data Structure] 有哪些树？

• 二叉树

• 二叉查找树

• 平衡二叉树

• 平衡二叉树之AVL树

• 平衡二叉树之红黑树

• B树 <=> B-树

• B+树

• B*树

• Trie树

• 后缀树

  • 广义后缀树

• ........

红黑树的应用场景

• HashMap
• HashSet
• TreeMap
• TreeSet
• Linux内核
• C++的库函数
• 其他
• 也就是说，只有红黑树搞懂了Java的集合框架就都明白了，对于其他的，我已经做了比较详细的源码解析。只要有基础的数组基础和链表基础即可。

2.树结构

 ├─ 树
 │    ├─ 树结构常用语
 │    ├─ 二叉搜索树
 │    │    ├─ 查找节点
 │    │    ├─ 插入节点
 │    │    ├─ 遍历
 │    │    ├─ 查找最大值、最小值算法
 │    │    ├─ 删除节点
 │    │    │    ├─ 1.删除没有子节点的节点
 │    │    │    ├─ 2.删除有一个子节点的节点
 │    │    │    ├─ 3.删除有两个子节点的节点
 │    │    │    ├─ 4.删除有必要吗？
 │    │    ├─ 二叉搜索树的效率
 │    │    ├─ 普通二叉搜索树的致命缺陷
 │    │    ├─ AVL树简介

2.1 树

树(Tree)是一种抽象数据类型，用来模拟具有树状结构性质的数据集合，它是由n(n>0)个有限节点通过链接它们的边组成一个具有一个层次关系的集合。它叫做“树”，是因为他像是一颗倒挂的树，也就是说根朝上的，叶子向下

树有很多种，向上面的一个节点有多余的两个节点的树，称为多路树，而每个节点最多只能有2个节点的一种形式称为二叉树。

**节点：**上图的圆圈，比如8,1,13等都是表示节点。节点一般代表一些实体，在java面向对象编程中，节点一般代表对象。

边：连接节点的线称为边，边表示节点的关联关系。一般从一个节点到另一个节点的唯一方法就是沿着一条顺着有边的道路前进。在Java当中通常表示引用。

2.2 树结构常用语

路径：顺着节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。

根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。

父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

子节点：一个节点含有的子树的节点称为该节点的子节点；F、G是C节点的子节点。

兄弟节点：具有相同父节点的节点互称为兄弟节点；F、G节点互为兄弟节点。

叶节点：没有子节点的节点称为叶节点，也叫叶子节点，比如上图的H、E、F、G都是叶子节点。

子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。

节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。

深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；（从上往下看）

高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；（从下往上看）

演示图解树的由来

2.3 二叉搜索树

二叉树：二叉树的每个节点最多只能有2个子节点

上面这个图的B节点有D、E、F三个子节点，所以这个树就不是二叉树，而是称为多路树

上面这幅图每个节点最多只能有两个节点，是二叉树，并且二叉树的子节点称为“左子节点”和“右子节点”

2.3.1 二叉搜索树是什么？

如果我们给一个二叉树添加一个额外的概念，就可以得到一种被称作 **二叉搜索树 (binary search tree)**的特殊二叉树

2.3.2 二叉搜索树的要求

• 如果它的左子树不为空，则左子树上所有的节点的值都要小于它的根节点的值
• 如果它的右子树不为空，则右子树上所有的节点的值都要小于它的根节点的值
• 它的左、右子树也分别为二叉排序树

2.3.3 二叉搜索树 - 查找节点

查找某个节点，必须从根节点开始查找

• 查找值比当前节点大，就搜索右子树
• 查找值和当前的节点值相等，停止搜索(已经找到)
• 查找值比当前节点小，就搜索左子树

2.3.4 二叉搜索树 - 插入节点

• 要插入节点，必须先找到需要插入的位置。与查找操作相似，由于二叉搜索树的特殊性
• 待插入的节点也需要从根节点开始比较，小于根节点则与根节点左子树比较
• 反之则与右子树比较，直到左子树为空或者右子树为空，则插入到响应的位置

2.3.5 二叉搜索树 - 遍历节点

遍历树是一种特定的顺序访问树的每一个节点，比较常用的有前序遍历、中序遍历和后续遍历。而二叉搜索树最常用的就是 中序遍历

• 中序遍历：左子树 -> 根节点 -> 右子树
• 前序遍历：根节点 -> 左子树 -> 右子树
• 后续遍历：左子树 -> 右子树 -> 根节点

2.3.6 二叉搜索树 - 查找最大值和最小值

• 要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节点，这个节点就是最小值

• 同理要找最大值，一直找到根节点的右节点，直到没有右节点，就是最大值。

2.3.7 二叉搜索树 - 删除节点

删除节点是最复杂的操作。删除的节点有三种情况，前2种比较简单，但是第三种比较复杂

• 该节点是叶子节点(没有子节点)
• 该节点有一个子节点
• 该节点有两个子节点

删除没有子节点的节点

要删除子节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为null即可

删除只有一个子节点的节点

删除只有一个子节点的节点，只要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可

删除有两个子节点的节点

当删除的节点存在2个节点的时候，那么删除之后，两个子节点的位置我们就没有办法处理了，

既然处理不了，我们就想到了另外一种办法，用另外一个节点来代替被删除的节点，那么应该使用哪个节点呢？

我们知道二叉搜索树中的节点是按照关键字来排序的，某个节点的关键字次高节点是它的中序遍历 后继节点

用后续节点来代替删除的节点，显然该二叉树还是有序的

.png)

那么如何找到删除节点中的后继节点呢？

我们稍微分析一下，实际上后继节点就是比要删除的节点的大的最小的哪个节点，只有这样代替删除的节点后才能满足二叉搜索树的特性，后继节点也就是：比删除节点大的最小节点

问题：删除是否有必要吗？

在上面的理论进行分析，删除还是比较复杂的操作，那么我们要不要删除此节点？

可以不删除此节点，只需要在Node类中增加一个标识字段isDelete，当该字段为true的时候，标识该节点已经删除，反之就没有删除，这样删除就不改变原有的数据结构了，但是影响的就是查询的时候需要进行判断。

2.3.8 二叉搜索树 - 时间复杂度分析

• 回顾经典的的查找算法 - 二分查找算法

  • [1,2,3,4,5,6,7,8,9]
  • 暴力算法：运气好性能不错，运气不好，性能下降
  • 二分查找：每次查找的时候，折半查找。但是要求数据必须是有序数组

• 二分查找的最大缺陷是什么？

  • 强制依赖数组的有序性

• 数组有什么缺陷

  • 不能动态扩容，插入和删除将会很多次移动

• 那么怎么才能拥有二分查找的高性能又能拥有链表一样的灵活性？

  • 二分查找树

• 二分查找算法时间复杂度推算过程

  • 第几次查询	剩余待查询元素数量
    1	N/2
    2	N/(2^2)
    3	N/(2^3)
    K	N/(2^K)

  • 从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，

    也就是是查到剩余最后一个数才查到我们想要的数据，也就是

    N/(2^K)=1 => 2^K = N => **K = log2 (N) => 二分查找算法时间复杂度：O(log2(N)) => O(logN)

2.3.9 二叉搜索树的致命缺陷

这颗二叉树查询效率咋样呢？

O(N)

怎么解决 二叉搜索树 退化成线性链表的问题？

如果插入元素时，树可以自动调整两边平衡，会保持不错的查找性能

2.4 AVL树简介

AVL树有什么特点？

1、具有二叉查找树的全部特性。

2、每个节点的左子树和右子树的高度差至多等于1。

平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了！（插入或者删除时，会发生左旋、右旋操作，使这棵树再次左右保持一定的平衡）

如何构建AVL树？//TODO

2.5 为什么有了平衡树还需要红黑树？

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，

因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，

几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树！

3.总结与彩蛋

• 了解历史，知其所以然

参考资料

红黑树(五)之 Java的实现

红黑树原理源码讲解

画图工具 Draw.io

使用网站：https://app.diagrams.net/ 可以直接使用网站去做

此画图工具开源地址： https://github.com/jgraph/drawio

Windows版本：同级目录下 软件包/draw.io-13.0.3-windows-no-installer.exe

本地的演示图片地址：同级目录下draw.io/树从链表的演变.png

**下一篇：Java 集合框架 - HashMap 底层 红黑树深度解读 **

• 敬请期待...