参考资料：https://blog.csdn.net/u014106644/article/details/90174332；

https://blog.csdn.net/qq_40722604/article/details/107792636；

https://blog.csdn.net/a519640026/article/details/106940115；

https://blog.csdn.net/qq_40722604/article/details/107792636；

https://blog.csdn.net/qq_41854763/article/details/82694873；

https://blog.csdn.net/weixin_42340670/article/details/80550932

Java中的树

• 说起树，我们最早是在大学学的八大数据结构：

数组，栈，队列，链表，树，散列表，堆，图

平常我们常用的可能就是数组，队列，链表，散列表这四种，

那么问题来了：为什么常用这几种？树和这几种数据结构有什么区别呢？

要想弄清楚这个问题，我们先要弄清楚这几个是什么东西

1. 数组：同一中元素类型的有限个元素排列起来的一个集合
2. 队列：一种特殊的线性表，先进先出
3. 链表：在屋里单元上非连续的存储结构，元素间的顺序由指针链接次序完成
4. 散列表：也叫哈希表，由key-value组成，可根据key直接找到对应的数据value

1. 那么树是一个什么东西呢？

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

    ①每个节点有零个或多个子节点；

    ②没有父节点的节点称为根节点；

    ③每一个非根节点有且只有一个父节点；

④除了根节点外，每个子节点可以分为多个不相交的子树；

这些是数据结构中的定义：

• 那么java中的树，集合又是什么样的呢？

1. java中的集合框架:
2. 

这就是java的集合框架结构，我们可以看到我们常用的几种：

List类型的arraylist，linkedlist

Set类型的hashset

Map类型的hashmap，linkedhashmap都在这里面

1. 那么我们看一下arraylist的内部实现

我们一般都是直接

List<String> xxx = new arraylist<>();

那么这样的内部是什么呢？

这也就是说我们这样直接是创建了一个object类型的空数组，

那么指定大小的arraylist呢？

这些都是很简单明了的 ，那么我们来看看arraylist的扩容过程

就是说每次扩容一般情况是扩容1.5倍原先的长度

1. 那么linkedlist呢？

Linkedlist是内部有一个

每个元素都会创建一个node，有2个指针指向前面和后面的node

Linkedlist中有

首节点和尾部节点的指针，方便我们在记录链表的首尾

那么链表是什么样的add过程呢？

set过程

那么vector呢

其实vector和arraylist 一样，就是add加上了synchronized关键字

1. 这里比较下vector，arraylist，linkedlist？

1. 相比linkedlist，arraylist查找方便，但删除，插入中间元素困难，但删除插入最后一个元素不困难
2. Arraylist和vector存在扩容的问题，arraylist一次扩容1.5倍，而vector默认是2倍，而linkedlist没有这个问题
3. 相比arraylist，vector更安全，但更加消耗性能，反而在使用中基本不适用

• 那么set呢？

1. hashSet

从这个构建函数可以看得出来：

Hashset能够保证每个元素的唯一性，就是使用的hashmap来存储数据

他所有的操作都是对他的这个hashmap的操作

• Hashmap

1. 其实我们大家都知道hashmap在jdk1.8中底层就用了树（红黑树），他的总体架构是：

数组+链表+红黑树

既然说了jdk1.8，那么我们先说下jdk1.7中hashmap的结构：

数组+链表

他们之间的差别就是：

当hash碰撞时，都开始使用链表处理碰撞，但1.8之后，当链表长度>=8时，将链表转成红黑树，大大减少查找时间，当节点<=6时，他又会变成链表

Hashmap的结构图：

从这3张图：我们可以清晰的看到：

当一个元素进入hashmap时，先根据key的hashcode比较，看是否发生碰撞，没有则在数组的位置上创建一个node来存放该元素，当发生碰撞时，则在碰撞的位置的链表尾部上添加该元素的node

当链表的元素大于8时，呢么他会转成红黑树

  

红黑树的类：

这里树先放一下，我们回到hashmap

我们上面各种集合都涉及到扩容，那么hashmap怎么扩容呢？

Hashmap默认初始大小是10，加载因子默认是0.75，也就是说当hashmap中插入的元素大于总容量的0.75时，hashmap就会发生扩容，扩容的默认比例是，扩容到原先的2倍。我们看下源代码：

  

说到这，我感觉集合说的也差不多了，正式进入树

• 树

树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。

1. 按分叉来区分：二叉树，多路树

二叉树的遍历方法：

1.先序遍历：按照根节点->左子树->右子树的顺序访问二叉树

  

先序遍历：（1）访问根节点；（2）采用先序递归遍历左子树；（3）采用先序递归遍历右子树；

(注：每个节点的分支都遵循上述的访问顺序，体现“递归调用”)

先序遍历结果：A BDFE CGHI

思维过程：（1）先访问根节点A，

（2）A分为左右两个子树，因为是递归调用，所以左子树也遵循“先根节点-再左-再右”的顺序，所以访问B节点，

（3）然后访问D节点，

（4）访问F节点的时候有分支，同样遵循“先根节点-再左--再右”的顺序,

(5)访问E节点，此时左边的大的子树已经访问完毕，

(6)然后遵循最后访问右子树的顺序，访问右边大的子树，右边大子树同样先访问根节点C,

(7)访问左子树G,

(8)因为G的左子树没有，所以接下俩访问G的右子树H,

(9)最后访问C的右子树I

2.中序遍历：按照左子树->根节点->右子树的顺序访问

中序遍历：（1）采用中序遍历左子树；（2）访问根节点；（3）采用中序遍历右子树

中序遍历结果：DBEF    A    GHCI

3.后序遍历：按照左子树->右子树-->根节点的顺序访问

  

后序遍历：（1）采用后序递归遍历左子树；（2）采用后序递归遍历右子树；（3）访问根节点；

后序遍历的结果：DEFB  HGIC   A

二叉查找树

二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质：
任意节点左子树不为空,则左子树的值均小于根节点的值
任意节点右子树不为空,则右子树的值均大于于根节点的值
任意节点的左右子树也分别是二叉查找树
没有键值相等的节点

局限性及应用
一个二叉查找树是由n个节点随机构成,所以，对于某些情况,二叉查找树会退化成一个有n个节点的线性链.如下图:

1. AVL树

AVL树是带有平衡条件的二叉查找树，和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的

使用场景：

AVL树适合用于插入删除次数比较少，但查找多的情况。
也在Windows进程地址空间管理中得到了使用
旋转的目的是为了降低树的高度，使其平衡
AVL树特点：
AVL树是一棵二叉搜索树
AVL树的左右子节点也是AVL树
AVL树拥有二叉搜索树的所有基本特点
每个节点的左右子节点的高度之差的绝对值最多为1，即平衡因子为范围为[-1,1]

1. 红黑树

一种自平衡二叉查找树, 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保从根到叶子节点的最长路径不会是最短路径的两倍，用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决

使用场景：

红黑树多用于搜索,插入,删除操作多的情况下

原因：
红黑树的查询性能略微逊色于AVL树，因为比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上完爆AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多

性质：
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

说完了概念，我们来看下红黑树的基本操作：

1. 右旋：就是把头上的节点向右转一下

1. 左旋：把头上的节点向左转一下

看到这，大家有个印象，我们来看下代码：

    

  

   

这个代码是将链表的node转换成红黑树的treenode，当转成treenode之后，我们就会进行红黑树的形成：

  

树形成后，我们要平衡树

平衡树，当我们发现不是红黑树之后，需要左旋和右旋

     这样我们才能得到一颗红黑树   右旋

这是只分析了1种情况，那么另外3种情况呢？

1. 需要先5和7调换位置，在进行右旋
2. 需要左旋
3. 需要12和15调换位置，再进行左旋

了解这之后我们无论红黑树有几层，我们都只需要找到这样的3个点就能进行红黑树的旋转，最后形成一颗红黑树。

那么红黑树的删除过程是怎么一个样子呢？

1. 这里先判断是否有个和hashcode碰撞的node，如果有，切key相同，则直接删除
2. 如果key不同，则判断是否是链表还是红黑树
3. 如果是红黑树再调用getTreeNode方法
4. 删除找到的节点

1. 1. 红黑树查找节点：

1. 1. 红黑树删除节点：

   先找到删除的节点，并将替换节点替换删除的节点

当删除的节点是黑色的时候，就是影响了红黑树的黑色高度的时候，这样就违反了红黑树的第5条，所以调用

说到这，红黑树就基本说完了，现在让我们看看B树和B+树

• B树：

1. 所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
4. 在关键字全集内做一次查找,性能逼近二分查找；
5. 非叶子结点   关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；即关键字时有序的；孩子指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

既然前面我们说了红黑树，avl树查询很快，为什么又要B树呢？

1. 当数据量太大，内存存不下时，数据只能放在磁盘上，而磁盘和内存间的访问时间又相差太大，，所以大量时间会用在磁盘IO上，那么我们需要提高程序性能，怎么办，红黑树完全无法做这样的操作：

红黑树的旋转需要全部的数据，而数据现在不能全在内存上

1. 红黑树的高度相对较大为 log n（底数为2），这样逻辑上很近的节点实际可能非常远，无法很好的利用磁盘预读（局部性原理），当我们读取磁盘一页数据时，他相邻的页也会被读取。

所以出现了B树，而且B树不像红黑树那样只有2个子树，他可以有多个子树，他可以分成4个子树，这样一下就可以排除四分之三的数据，而且B树一般是三层，不会像红黑树那样高度很大，大大节省了大数据量的查询时间

• B+树

1. 对于B树的改进，每个节点具有关键字以及孩子指针属性：
2. 非叶子结点的子树指针与关键字个数相同；
3. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
4. 为所有叶子结点增加一个链指针；
5. 所有关键字都在叶子结点出现；
6. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；不可能在非叶子结点命中；非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；更适合文件索引系统；

B-树和B+树的区别

1.B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。

如下所示B-树/B+树查询节点 key 为 50 的 data

B-树：

 

从上图可以看出，key 为 50 的节点就在第一层，B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。

B+树：

 

由于B+树所有的 data 域都在根节点，所以查询 key 为 50的节点必须从根节点索引到叶节点，时间复杂度固定为 O(log n)。

由此可得：B树的由于每个节点都有key和data，所以查询的时候可能不需要O(logn)的复杂度，甚至最好的情况是O(1)就可以找到数据，而B+树由于只有叶子节点保存了data，所以必须经历O(logn)复杂度才能找到数据

2. B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

 

根据空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。

B+树可以很好的利用局部性原理，若我们访问节点 key为 50，则 key 为 55、60、62 的节点将来也可能被访问，我们可以利用磁盘预读原理提前将这些数据读入内存，减少了磁盘 IO 的次数。

当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

由此可得：由于B+树的叶子节点的数据都是使用链表连接起来的，而且他们在磁盘里是顺序存储的，所以当读到某个值的时候，磁盘预读原理就会提前把这些数据都读进内存，使得范围查询和排序都很快

3.B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确

这个很好理解，由于B-树节点内部每个 key 都带着 data 域，而B+树节点只存储 key 的副本，真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的，一次磁盘 IO 会读取若干个 block，具体和操作系统有关，那么由于磁盘 IO 数据大小是固定的，在一次 IO 中，单个元素越小，量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树，从这点来看B+树相对B-树磁盘 IO 次数少。

由此可得：由于B树的节点都存了key和data，而B+树只有叶子节点存data，非叶子节点都只是索引值，没有实际的数据，这就时B+树在一次IO里面，能读出的索引值更多。从而减少查询时候需要的IO次数！

 

从上图可以看出相同大小的区域，B-树仅有 2 个 key，而B+树有 3 个 key。