什么是红黑树
发表于：2024-11-25 作者：热门IT资讯网编辑
编辑最后更新 2024年11月25日，这篇文章主要介绍"什么是红黑树"的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇"什么是红黑树"文章能帮助大家解决问题。为什么要有红黑树想必大家对二叉树搜索树都不陌
这篇文章主要介绍"什么是红黑树"的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇"什么是红黑树"文章能帮助大家解决问题。
为什么要有红黑树
想必大家对二叉树搜索树都不陌生，首先看一下二叉搜索树的定义：
二叉搜索树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
从理论上来说，二叉搜索树的查询、插入和删除一个节点的时间复杂度均为O（log(n)）,已经完全可以满足我们的要求了，那么为什么还要有红黑树呢？
我们来看一个例子，向二叉搜索树中依次插入（1，2，3，4，5，6），插入之后是这样的
平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
还是刚刚的例子，假如我们用平衡二叉树来实现的话，插入完元素后应该是下面这样的（不唯一）
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须除了满足二叉搜索树的性质外，还要满足下面的性质：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
这就是红黑树的五条性质。我相信很多人都看到过，能背下来的也不在少数，但是真正理解为什么要这样定义的恐怕就不多了。下面就从2-3树的角度来谈谈红黑树的定义。
从2-3树来看红黑树
一般我们接触最多的是二叉树，也就是一个父节点最多有两个子节点。2-3树与二叉树的不同之处在于，一个父节点可以有两个子节点，也可以有三个子节点，并且其也满足类似二叉搜索树的性质。还有最重要的，2-3树的所有叶子节点都在同一层，且最后一层不能有空节点，类似于满二叉树。
我们依次插入10，9，8，7，6，5，4，3，2，1来看一下2-3数是如何进行自平衡的。
2-3树在插入元素之前首先要进行一次未命中的查找，然后将元素插入叶子节点中，之后再进行平衡操作，下面具体说明。
首先插入10，如下图
然后插入9，9小于10，2-3树在插入时要将9融入10这个叶子节点中（当然也是根节点），融合完成后如下：
这是一个3节点，不用执行平衡操作。2-3树中把有两个元素，三个子节点的节点称为3节点，把有一个元素，两个子节点的的节点称为2节点。
接着插入8，插入8的时候同样要先融入叶子节点中，如下图左侧所示
8融入叶子节点后，该结点便拥有了3个元素，不满足2-3树的定义，这时就要把3节点进行分裂，即把左侧和右侧的元素分裂为2节点，而中间的元素抽出，继续融入其父节点，在这里便成为了一个根节点。
继续插入7，如下
接着插入6，还是首先找到叶子节点，然后将其融入，如下图左侧所示
接着插入5，如下图所示，同样不需要进行平衡操作
接着插入3，3融入4所在的叶子节点中，不需要进行平衡操作
最后插入2，同样先找到叶子节点，然后将其融入，如下图所示
再看红黑树
那么红黑树与2-3树有什么关系呢？现在我们对2-3树进行改造，改造成一个二叉树。怎么改造呢？对于2节点，保持不变；对于3节点，我们首先将3节点中左侧的元素标记为红色，如下图2所示。
下面我们回过头再看下红黑树的五条性质。
2-3树中存在2节点和3节点，3节点中左侧的元素便是红色节点，而其他的节点便是黑色节点。
性质2：根节点是黑色。
在2-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树中的绝对平衡，在红黑树中自然就是任意一结点到每个叶子结点的路径都包含数量相同的黑结点了。
相信大家现在已经对红黑树的五条性质有了更加深刻的体会了。那么我们再看下红黑树维持平衡的三种操作，即变色、左旋、右旋怎么理解呢？
首先看一下 变色，以下图为例，
对应到红黑树中就是，首先插入节点3，在红黑树中新插入的节点默认为红色，然后不满足定义，所以需要进行分解，分解后各个节点都为2节点，所以变为黑色。而2节点需要继续向上融合，故要变成红色。
接着看一下 右旋转，以下图为例，
接着看一下 左旋转，与右旋转类似，以下图为例，
关于"什么是红黑树"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注行业资讯频道，小编每天都会为大家更新不同的知识点。