二叉搜索树的搜索复杂度为O(h),h是树的高度,它的缺点就是我们无法保证树的高度,当树的高度较高时,搜索时间会增大.

红黑树是满足一些特殊性质的二叉搜索树,能保证树的高度h \leq 2 \lg ( n + 1 ),即在最坏的情况下时间复杂度为O(\lg n)

红黑树的性质

红黑树是满足如下性质的二叉搜索树:

  1. 每个结点或是红色的,或是黑色的.
  2. 根节点是黑色的.
  3. 每个叶结点(None)是黑色的.
  4. 如果一个结点是红色的,则它的两个子结点都是黑色的(也就是说不存在两个连续的红色节点).
  5. 对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点.

image.png

正是由于这些条件的限制,红黑树最长路径不会超过最短路径的2倍.当某条路径最短时,这条路径必然都是由黑色节点构成。当某条路径长度最长时,这条路径必然是由红色和黑色节点相间构成(性质4限定了不能出现两个连续的红色节点)。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时,在路径最长的情况下,路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量,也就是最短路径长度的2倍。

红黑树的黑高

从某个结点出发到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高,记为bh(x).黑高有一些有趣的性质:

  • 从结点x到叶节点所有路径的黑高都是相同的
  • 以x为根结点的树至少包含2^{bh(x)}-1个内部结点.

红黑树的性能

根据黑高的性质有节点个数n与黑高的关系:

n \geq 2^{bh(x)}-1

根据红黑树的性质4,可知从根到叶任何一条路径上至少有一半结点是黑色的,因此若树高为h,则黑高至少为h/2,即:

n \geq 2^{h/2}-1

两边取对数得:

h \leq 2 \lg ( n + 1 )

二叉搜索树的搜索复杂度为O(h),所以红黑树的最坏情况下复杂度为O(\lg n).

图解红黑树

红黑树这些优良的性质都是在插入的时候维护的,不过维护这些性质做出的调整比较复杂,因为情况非常多,本文就不详细列举每种情况了,我们用一个例子来理解一下红黑树相对二叉搜索树的不同.

假设初始的二叉查找树只有三个节点,根节点值为9,左孩子值为8,右孩子值为12:
image.png
接下来我们依次插入如下五个节点:7,6,5,4,3。依照二叉查找树的特性,结果会变成什么样呢?
image.png

同样的情况,来看一下在红黑树中会有怎样的变化(这里省略了叶节点):

image.png

现在来插入节点,思考一下我们要插入的下一个是黑色的还是红色的呢?如果插入的是黑色节点时,则每次插入都会违返性质5, 每次都需要调整结构。如果插入的节点是红色,仅出现两个连续的红色节点的情况需要调整结构.所以每次插入的新节点一定是红色的.

现在来插入节点7,很不幸,有两个连续的红色节点,违法性质4,需要变色:
image.png

插入节点6,又出现两个连续的红色节点,把父节点变成黑色节点,把祖父节点变成红色节点,同时反向旋转祖父节点:
image.png

插入节点5,需要变色:
image.png

插入节点4,变色并右旋:
image.png

增加节点3,变色一次后发现还有两个连续红色节点,接着变色与旋转:
image.png

从最终效果看红黑树的性质完美的控制住了树的野蛮生长.


参考:
https://blog.csdn.net/net_wolf_007/article/details/79706498
http://files.cnblogs.com/files/bbvi/RedBlackBinaryTree.rar

posted @ 2019-02-11 11:22:53
评论加载中...

发表评论