红黑树中nil结点_什么是红黑树？看完这篇你就明白了！
Java技术栈
关注阅读更多优质文章
为什么要有红黑树
一般人都对binary search tree有一定的了解。
让我们先了解一下binary search tree的基本定义：
Binary Search Tree（BST）要么是空的状态，
要么满足以下性质：
如果左子tree不为空，
则其所有节点数值都小于root node数值；
如果右子tree不为空，
则其所有节点数值都大于root node数值；
而左右subtrees同样也是 BST。
从理论上讲，
binary search tree在查询、插入和删除操作上的时间复杂度均为O(\log n)，
这意味着它已经能够很好地满足大多数需求。
那么为什么要引入red-black trees呢？
举个例子，
如果我们依次向 BST 中插入数字序列(1,2,3,4,5,6)，
最终会得到怎样的结构？
退化成链表的二叉搜索树
可以看出，在此情形下
平衡二叉树(Balanced Binary Tree)具备以下特征：其要么为空树，要么其左右子树的高度差绝对值不超过1，并且左右子树各自均为平衡二叉树。
仍然基于上文中的示例，在这种情况下如果我们采用平衡二叉树结构来实现，则插入操作完成后数据结构会呈现如下形式（其形式并非单一）
自平衡的二叉树
在最差情况下
然而这就带来了另一个问题。那就是在插入或删除任何一个元素后，并非像人们想象中那样容易就能保证整个数据结构的高度保持稳定和均衡状态。实际上，在这种情况下我们必须采取一系列复杂的操作来维持其高度的最佳状态，并且这些操作往往会导致较高的时间和空间复杂度消耗
二叉搜索树可能退化为链表形式，在这种情况下虽然能够实现快速查找功能但在极端数据分布下可能导致性能严重下降
没错，这就是我们要谈的红黑树了。首先看一下红黑树的定义：
红黑树基于包含红黑结点且能够自我平衡的二叉查找树。它需具备除了二叉搜索树的基本性质之外还需要额外满足以下特性：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点必为黑色。
性质3：所有叶子节点（NIL）均需为黑色。
性质4：任何红色节点的儿子必定为黑色。
性质5：任一节点通往所有叶子路径上的黑色数目相同。
这些即是定义红黑树的核心依据。
从2-3树来看红黑树
我们最常接触的就是二叉树这一数据结构类型，在其中每个父节点至多包含两个子节点。相比传统的二叉树结构，在2-3树中同一父节点可能拥有两个或三个子节点，并且它仍然遵循与二叉搜索树相似的组织原则。
特别重要的是，在2-3树中所有叶节点都位于同一层次，并且最后一层不允许出现空缺。这种结构与完美二叉树类似。
我们依次插入10，9，8，7，6，5，4，3，2，1来看一下2-3数是如何进行自平衡的。
在插入新元素之前必须先执行一次无命中状态下的查找操作, 接着将该元素放置于叶子节点位置, 随后需要对整个树结构进行平衡调整, 详细解释这些步骤如下.
首先插入10，如下图
在2-3树结构中进行插入操作时，在已经存在的最大值节点（例如编号为10）附近进行调整；随后尝试插入9号元素；由于该新元素的值低于现有最大值（10），因此在构建过程中会将新元素与现有节点进行整合（因为其值较低）；整合完成后，请参考以下结果示例：
在2-3树结构中进行插入操作时加入元素9。其中属于3节点类型的一种情况是该结点包含两个数据项并且拥有三个子树。此时无需进行平衡调整步骤。而当处理含有一个数据项以及两个子树的情况时则被定义为2型结点。随后，在将8加入树的过程中需要首先处理到叶子层的位置并按照相应的规则进行扩展或更新
2-3树中插入8
当8个元素被插入到叶子节点后, 此时该结点拥有三个子元素, 这违反了二叉树的基本性质, 因此需要将这个三节点进行拆分. 即将左侧和右侧的所有子项分别拆分为两个二叉树节点, 而中间剩余的一个子项则被提取出来, 然后将其余的内容重新注入到父节点中, 在这种情况下就成为了新的根节点.
继续插入7，如下
在2-3树结构中进行7节点的插入操作后，在所有节点上均满足2-3树的基本结构要求。随后尝试插入6号节点时，则会按照以下步骤执行：其流程首先是定位到叶子节点位置，并对其进行整合处理（如图所示左侧部分）。
在2-3树中进行插入操作时，在叶子节点依次插入新元素会导致部分节点超出容量限制的问题。具体来说，在向2-3树中插入6号元素之后，在叶子节点依次出现了编号为6、7、8的三个元素违反了2-3树的基本性质要求。此时需要执行分裂操作：即从该叶子节点中分离出编号为7的元素，并将其值转移至其父节点；然后将剩下的两个较小编号（6号和8号）分别作为左右子节点重新构造该父节点的状态结构。随后继续进行5号元素的插入操作：如图所示的操作流程表明，在处理完前一阶段的问题后，在后续步骤中无需再对数据结构进行平衡调整即可完成整个过程
2-3树中依次插入5和4；而不是先定位到叶子节点，并将它们纳入其中。
在2-3树结构中进行数值4的插入操作后会发现导致数值4、5和6所在的叶子节点违反了2-3树的组织原则因此必须执行分裂操作即将数值5移至其父节点位置而数值4和6则分别作为新的左子节点和右子节点被分离出来这样一来父节点现在拥有数值5、7和9从而又引发了进一步的分裂需求于是将数值7提升为新的根节点并将其左子节点设为5右子节点设为9最后再将数值3整合到其所在子树中这一过程无需进行平衡调整
在2-3树中加入3元素后，请问是先定位叶子节点位置再将其纳入结构吗？如上图左侧所示
在2-3树中进行插入操作时，在叶子节点中找到位置并插入新的元素可能会导致结构不符合定义的情况发生。此时需要执行分裂操作：将被插入的元素移入其父节点，并将被分裂出来的子元素分别作为左子节点和右子节点从父节点分离出来；接着，在完成上述步骤后进行第二次插入操作（如图所示）。
在2-3树中进行一次插入操作 至此之后我们便完成了对序列10 9 8 7 6 5 4 3 2 1依次进行插入操作并且保证了整个数据结构始终保持着高度平衡的状态 这个过程是不是非常令人惊叹呢
再看红黑树
那么红黑树与2-3树之间存在什么联系呢？我们可以将一个2-3树转换为二叉树，并探讨这种变换的意义。具体来说，在这种情况下：对于每个原本是二节点的结构（即有两个子节点）而言无需更改；而对于原本是三节点的结构（即有一个父节点和两个子节点），我们需要将该父节点保留下来，并将其左子节点标记为红色（如图所示）。
将2-3树改造为红黑树的形式；随后我们将此结构转化为图3所示的样子；接着，在中间子节点处设置其父节点为那个红色的父亲；如上文所述，在这种情况下（可能需要进一步说明），我们会将其父设为那个带有红色标记的父亲；最终我们将此结构转换为二叉树形式；看起来是不是挺熟悉的？没错，这就是大名鼎鼎的红黑树啊！下面让我们回顾一下关于红黑树的基本性质。
通过分析2-3树结构理解红黑树本质
通过分析...
2节点与3节点在红黑树中的等价形式
显然，无论是哪种情况，根节点都是黑色的。
性****质3：每个叶子节点(NIL)是黑色。 这里的叶子节点不是指左右子树为空的那个叶子节点，而是指节点不存在子节点或者为空节点被称作叶子节点。在性质2中我们讨论的根节点是黑色的都是讨论根节点不为空的情况，若红黑树是一个空树，那么根节点自然也是空的叶子节点，这时候叶子节点便必然是黑色的。 性质4：每个红色结点的两个子结点一定都是黑色。 还是从2-3树的角度来理解，红色节点对应2-3树中3节点左侧的元素，那么它的子节点要么是2节点，要么是3节点。无论是2节点还是3节点对应的节点颜色都是黑色的，这在性质2时已经讨论了。 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。 性质5应该是红黑树最重要的一条性质了。2-3树是一颗绝对平衡的树，即2-3树中任意一个节点出发，到达叶子节点后所经过的节点数都是一样的。那么对应到红黑树呢？2-3树中2节点对应到红黑树便是一个黑色的节点，而3节点对应到红黑树是一个红色节点和一个黑色节点。所以，无论是2节点还是3节点，在红黑树中都会对应一个黑色节点。那么2-3树中的绝对平衡，在红黑树中自然就是任意一结点到每个叶子结点的路径都包含数量相同的黑结点了。
相信大家现在已经对红黑树的五条性质有了更加深刻的体会了。那么我们再看下红黑树维持平衡的三种操作，即变色、左旋、右旋怎么理解呢？
首先看一下变色 ，以下图为例，
在红黑树中对颜色进行调整时会遇到一些特殊的情况
在插入元素1之后进行右旋操作：首先将2节点与其原有的连接断开，并切除其右子树；随后将被切除的右子树作为新的左子树附加到3节点的左侧；接着调整相关节点的颜色：将2节点着色为原来的3节点颜色，并将3节点着色为原来的2节点颜色。如图所示
在红黑树中进行一次左旋转变换 插入元素3之后的操作如下：随后断开2号节点与其父节点之间的连接关系。接着断开该子节点（假设其父节点为2号）与其原有父指针的关系。随后将该子节点重新挂接到其祖父（即原来的根）右侧的位置。这样操作不会违背二分搜索树的基本性质。接着将祖父（即原来的根）重新挂接到新的孙子（即插入后的那个）左侧的位置。完成以上步骤后还需要对相关指针进行颜色设置：即改变相关父-子指针的颜色设置：具体来说就是将祖父（原根）从原来的红色状态改为黑色状态；并将被插入的新孙子从黑色状态改为红色状态
写在最后
值得强调的是，在文章中所讨论到的一种特殊形式是左倾式红黑树，在这种情况下红色节点总是父节点的左子节点。实际上根据严格的定义标准，并不需要这样的限制条件存在；只要满足构成标准的基本规则即可。例如完全可以通过不同的结构实现右倾式设计等方法来满足同样的基本要求；希望读者在理解时不要产生任何误解或误读的情况
关注Java技术栈看更多干货
戳原文，获取更多福利！