前言

本文收录于专辑：http://dwz.win/HjK，点击解锁更多数据结构与算法的常识。

你好，我是彤哥。

后面两节，咱们一起学习了对于跳表的理论知识，并手写了两种齐全不同的实现，咱们放一张图来简略地回顾一下：

实现跳表的要害之处是在有序链表的根底上加上各层索引，通过这些索引能够做到 O(log n)的工夫复杂度疾速地插入、删除、查找元素。

说起跳表，咱们就不得不提另一种十分经典的数据结构——红黑树，红黑树绝对于跳表来说，尽管工夫复杂度都是 O(log n)，然而红黑树的应用场景绝对更宽泛一些，在晚期的 Linux 内核中就始终存在红黑树的实现，也使用在了更高效的多路复用器 Epoll 中。

所以，红黑树是每一个程序员不得不会的知识点，甚至有些变态的面试官，还会让你手写红黑树的一部分实现，比方左旋、右旋、插入均衡的过程、删除均衡的过程，这些内容非常复杂，靠死记硬背往往很难彻底把握。

彤哥也是始终在寻找一种红黑树的记忆法，总算让我找到了那么一种还算不错的形式，从红黑树的起源登程，了解红黑树的实质，再从实质登程，彻底把握不必死记硬背的办法，最初再把它手写进去。

从本节开始，我也将把这种办法传递给你，因而，红黑树的局部，我会分成三个大节来解说：

• 从红黑树的起源，到红黑树的实质
• 从红黑树的实质，找到不必死记硬背的办法
• 不靠死记硬背，手写红黑树

好了，上面咱们就进入第一大节。

红黑树的起源

二叉树

说起树，咱们不得不说最有名的树，那就是二叉树，什么是二叉树呢？

二叉树（binary tree），是指树中的每个节点最多只有两个子节点的树。

当然，二叉树自身仿佛没什么用，咱们平时说的二叉树基本上都是指二叉查找树，或者叫有序二叉树、二叉搜寻树、二叉排序树。

二叉查找树

二叉查找树（BST，binary search tree），就是在二叉树的根底上减少有序性，这个有序性个别是指天然程序，有了有序性，咱们就能够应用二叉树来疾速的查找、删除、插入元素了。

比方，下面这颗二叉查找树，查找元素的均匀工夫复杂度为 O(log n)。

然而，二叉查找树有个十分重大的问题，试想，还是这三个元素，如果依照 A、B、C 的程序插入元素会怎么？

这是啥？单链表？没错，当依照元素的天然程序插入元素的时候，二叉查找树就进化成单链表了，单链表的插入、删除、查找元素的工夫复杂度是多少？O(n)。

所以，在极限状况下，二叉查找树的工夫复杂度是十分差的。

既然，插入元素后有可能导致二叉查找树的性能变差，那么，咱们是否能够减少一些伎俩，让插入元素后的二叉查找树仍然性能良好呢？

答案是必定的，这种伎俩就叫做 均衡，这种能够自均衡的树就叫做均衡树。

均衡树

均衡树（self-balancing or height-balanced binary search tree），是指插入、删除元素后能够自均衡的二叉查找树，使得它的工夫复杂度能够始终渐近于 O(log n)。

比方，下面那颗树，按 A、B、C 插入元素后，做一次旋转操作，就能够再次变成查找时间复杂度为 O(log n)的树。

然而，均衡树始终只是一个概念，直到 1962 年才由两个苏联人创造了第一种均衡树——AVL 树。

严格来说，均衡树是指能够自均衡的二叉查找树，三个关键词：自均衡、二叉、查找（有序）。

AVL 树

AVL 树（由发明者Adelson-Velsky 和 Landis 的首字母缩写命名），是指任意节点的两个子树的高度差不超过 1 的均衡树。

比方，下面这颗树，就是一颗 AVL 树，不信你能够数数看，是不是每个节点的两个子树的高度差都不超过 1。

是不是很难发现它真的是一颗 AVL 树，没错，这是 AVL 树的第一个毛病，不够直观，特地是节点个数多的时候。

第二个毛病，就是插入、删除元素的时候自均衡的过程非常复杂，比方，下面这颗树插入一个节点T：

咱们从 T 往上找，它的父节点 U，U 的两颗子树的高度差为 1，满足 AVL 树的规定，再往上，S 的两颗子树的高度差为 1，也满足规定，再往上，V 的两颗子树的高度差为 2，不满足规定，此时，须要一个自均衡的过程，该如何自均衡呢？

我上面给出图示，你能够试着了解一下：

红色节点示意旋转的轴。

通过两次旋转，让这颗树再次变成了 AVL 树，而且这只是其中一种插入场景，实在的状况还要依据插入的地位的不同做不同的旋转，你能够多插入几个节点本人尝试均衡一下。

同样地，AVL 树的代码也不是那么好实现的，反正，到目前为止，彤哥是没搞懂 AVL 树的各种规定。

基于这些毛病，所以，起初又倒退进去了各种各样的神奇的均衡树。

2- 3 树

2- 3 树，是指每个具备子节点的节点（外部节点，internal node）要么有两个子节点和一个数据元素，要么有三个子节点和两个数据元素的自均衡的树，它的所有叶子节点都具备雷同的高度。

简略点讲，2- 3 树的非叶子节点都具备两个分叉或者三个分叉，所以，称作 2 叉 - 3 叉树更容易了解。

另外一种说法，具备两个子节点和一个数据元素的节点又称作 2 节点，具备三个子节点和两个数据元素的节点又称作 3 节点，所以，整颗树叫做 2 - 3 树。

2- 3 树，插入元素后自均衡的过程绝对于 AVL 树就要简略得多了，比方，下面这颗树，再插入一个元素 K，它会先找到 I J 这个节点，插入元素 K，造成长期节点 I J K，不合乎 2 - 3 树的规定，所以决裂，J 往上移，F H这个节点变成了 F H J 了，也不合乎 2 - 3 树的规定，持续上移H，根节点变为D H，同时，上移的过程中，子节点也要相应的决裂，过程大抵如下：

画图辛苦了，关注一波：彤哥读源码。

能够看到，下面自均衡的过程中，呈现了一种节点，它具备四个子节点和三个数据元素，这个节点能够称作 4 节点，如果把 4 节点当作是能够容许存在的，那么，就呈现了另一种树：2-3- 4 树。

2-3- 4 树

2-3- 4 树，它的每个非叶子节点，要么是 2 节点，要么是 3 节点，要么是 4 节点，且能够自均衡，所以称作 2 -3- 4 树。

2 节点、3 节点、4 节点的定义在下面曾经提及，咱们再重申一下：

2 节点：蕴含两个子节点和一个数据元素；

3 节点：蕴含三个子节点和两个数据元素；

4 节点：蕴含四个子节点和三个数据元素；

当然，2-3- 4 树插入元素的过程也很好了解，比方，下面这颗树，插入元素 M，找到 K L 这个节点，插入即可，造成 4 节点，满足规定，不须要自均衡：

再插入元素 N 呢？过程与 2 - 3 树一样，向上决裂即可，此时，两头节点有两个，取任意一个上移都是能够的，咱们这里以左中节点上移为例，大抵过程如下：

是不是挺简略的，至多比 AVL 树那种左旋右旋简略得多。

同样地，在 2 -3- 4 树自均衡的过程中呈现了长期的 5 节点，所以，如果容许 5 节点的存在呢？

嗯，2-3-4- 5 树由此诞生！

同样地，还有 2 -3-4-5- 6 树、2-3-4-5-6- 7 树……子子孙孙，无穷尽也~

所以，有人就把这一类树演绎为一个新的名字：B 树。

B 树

B 树，示意的是一类树，它容许一个节点能够有多于两个子节点，同时，也是自均衡的，叶子节点的高度都是雷同的。

所以，为了更好地区分一颗 B 树到底属于哪一类树，咱们给它一个新的属性：度（Degree）。

具备度为 3 的 B 树，示意一个节点最多有三个子节点，也就是 2 - 3 树的定义。

具备度为 4 的 B 树，示意一个节点最多有四个子节点，也就是 2 -3- 4 树的定义。

B 树，一个节点能够存储多个元素，有利于缓存磁盘数据，整体的工夫复杂度趋向于 O(log n)，原理也比较简单，所以，常常用于数据库的索引，包含晚期的 mysql 也是应用 B 树来作为索引的。

然而，B 树有个大缺点，比方，我要按范畴查找元素，以下面的 2 -3- 4 树为例，查找大于 B 且小于 K 的所有元素，该怎么实现呢？

很难，简直无解，所以，前面又呈现代替 B 树的计划：B+ 树。

当然了，B+ 树不是本节的重点，本节的重点是红黑树。

纳尼，红黑树在哪里？写了 3000 多字了，还没见到红黑树的影子，我尬了~

来了来了，有意思的红黑树来了~~

红黑树

先上一张图，请认真领会：

看明确了没有？红黑树是啥？红黑树就是 2 -3- 4 树！！！

OK，本节到此结束。

后记

本节，咱们一起从二叉树登程，一路通过二叉查找树、均衡树、AVL 树、2- 3 树、2-3- 4 树、B 树，最初终于得出了红黑树的实质，红黑树的实质就是一颗 2 -3- 4 树，换了个皮肤而已。

那么，为什么要再造一个红黑树呢？间接用 2 -3- 4 树它不香么？

咱们下一节解答，同时，下一节，咱们将从红黑树的实质登程，彻底了解红黑树插入、删除、查找、左旋、右旋的全过程，再也不必死记硬背了，还不来关注我 ^^

关注公主号“彤哥读源码”，解锁更多源码、根底、架构常识。