关于java:啥是二叉搜索树B树B树AVL树红黑树怎么那么多的树一文全总结

在理解 B 树、B+ 树、AVL 树、红黑树 之前，咱们先看一下各种树型构造的大抵理论利用场景：

B 和 B + 树：次要用在文件系统以及数据库中做索引等

AVL 树：均衡二叉树之一，利用绝对其余数据结构比拟少，windows 对过程地址空间的治理用到了 AVL

红黑树：均衡二叉树，广泛应用在 C ++STL 中，比方 map 和 set，Java 的 TreeMap

树结构曾经有了很多种形式，为何呈现 B 树、B+ 树、AVL 树、红黑树，首先要理解一下二叉搜寻树

1. 二叉搜寻树

1）概念

均衡二叉树是采纳二分法思维把数据按规定组装成一个树形构造的数据，用这个树形构造的数据缩小无关数据的检索，大大的晋升了数据检索的速度。

咱们在二叉树的深度遍历过程中，应用中序遍历，就能获取失去有序的序列。

2）特点

• 任意节点左子树不为空, 则左子树的值均小于根节点的值.
• 任意节点右子树不为空, 则右子树的值均大于于根节点的值.
• 任意节点的左右子树也别离是二叉查找树.
• 没有键值相等的节点.

3）二叉搜寻树存在的局限

二叉树在查找数据时，工夫复杂度 最好状况是 O(logn)，最坏状况下工夫复杂度 O(n)，如 a 图所示，二叉树进化成一个链表了，恰好抉择了最小或者最大的节点做 root，节点排在了一条直线上。

因而, 在二叉查找树的根底上, 又呈现了 AVL 树, 红黑树, 它们两个都是基于二叉查找树, 只是在二叉查找树的根底上又对其做了限度.

1. B 树

1）概念

B 树又名均衡多路查找树（查找门路不只两个），不同于常见的二叉树，它是一种多叉树，咱们常见的应用场景个别是在数据库索引技术里，大量使用者 B 树和 B + 树的数据结构。

有些教材中，也把 B 树称为 B - 树, - 只是一个符号，无需太在意命名模式。

B 树大多用在磁盘上用于查找磁盘的地址。因为磁盘会有大量的数据，有可能没有方法一次将须要的所有数据退出到内存中，所以只能逐个加载磁盘页，每个磁盘页就对应一个节点，而对于 B 树来说，B 树很好的将树的高度升高了，这样就会缩小 IO 查问次数，尽管一次加载到内存的数据变多了，但速度相对快于 AVL 或是红黑树的。

2）特点

1）定义任意非叶子结点最多只有 M 个儿子；且 M >2
2）所有节点关键字是按递增秩序排列，并遵循左小右大准则
3）位于 M - 1 和 M key 的子节点的值位于 M -1 和 M key 对应的 Value 之间
4）其它节点至多有 M / 2 个子节点 [M/2,M-1]
5）所有叶子节点都在同一层

3）B 树查问流程

这里应用字母来示意：

如上图我要从上图中找到 E 字母，查找流程如下：

（1）获取根节点的关键字进行比拟，以后根节点关键字为 M，E<M（26 个字母程序），所以往找到指向右边的子节点（二分法规定，左小右大，右边放小于以后节点值的子节点、左边放大于以后节点值的子节点）；

（2）拿到关键字 D 和 G，D<E<G 所以间接找到 D 和 G 两头的节点；

（3）拿到 E 和 F，因为 E =E 所以间接返回关键字和指针信息（如果树结构外面没有蕴含所要查找的节点则返回 null）；

搜寻 B 树时，很显著，拜访节点（即读取磁盘）的次数与树的高度呈反比，而 B 树与红黑树和一般的二叉查找树相比，尽管高度都是对数数量级，然而显然 B 树中 log 函数的底能够比 2 更大，因而，和二叉树相比，极大地缩小了磁盘读取的次数。

3.B+ 树

1）概念

B+ 树时 B 树的一种降级版本，B+ 树查找的效率要比 B 树更高、更稳固。

B+ 树是应文件系统所需而产生的一种 B 树的变形树 ( 文件的目录一级一级索引, 只有最底层的叶子节点 (文件) 保留数据 .), 非叶子节点只保留 索引, 不保留理论的数据, 数据都保留在叶子节点中.

这不就是文件系统文件的查找吗? 咱们就举个文件查找的例子: 有 3 个文件夹,a,b,c, a 蕴含 b,b 蕴含 c, 一个文件 yang.c, a,b,c 就是索引 (存储在非叶子节点), a,b,c 只是要找到的 yang.c 的 key, 而理论的数据 yang.c 存储在叶子节点上.
所有的非叶子节点都能够看成索引局部

2）特点

B+ 树和 B 树相似，但多了几条规定

• 非叶子结点的子树指针个数与关键字（节点中的元素个数）个数雷同
• 非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i], K[i+1]) 的子树（B- 树是开区间）
• 所有叶子结点有一个链指针
• 所有关键字都在叶子结点呈现
• 只有叶子节点有 Data 域

3）B+ 树与 B 树比照

1、B+树的层级更少 ：相较于 B 树，B+ 每个 非叶子 节点存储的要害字数更多，树的层级更少所以查问数据更快；

2、B+树查问速度更稳固 ：B+ 所有关键字数据地址都存在 叶子 节点上，所以每次查找的次数都雷同所以查问速度要比 B 树更稳固;

3、B+树人造具备排序功能：B+ 树所有的 叶子 节点数据形成了一个有序链表，在查问大小区间的数据时候更不便，数据紧密性很高，缓存的命中率也会比 B 树高。

4、B+树全节点遍历更快：B+ 树遍历整棵树只须要遍历所有的 叶子 节点即可，，而不须要像 B 树一样须要对每一层进行遍历，这有利于数据库做全表扫描。

B 树 绝对于 B+ 树 的长处是，如果常常拜访的数据离根节点很近，而 B 树 的非叶子 节点自身存有关键字其数据的地址，所以这种数据检索的时候会要比 B+ 树 快。

B+ 树绝对于 B 树的最次要的长处：

1. B+ 树只有叶子节点存放数据，而其余节点只寄存索引，而 B 树每个节点都有 Data 域。所以雷同大小的节点 B + 树蕴含的索引比 B 树的索引更多（因为 B 树每个节点还有 Data 域）
2. B+ 树的叶子节点是通过链表连贯的，所以找到上限后能很快进行区间查问，比 B 树中序遍历快

1. AVL 树（均衡二叉树）

1）概念

AVL、红黑树是对二叉搜寻树的改良版本。

均衡因子：节点的左右子树深度之差。在一棵均衡二叉树中，节点的均衡因子只能取 0、1 或者 -1，别离对应着左右子树等高，左子树比拟高，右子树比拟高。

AVL 树是带有平衡条件的二叉查找树，个别是用均衡因子差值判断是否均衡并通过旋转来实现均衡，左右子树树高不超过 1，和红黑树相比，它是严格的均衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过 1）。

不论咱们是执行插入还是删除操作，只有不满足下面的条件，就要通过旋转来保持平衡，而 旋转是十分耗时 的，由此咱们能够晓得AVL 树适宜用于插入删除次数比拟少，但查找多的状况。

由上图所知：任意节点的左右子树的均衡因子差值都不会大于 1

2）AVL 保持平衡的四种操作

增删改查操作和二分搜寻树相似，然而要多思考的就是对节点的均衡思考，如果一串数字的插入程序为 3，4，5。那么这棵树结构就会进化为一个链表。而这时候 AVL 就会对这个树进行旋转操作来达到均衡，所以，咱们就晓得旋转的操作会在减少，删除，批改这三个中央进行旋转。旋转操作分为上面四种状况

1. LL 右单旋转

如图，8 的左子树曾经进化为链表，并且 5，8 这两个节点不再均衡，这时咱们先找到深度最深的不均衡节点 5，对节点 5 进行 LL 旋转操作，在如图的这种状况下，失去右图的构造

2. RR 左单旋转

如图，当插入程序为当插入程序为 8，3，10，13，15 的时候，树的构造变成右边的样子，这时 10 节点和 8 节点曾经不均衡，为了放弃 AVL 的均衡，咱们要对 10 节点进行 RR 旋转，如右图所示

3. LR 先左后右

如图。5，8 节点曾经不均衡，这时要对 5 节点做均衡解决，首先将 5 进行 RR 左旋转，7 的左节点也变为 5 的右节点。

这时 7，8 还是不均衡的，对 8 进行右旋转，8 的右节点也变为 8 的左节点，如图。

4. RL 先右后左

如左图，8，13 节点不均衡，对 13 节点进行 LL 右旋转，失去右图

这时 8，10 是不均衡的，对 8 节点进行 RR 左旋转，失去右图。

以上就是保持平衡的形式。

3）AVL 存在的局限性

因为保护这种高度均衡所付出的代价比从中取得的效率收益还大, 故而理论的利用不多，

更多的中央是用谋求部分而不是十分严格整体均衡的红黑树. 当然, 如果利用场景中对插入删除不频繁, 只是对查找要求较高, 那么 AVL 还是较优于红黑树.

1. 红黑树

1）概念

一种二叉查找树，但在每个节点减少一个存储位示意节点的色彩，能够是 red 或 black（非红即黑）。通过对任何一条从根到叶子的门路上各个节点着色的形式的限度，红黑树确保没有一条门路会比其它门路长出两倍。它是一种弱均衡二叉树(因为是弱均衡，能够推出，雷同的节点状况下，AVL 树的高度低于红黑树)，绝对于要求严格的 AVL 树来说，它的旋转次数少，所以对于搜寻、插入、删除操作较多的状况下，咱们就用红黑树。

2）特色

1、每个节点非红即黑；

2、根节点是黑的；

3、每个叶节点 (叶节点即树尾端 NULL 指针或 NULL 节点) 都是黑的；

4、如果一个节点是红的, 那么它的两儿子都是黑的；

5、对于任意节点而言，其到叶子点树 NULL 指针的每条门路都蕴含雷同数目的黑节点；

6、高度始终保持在 h = logn

7、红黑树的查找、插入、删除的工夫复杂度最坏为 O(log n)

3）红黑树的自均衡操作

但插入、或者删除红黑树的数值时，为了从新合乎红黑树的规定，须要对红黑树进行旋转、变色操作。

当在对红黑树进行插入和删除等操作时，对树做了批改可能会毁坏红黑树的性质。为了持续放弃红黑树的性质，能够通过对结点进行从新着色，以及对树进行相干的旋转操作，即通过批改树中某些结点的色彩及指针构造，来达到对红黑树进行插入或删除结点等操作后持续放弃它的性质或均衡的目标。

树的旋转分为左旋和右旋，上面借助图来介绍一下左旋和右旋这两种操作。

• 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点放弃不变。

 应用动图更好了解：【由动图可知，红黑树并不是简略的旋转，须要随同着子树的转换】

• 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点放弃不变。

应用动图更好了解：

咱们先疏忽色彩，能够看到旋转操作不会影响旋转结点的父结点，父结点以上的构造还是放弃不变的。
左旋 只影响旋转结点和其 右子树 的构造，把右子树的结点往左子树挪了。
右旋 只影响旋转结点和其 左子树 的构造，把左子树的结点往右子树挪了。

所以旋转操作是 部分 的。另外能够看出旋转能放弃红黑树均衡的一些打量了：当一边子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点。

• 变色：结点的色彩由红变黑或由黑变红。

Java _TreeMap_实现了_SortedMap_接口，也就是说会依照 key 的大小程序对_Map_中的元素进行排序，key大小的评判能够通过其自身的天然程序（natural ordering），也能够通过结构时传入的比拟器（Comparator）。_TreeMap_底层通过红黑树（Red-Black tree）实现

看一下红黑树插入一个数值，红黑树自均衡的一个过程：

6. 二叉搜寻树、B 树、B+ 树、AVL 树、红黑树的常见面试题

1）为什么设计红黑树

红黑树通过它规定的设定，确保了插入和删除的最坏的工夫复杂度是 O(log N)。

红黑树 解决了 AVL 均衡二叉树的保护起来比拟麻烦的问题，红黑树，读取略逊于 AVL，保护强于 AVL，每次插入和删除的均匀旋转次数应该是远小于均衡树。

因而：

绝对于要求严格的 AVL 树来说，红黑树的旋转次数少，所以对于插入、删除操作较多的状况下，咱们就用红黑树。然而，只是对查找要求较高, 那么 AVL 还是较优于红黑树.

2）B 树的作用

B 树大多用在磁盘上用于查找磁盘的地址。因为磁盘会有大量的数据，有可能没有方法一次将须要的所有数据退出到内存中，所以只能逐个加载磁盘页，每个磁盘页就对应一个节点，而对于 B 树来说，B 树很好的将树的高度升高了，这样就会缩小 IO 查问次数，尽管一次加载到内存的数据变多了，但速度相对快于 AVL 或是红黑树的。

3）B 树和 B+ 树的区别

B/B+ 树用在磁盘文件组织、数据索引和数据库索引中。其中 B + 树比 B 树更适宜理论利用中操作系统的文件索引和数据库索引，因为：
1、B+ 树的磁盘读写代价更低
B+ 树的外部结点并没有指向关键字具体信息的指针。因而其 外部结点 绝对 B 树 更小。如果把所有同一外部结点的关键字寄存在同一盘块中，那么盘块所能包容的关键字数量也越多。一次性读入内存中的须要查找的关键字也就越多。相对来说 IO 读写次数也就升高了。

举个例子，假如磁盘中的一个盘块包容 16bytes，而一个关键字 2bytes，一个关键字具体信息指针 2bytes。一棵 9 阶 B -tree(一个结点最多 8 个关键字)的外部结点须要 2 个盘快。而 B + 树外部结点只须要 1 个盘快。当须要把外部结点读入内存中的时候，B 树就比 B + 树多一次盘块查找时间(在磁盘中就是盘片旋转的工夫)。

2、B+-tree 的查问效率更加稳固
因为非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的 门路长度雷同，导致每一个数据的查问效率相当。

3、 B 树在元素遍历的时候效率较低

因为 B + 树的数据都存储在叶子结点中，分支结点均为索引，不便扫库，只须要扫一遍叶子结点即可，然而 B 树因为其分支结点同样存储着数据，咱们要找到具体的数据，须要进行一次中序遍历按序来扫，所以 B + 树更加适宜在区间查问的状况，所以通常 B + 树用于数据库索引。在数据库中基于范畴的查问绝对频繁，所以此时 B + 树优于 B 树。

4）B 树和红黑树的区别

最大的区别就是树的深度较高，在磁盘 I / O 方面的体现不如 B 树。

要获取磁盘上数据，必须先通过磁盘移动臂挪动到数据所在的柱面，而后找到指定盘面，接着旋转盘面找到数据所在的磁道，最初对数据进行读写。磁盘 IO 代价次要破费在查找所需的柱面上，树的深度过大会造成磁盘 IO 频繁读写。依据磁盘查找存取的次数往往由树的高度所决定。

所以，在大规模数据存储的时候，红黑树往往呈现因为树的深度过大而造成磁盘 IO 读写过于频繁，进而导致效率低下。在这方面，B 树体现绝对优异，B 树能够有多个子女，从几十到上千，能够升高树的高度。

5）AVL 树和红黑树的区别

红黑树的算法工夫复杂度和 AVL 雷同，但 统计性能 比 AVL 树更高。

1、红黑树和 AVL 树都可能以 O(log2 n)的工夫复杂度进行搜寻、插入、删除操作。
2、因为设计，红黑树的任何不均衡都会在三次旋转之内解决。AVL 树减少和删除可能须要通过一次或屡次树旋转来从新均衡这个树。

在 查找 方面：
  红黑树的性质 (最长门路长度不超过最短门路长度的 2 倍)，其查找代价根本维持在 O(logN) 左右，但在最差状况下 (最长门路是最短门路的 2 倍少 1)，比 AVL 要略逊色一点。
  AVL 是严格均衡的二叉查找树（均衡因子不超过 1）。查找过程中不会呈现最差状况的单支树。因而查找效率最好，最坏状况都是 O(logN) 数量级的。

所以，综上：
  AVL 比 RBtree 更加均衡，然而 AVL 的插入和删除会带来大量的旋转。所以如果 插入和删除比拟多 的状况，应该应用 RBtree, 如果 查问操作比拟多，应该应用AVL。

AVL 是一种高度均衡的二叉树，保护这种高度均衡所付出的代价比从中取得的效率收益还大，故而理论的利用不多，更多的中央是用谋求部分而不是十分严格整体均衡的红黑树。当然，如果场景中对插入删除不频繁，只是对查找特地有要求，AVL 还是优于红黑的。

6）数据库为什么应用 B 树，而不应用 AVL 或者红黑树

咱们假如 B + 树一个节点能够有 100 个关键字，那么 3 层的 B 树能够包容大略 1000000 多个关键字（100+101100+101101*100）。而红黑树要存储这么多至多要 20 层。所以应用 B 树绝对于红黑树和 AVL 能够 缩小 IO 操作

7）mysql 的 Innodb 引擎为什么采纳的是 B + 树的索引形式

B+ 树只有叶子节点存放数据，而其余节点只寄存索引，而 B 树每个节点都有 Data 域。所以雷同大小的节点 B + 树蕴含的索引比 B 树的索引更多（因为 B 树每个节点还有 Data 域）

还有就是 B + 树的叶子节点是通过链表连贯的，所以找到上限后能很快进行区间查问，比 B 树中序遍历快

8）红黑树 和 b+ 树的用处有什么区别？

1. 红黑树多用在外部排序，即全放在内存中的，STL 的 map 和 set 的外部实现就是红黑树。
2. B+ 树多用于外存上时，B+ 也被成为一个磁盘敌对的数据结构。

9）为什么 B + 树比 B 树更为敌对

• 磁盘读写代价更低
  树的非叶子结点外面没有数据，这样索引比拟小，能够放在一个 blcok（或者尽可能少的 blcok）外面。防止了树形构造一直的向下查找，而后磁盘不停的寻道，读数据。这样的设计，能够升高 io 的次数。
• 查问效率更加稳固
  非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当。
• 遍历所有的数据更不便
  B+ 树只有遍历叶子节点就能够实现整棵树的遍历，而其余的树形构造 要中序遍历才能够拜访所有的数据。

参考：

https://www.cnblogs.com/carpenterlee/p/5503882.html

https://www.jianshu.com/p/86a1fd2d7406

https://juejin.im/post/6844903859974848520#heading-16

https://blog.csdn.net/whoamiyang/article/details/51926985

https://marian5211.github.io/2018/03/09/B%E6%A0%91%E3%80%81B-%E6%A0%91%E3%80%81AVL%E6%A0%91%E3%80%81Trie%E6%A0%91%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8%E5%9C%BA%E6%99%AF/

最初的最初，欢送关注公众号。。。。。

————————  end ————————————-