下一轮人工智能革命

【红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡】

5.不会有连续的红色节点

【2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点】

相信在你的视角中，红黑树已经不再是这五条僵硬的定义了，它背后正浮现着一颗2-3树概念模型。虽然你已经有了这样的认识，但是红黑树作为真正的实现模型，我们还是要回到这个实现本身来探究它的一系列操作。在开始前，我准备了两个基础知识，希望能帮助到你。

1.作为二叉查找树

二叉查找树的节点有一个元素X和两个指针域，左指针指向小于X的元素，右指针指向大于X的元素。

假设我们的插入序列是1~10，那么这颗树会演变成只有右链接的形式，树高会增加到10层，这个时候已经不具备O(LogN)的查找时间复杂度，因为这颗树退化成了链表。

因此对二叉树进行平衡调整是很重要的一个环节，无论是AVL还是红黑树，它们本质上都是希望尽可能保证这颗二叉查找树中的元素尽量均衡的分布在树的两侧。

当我们向一颗二叉查找树中插入一个元素Y的时候，我们会一直与树中的节点进行大小比较，如果Y小于当前元素，就往左走，如果Y大于当前元素，就往右走，直到达到叶子节点，这个时候我们可以把Y插入这颗二叉查找树了。

由于这次的插入动作，整棵树可能会发生一些不平衡，因此我们需要在插入后进行一次平衡调整，使得整棵树恢复到平衡的状态(具体如何调整，要看树是AVL还是红黑树亦或是其他的平衡树)。

二叉查找树的删除是一个很有意思的问题，不同于插入的是，待删除的元素并不能保证一定出现在树中的叶子节点。这将带来一个棘手的情景，即我们需要从树的中间部分取走一个元素，而且在取走后还需要经过调整来使得整颗树满足平衡的性质。从树的中间部分直接取走一个节点的场景实在是太多，也牵扯到了太多相关的节点，这种操作很难实现。

好在有人提出了一个观点，我们对查找树中一个节点的删除，其实可以不必真的改动这个节点的位置。由于查找树的特殊性质，将某个元素节点删除后，它有两个最佳替代者，分别是有序序列中的前驱元素和后继元素。

我们还是以一个包含元素1~10的二叉查找树为例，如果我们希望删除5所在的节点，那么让4或者6替代它的位置都是可行的。作为前驱元素的4，会存放在5所在节点的左子树的最右侧;作为后继元素的6，会存放在5所在节点的右子树的最左侧。

关于这个结论，大家只需稍加思索便可以明白。

现在我们又让问题简化了，也就是说，删除某个节点的时候，我们先找到它的前驱元素或者后继元素(随便选一个)，将它的前驱元素直接填到待删除的节点，然后再把它的前驱元素或者后继元素删除。

这个时候问题就转化成了在二叉查找树中删除一个没有左子树的节点(或者是一个没有右子树的节点)，我们只需要将这个节点删除再进行对应的平衡调整即可(虽然还是需要调平，但是比直接在树中层删除一个同时具备左右儿子的节点要容易很多)。

注意，此处并没有强调是针对红黑树的操作，因为红黑树和AVL都是二叉查找树，它们都适用这个方法。

介绍一下树的旋转

为了调平一颗二叉树，使得其左右节点数目分布均匀，通常会选择旋转的手段。你可以把一颗二叉树某节点的左右子树想象成天平上待称量的物品，如果哪边重了，我们就从重的那边拿出一部分，加到轻的那边，以此保持相对的平均。

在二叉树中这种调整的操作就是旋转，下面给出了两个示例，希望大家能够仔细探究，旋转是二叉树调平的精髓。

介绍一下树的旋转

（编辑：鹰潭站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!