一.二叉排序树
二叉排序树的定义是任意一个父节点的值，大于其左子树节点的值，小于其右子树节点的值。
以下是两个例子：
（1）数组：5,3,1,4,8,9,7
它的二叉排序树是这样的：
它的时间复杂度是O(logn)。
（2）数组：1,2,3
它的二叉排序树是这样的：
它的时间复杂度是O(n)。
由此可见，两种情况下的二叉排序树的时间复杂度不同，因此，二叉排序树是不稳定的。
当树的结构完全平衡时（如红黑树），节点数 n 与高度 h 的关系为h = logn。此时核心操作的时间复杂度为O(log n)，这是二叉排序树的最优性能。
当节点按升序或降序插入时，二叉排序树会退化为一条单链（每个节点只有左子树或只有右子树）。此时树的高度h = n，核心操作的时间复杂度退化为O(n)。
为了解决这种不平衡的现象，引入了一种更先进的树，名为平衡二叉树。
二.平衡二叉树
平衡二叉树在排序二叉树的基础上，要求左右子树高度差的绝对值不能超过 1（小于等于 1）。
如果这个树不平衡了，我们应该怎么调节？于是引入了4种平衡化调整策略。
（1）LL型
这是调节前的树：
这是调节后的树：
技巧：让不平衡节点朝着造成不平衡的节点走两步，盯着不平衡主链，让中间节点成为新的父节点，其余节点按照顺序进行插入。
（2）RR型
这是调节前的树：
这是调节后的树：
整体方法和LL型类似。
（3）LR型
这是调节前的树：
这是调节后的树：
技巧：
还是先让不平衡节点朝着造成不平衡的节点走两步，
然后盯着不平衡主链，采用两步旋转法：
第一步：后二整体旋转（把造成不平衡的点和它的父节点调换顺序，并变成LL/RR型）
第二步：采用LL/RR旋转
（4）RL型
这是调节前的树：
后二整体旋转之后的树：
这是调节后的树：
整体和LR型类似。
其实，平衡二叉树也是有缺点的，它过分追求时间复杂度的完美，导致旋转过程会消耗大量的计算机资源。
于是引入了一个性能更好的树，名为红黑树。
三.红黑树
在介绍红黑树之前，要先了解一下2-3-4树（4阶B树），因为2-3-4树与红黑树是等价的数据结构，它们之间可以相互转换。
（1）2-3-4树的特点与插入操作
2-3-4树每种节点的结构：
特性：每个节点的关键字都是有序排列的，且左子树的所有关键字小于根节点关键字，右子树的所有关键字大于根节点关键字。所有叶子节点都在同一层，保证了树的高度平衡。
插入操作：首先从根节点开始查找插入位置，找到合适的叶子节点后插入新关键字。如果插入后该节点的关键字数量超过 3 个（即成为 4 - 节点），则需要进行分裂操作。将 4 - 节点中间的关键字提升到父节点，左右两边的关键字分别形成两个新节点。如果父节点也因此变得满了（成为 4 - 节点），则需要递归地对父节点进行分裂操作。
（2）2-3-4树到红黑树的转换
首先我们先了解一下2-3-4树与红黑树各种节点的对应样式：
下图是一个2-3-4树：
然后找到各节点对应的红黑树样式，2节点对应一个黑节点，3节点对应父节点是黑节点，下面接一个红结点，4节点对应父节点是黑节点，下面左右节点都是红结点。
调整好之后如下图所示：
（每个最下方的节点下面都有一个黑色的叶子结点，图中没有画出来）
（3）红黑树的特点
1.红黑树的节点颜色不是红色就是黑色的。
2.根节点一定是黑色的。
3.叶子节点也是黑色的（上面那张图每个最下方的节点下面都有一个黑色的叶子结点，图中没有画出来）。
4.如果一个节点是红色的，那么他的子节点一定是黑色的。
5.从根节点出发到任意的一个叶子节点，所走过的路径上黑色节点的数目是相同的。
从特点中还可以得出一个结论：红黑树当中最长的链条不会超过最短链条的 2 倍。
