为什么要有红黑树
想必大家对二叉树搜索树都不陌生, 首先看一下二叉搜索树的定义:
二叉搜索树(Binary Search Tree), 或者是一棵空树, 或者是具有下列性质的二叉树: 若它的左子树不空, 则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空, 则右子树上所有结点的值均大于它的根结点的值; 它的左, 右子树也分别为二叉排序树.
从理论上来说, 二叉搜索树的查询, 插入和删除一个节点的时间复杂度均为 O(log(n)), 已经完全可以满足我们的要求了, 那么为什么还要有红黑树呢?
我们来看一个例子, 向二叉搜索树中依次插入(1,2,3,4,5,6), 插入之后是这样的
可以看到, 在这种情况下, 二叉搜索树退化成了链表!!! 这时候查询, 插入和删除一个元素的时候, 时间复杂度变成了 O(n), 显然这是不能接受的. 出现这种情况情况的原因是二叉搜索树没有自平衡的机制, 所以就有了平衡二叉树的概念.
平衡二叉树 (Balanced Binary Tree) 具有以下性质: 它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1, 并且左右两个子树都是一棵平衡二叉树.
还是刚刚的例子, 假如我们用平衡二叉树来实现的话, 插入完元素后应该是下面这样的(不唯一)
平衡二叉树保证了在最差的情况下, 二叉树依然能够保持绝对的平衡, 即左右两个子树的高度差的绝对值不超过 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, 如下
插入后, 各个节点都满足 2-3 树的定义, 不需要进行平衡操作.
接着插入 6, 还是首先找到叶子节点, 然后将其融入, 如下图左侧所示
插入后 6,7,8 三个元素所在的叶子节点不再满足 2-3 树的定义, 需要进行分裂, 即抽出元素 7 融入父节点, 6 和 8 分裂为 7 的左右子节点.
接着插入 5, 如下图所示, 同样不需要进行平衡操作
接着插入 4, 还是首先找到叶子节点, 然后将其融入, 如下图左侧所示
插入后 4,5,6 三个元素所在的叶子节点不再满足 2-3 树的定义, 需要进行分裂, 即抽出元素 5 融入父节点, 4 和 6 分裂为 5 的左右子节点. 5 融入父节点后, 该结点便有了 5,7,9 三个元素, 因而需要继续分裂, 元素 7 成为新的根节点, 5 和 9 成为 7 的左右子节点.
接着插入 3,3 融入 4 所在的叶子节点中, 不需要进行平衡操作
接着插入 2, 还是首先找到叶子节点, 然后将其融入, 如下图左侧所示
插入后 2,3,4 三个元素所在的叶子节点不再满足 2-3 树的定义, 需要进行分裂, 即抽出元素 3 融入父节点, 2 和 4 分裂为 3 的左右子节点, 3 融入 5 所在的父节点中.
最后插入 2, 同样先找到叶子节点, 然后将其融入, 如下图所示
至此, 我们便完成了在 2-3 树中依次插入 10,9,8,7,6,5,4,3,2,1, 并且 2-3 树始终维护着平衡. 怎么样, 是不是很神奇.
再看红黑树
那么红黑树与 2-3 树有什么关系呢? 现在我们对 2-3 树进行改造, 改造成一个二叉树. 怎么改造呢? 对于 2 节点, 保持不变; 对于 3 节点, 我们首先将 3 节点中左侧的元素标记为红色, 如下图 2 所示.
然后我们将其改造成图 3 的形式; 再将 3 节点的位于中间的子节点的父节点设置为父节点中那个红色的节点, 如图 4 的所示; 最后我们将图 4 的形式改为二叉树的样子, 如图 5 所示. 图 5 是不是很熟悉, 没错, 这就是我们常常提到的大名鼎鼎的红黑树了.
下面我们回过头再看下红黑树的五条性质.
性质 1: 每个节点要么是黑色, 要么是红色.
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 树中的绝对平衡, 在红黑树中自然就是任意一结点到每个叶子结点的路径都包含数量相同的黑结点了.
相信大家现在已经对红黑树的五条性质有了更加深刻的体会了. 那么我们再看下红黑树维持平衡的三种操作, 即变色, 左旋, 右旋怎么理解呢?
首先看一下变色, 以下图为例,
在 2-3 树中插入节点 3 后, 便不再满足 2-3 树的定义, 需要进行分解, 将元素 2 抽出作为 1 和 3 的父节点, 然后 2 继续向上融合.
对应到红黑树中就是, 首先插入节点 3, 在红黑树中新插入的节点默认为红色, 然后不满足定义, 所以需要进行分解, 分解后各个节点都为 2 节点, 所以变为黑色. 而 2 节点需要继续向上融合, 故要变成红色.
接着看一下右旋转, 以下图为例,
插入元素 1 后, 进行右旋转操作, 首先把 2 节点与 3 节点断开连接, 同时把 2 与 2 的右子树断开连接, 然后把 2 的右子树连接至 3 的左子树位置, 不会违背二分搜索树的性质, 然后再把 3 连接至 2 的右子树位置. 最后还要改变对应节点的颜色, 即把 2 节点的颜色改为原来 3 节点的黑色, 把 3 节点的颜色改为原来 2 节点的红色.
接着看一下左旋转, 与右旋转类似, 以下图为例,
插入元素 3 后, 进行左旋转操作, 首先把 2 节点与 3 节点断开连接, 同时把 3 与 3 的左子树断开连接, 然后把 3 的左子树连接至 2 的右子树位置, 不会违背二分搜索树的性质, 然后再把 2 连接至 3 的左子树位置. 最后还要改变对应节点的颜色, 即把 2 节点的颜色改为原来 3 节点的红色, 把 3 节点的颜色改为原来 2 节点的黑色.
写在最后
最后需要说的是, 本文中提到的红黑树是一种特殊的红黑树 -- 左倾红黑树, 即红色节点都是父节点的左子树, 其实按照红黑树的定义不必这样. 只要满足红黑树的五条性质, 就是红黑树, 比如完全可以实现右倾红黑树等等, 希望大家不要有误解.
更多关于红黑树的知识, 比如红黑树的插入, 删除操作, 限于篇幅, 本文不再介绍, 有兴趣的还是推荐大家阅读《算法 4》或者《算法导论》.
更多关于算法, 数据机构和计算机基础知识的内容, 欢迎扫码大家关注我的公众号 "超悦编程".
来源: https://www.cnblogs.com/exzlc/p/12203744.html