前言大家好，我是童哥。在前面两节中，我们一起学习了关于跳转列表的理论知识，亲手写了两个完全不同的实现。放一张图简单回顾一下：实现跳表的关键是在有序链表的基础上，在每一层添加索引，通过这些索引，可以快速插入、删除、查找时间复杂度为O(logn)。说到跳表，就不得不提另一种非常经典的数据结构——红黑树。与跳表相比，红黑树的时间复杂度为O(logn)，但是红黑树的使用场景相对更广。红黑树的实现一直存在于早期的Linux内核中，在效率更高的多路复用器Epoll中也有使用。所以红黑树是每个程序员都必须知道的知识点，甚至有些变态的面试官会让你手写红黑树的一部分，比如左撇子，右撇子，过程插入余额和删除余额。过程，这些内容非常复杂，靠死记硬背往往很难完全掌握。童哥也一直在找红黑树的记忆方法，终于让我找到了这么一个相当不错的方法，从红黑树的起源说起，了解红黑树的本质，从本质，彻底掌握方法，不用死记硬背，最后手写出来。从这一节开始，我也把这个方法传给大家。因此，我将红黑树的部分分成三段来讲解：从红黑树的起源到红黑树的本质从红黑树的本质中找到一个做的方法notrequirerotememorization就是不靠死记硬背，手写红黑树就行，下面进入第一节。红黑树的由来二叉树说到树，不得不说最著名的树就是二叉树。什么是二叉树？二叉树是指树中每个节点至多有两个子节点的树。当然，二叉树本身似乎没什么用。我们平时说的二叉树基本上就是指二叉搜索树，或者说有序二叉树、二叉搜索树、二叉排序树。二叉搜索树二叉搜索树（BST，binarysearchtree）是在二叉树的基础上加了序。这个顺序一般是指自然顺序。有了顺序，我们就可以使用二叉树来快速查找、删除、插入元素。例如，在上面的二叉搜索树中，查找元素的平均时间复杂度是O(logn)。但是，二叉搜索树有一个很严重的问题。想想这三个要素。如果按A、B、C的顺序插入元素会怎样？这是什么？单向链表？当顺序插入元素时，二叉搜索树退化为单向链表。单向链表中插入、删除、查找元素的时间复杂度是多少？在）。因此，在极限情况下，二叉搜索树的时间复杂度很差。既然二叉搜索树在插入元素后性能可能会变差，那么我们是否可以增加一些手段让二叉搜索树在插入元素后仍然表现良好呢？答案是肯定的，这种方法叫做Balance，这种自平衡的树叫做平衡树。平衡树平衡树（self-balancingorheight-balancedbinarysearchtree）是指在插入和删除元素后可以自平衡的二叉搜索树，使其时间复杂度总是可以渐近到O(logn).比如上面的树，按照A、B、C插入元素，进行旋转操作后，又可以变成一棵搜索时间复杂度为O(logn)的树。然而，平衡树一直只是一个概念。直到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树指的是一棵自平衡树，每个子节点（internalnode，内部节点）要么有两个子节点和一个数据元素，要么有三个子节点和两个数据元素，它的所有叶子节点都有同样的高度。简单的说，2-3树的非叶子节点有两个叉或者三个叉，所以更容易理解为2-3叉树。也就是说，有两个子节点和一个数据元素的节点也称为2节点，有3个子节点和2个数据元素的节点也称为3节点，所以整棵树称为2-3树.对于2-3棵树，插入元素后自平衡的过程比AVL树要简单的多。比如在上面的树中插入一个元素K，它会先找到结点IJ，插入元素K，形成一个临时的结点IJK，不符合2-3树的规则，所以分裂，J移动向上，结点FH变为FHJ，不符合2-3树的规则。继续向上移动H，根节点变为DH。同时，在向上移动的过程中，子节点也要进行相应的分裂。过程大致如下：画图好难，关注一波：童哥阅读源码。可以看出，在上面的自平衡过程中，出现了一个节点，它有四个子节点，三个数据元素。这个节点可以称为4-节点。如果允许存在4个节点，那么，则出现另一棵树：2-3-4树。2-3-4树2-3-4树，它的每个非叶子节点要么是2个节点，要么是3个节点，要么是4个节点，并且可以自平衡，所以叫2-3-4树。2个节点、3个节点、4个节点的定义上面已经讲过了，这里再重申一下：2个节点：包含两个子节点和一个数据元素；3个节点：包含三个子节点和两个数据元素；4个节点：包含4个子节点和3个数据元素；当然，2-3-4树中插入元素的过程也很好理解。例如，在上面的树中，插入元素M，找到节点KL，将其插入，形成4个节点。满足规则不需要自平衡：再插入元素N怎么样？过程和2-3树一样，只是分裂了。这时候中间节点有两个，可以拿任何一个上移。这里我们以左边的中间结点向上移动为例，大致过程如下：是不是很简单，至少比左手和右手的AVL树简单很多。同样，2-3-4树在自平衡过程中出现了一个临时的5-node，如果允许5-node怎么办？那么，2-3-4-5树诞生了！同样的，还有2-3-4-5-6棵树，2-3-4-5-6-7棵树……子子孙孙，无穷无尽~于是，有人给这种树起了个新名字:B树。B-treeB-tree表示一种树，它允许一个节点有两个以上的子节点。同时也是自平衡的，叶子节点的高度是一样的。因此，为了更好的区分一棵B-tree属于哪一类树，我们赋予它一个新的属性：Degree。度数为3的B树表示一个节点最多有三个子节点，这是2-3树的定义。度为4的B树表示一个节点最多有四个子节点，这是2-3-4树的定义。B树，一个节点可以存储多个元素，有利于缓存磁盘数据。整体时间复杂度趋向于O(logn)，原理比较简单。因此常用于数据库索引，包括早期的mysql。B树用作索引。但是，B树有一个很大的缺陷。例如，我想按范围查找元素。以上面的2-3-4树为例，如何找出所有大于B小于K的元素呢？很难，几乎不可能因此，后来出现了一个替代B-tree的解决方案：B+树。当然B+树不是本节的重点，本节的重点是红黑树。纳尼，红黑树在哪里？写了3000多字，还没有看到红黑树的影子。张图，请仔细理解：你明白了吗？什么是红黑树？红黑树是2-3-4树！！！OK，本节到此结束。后记本小节，我们一起从二叉树开始，历经二叉搜索树、平衡树、AVL树、2-3树、2-3-4树、B树，最终得到红-blacktree,red黑树的本质是一个2-3-4的树，不同的皮。那么，为什么要构建另一棵红黑树呢？直接用2-3-4树不好吗？本文转载自微信公众号“童哥阅读源码”，可通过以下二维码关注。转载本文请联系童哥阅读源码公众号。
