数据结构：二叉排序树，平衡二叉树，红黑树的介绍

一.二叉排序树

二叉排序树的定义是任意一个父节点的值，大于其左子树节点的值，小于其右子树节点的值。

以下是两个例子：

（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 倍。