本篇红黑树文章,近120多幅图构成,让你了解红黑树不再难。
发表是最好的记忆 --候捷
目录:
红黑树介绍
旋转分析
插入分析
删除分析
完整实例宏微观图解过程
5.1 插入宏微观图解过程
5.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。
一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:
-
每个节点要么是红,要么是黑色;
-
根节点是黑色;
-
每个叶节点,即空节点(NIL)是黑色;
-
如果一个节点是红色,那么它的2个孩子节点必为黑色;
-
对于每个节点,从该节点到其子孙的叶子节点的路径上包含相同数目的黑色节点;
下图所示,即是一颗红黑树:
左旋与右旋
为什么要左旋右旋?
因为红黑树插入或删除节点后,树的结构发生了 变化,从而可能破坏红黑树的性质。为了维持插入或删除节点后的树,仍然是一棵红黑树,所以有必要对树的结构做部分调整,从而恢复红黑树的原本性质。而为了恢复红黑树性质而作的动作包括节点颜色的改变(重新着色),和节点的调整。
这部分节点调整工作,改变指针结构,即是通过左旋或右旋而达到目的。
从而使插入或删除节点的树重新成为一棵新的红黑树。
请看下图:
左旋代码实现,分三步:
右旋代码类似,可自行对比类比分析。