首页 » 技术分享 » 红黑树之旅 | 120+个图解过程

红黑树之旅 | 120+个图解过程

 
  • 本篇红黑树文章,近120多幅图构成,让你了解红黑树不再难。

  • 发表是最好的记忆 --候捷

目录:

  1. 红黑树介绍

  2. 旋转分析

  3. 插入分析

  4. 删除分析

  5. 完整实例宏微观图解过程

        5.1 插入宏微观图解过程

        5.2 删除宏微观图解过程

  1. 代码实现分析

  2. 分析过程附件

先看下《算法导论》对RBTree的介绍:

红黑树,一种二叉查找树,但在每个节点上增加一个存储位表示节点的颜色,可以是Red或Black。


通过对任何一条从根到叶子的路径上各个节点着色方式的限制,红黑树确保没有1条路径会比其它路径长出2倍,因而是接近平衡的。

 

下面,在具体介绍红黑树之前,我们先来简单了解下,二叉查找树的一般性质:

(1)在一棵二叉查找树上,执行查找、插入、删除等操作的时间复杂度为O(logN); 因为,一棵由n个节点,随机构造的二叉查找树的高度为logN, 所以顺理成章,一般操作的执行时间O(logN);

         至于n个节点的二叉树高度为logN的证明,可参考《算法导论》

(2)但若是一棵具有n个节点的线性链,则这些操作最坏情况运行时间为O(n);

 

而红黑树,能保证在最坏情况下,基本的动态操作的时间均O(logN);

我们知道,红黑树上每个节点内含有5个域,color, key, left, right, p。 如果相应的指针域没有,则设为NIL。

一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:

  1. 每个节点要么是红,要么是黑色;

  2. 根节点是黑色;

  3. 每个叶节点,即空节点(NIL)是黑色;

  4. 如果一个节点是红色,那么它的2个孩子节点必为黑色;

  5. 对于每个节点,从该节点到其子孙的叶子节点的路径上包含相同数目的黑色节点;

下图所示,即是一颗红黑树:

左旋与右旋

为什么要左旋右旋?

因为红黑树插入或删除节点后,树的结构发生了 变化,从而可能破坏红黑树的性质。为了维持插入或删除节点后的树,仍然是一棵红黑树,所以有必要对树的结构做部分调整,从而恢复红黑树的原本性质。而为了恢复红黑树性质而作的动作包括节点颜色的改变(重新着色),和节点的调整。

这部分节点调整工作,改变指针结构,即是通过左旋或右旋而达到目的。

从而使插入或删除节点的树重新成为一棵新的红黑树。

请看下图:

左旋代码实现,分三步:



右旋代码类似,可自行对比类比分析。


转载自原文链接, 如需删除请联系管理员。

原文链接:红黑树之旅 | 120+个图解过程,转载请注明来源!

0