数据结构之红黑树
1. 简介
红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树( 树),因此,红黑树在很多地方都有应用。在 中,很多部分目前
包括 应用了红黑树的变体 中的红黑树有一些变化,这些修改提供了更好的性能,以及对 操作的支持。它是
复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的它可以在 时间内做查找,插入和删除等操作。
本文介绍了红黑树的基本性质和基本操作。
2. 红黑树的性质
红黑树,顾名思义,通过红黑两种颜色域保证树的高度近似平衡。它的每个节点是一个五元组:(颜色),(数据), (左孩子),
!(右孩子)和 (父节点)。
红黑树的定义也是它的性质,有以下五条:
性质 "#节点是红色或黑色
性质 $#根是黑色
性质 %#所有叶子都是黑色(叶子是 & 节点)
性质 '#如果一个节点是红的,则它的两个儿子都是黑的
性质 (#从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。
这五个性质强制了红黑树的关键性质从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。为什么呢?性质 ' 暗示着任何一个简单路径上
不能有两个毗连的红色节点,这样,最短的可能路径全是黑色节点,最长的可能路径有交替的红色和黑色节点。同时根据性质 ( 知道:所有最长的路径都有
相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。
3. 红黑树的基本操作
因为红黑树也是二叉查找树,因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。然而,红黑树上的插入操作和删除操作会导致不再符合
红黑树的性质。恢复红黑树的性质需要少量的颜色变更实际是非常快速的和不超过三次树旋转对于插入操作是两次。虽然插入和删除很复杂,
但操作时间仍可以保持为 次。
3.1 插入操作
插入操作可以概括为以下几个步骤:
"查找要插入的位置,时间复杂度为:&
$将新节点的 赋为红色
%自下而上重新调整该树为红黑树
其中,第"步的查找方法跟普通二叉查找树一样,第$步之所以将新插入的节点的颜色赋为红色,是因为:如果设为黑色,就会导致根到叶子的路
径上有一条路上,多一个额外的黑节点,这个是很难调整的。但是设为红色节点后,可能会导致出现两个连续红色节点的冲突,那么可以通过颜色调换
())和树旋转来调整,这样简单多了。下面讨论步骤%的一些细节:
设要插入的节点为 &,其父节点为 *,其父亲 的兄弟节点为 +(即 * 和 + 是同一个节点的两个子节点)。
,"-如果 * 是黑色的,则整棵树不必调整便是红黑树。
,$-如果 * 是红色的(可知,其父节点 一定是黑色的),则插入 . 后,违背了性质 ',需要进行调整。调整分以下 % 种情况:
(a)N 的叔叔 U 是红色的
如上图所示,我们将 * 和 + 重绘为黑色并重绘节点 为红色用来保持性质 (。现在新节点 & 有了一个黑色的父节点 *,因为通过父节点 * 或叔父节
点 + 的任何路径都必定通过祖父节点 ,在这些路径上的黑节点数目没有改变。但是,红色的祖父节点 的父节点也有可能是红色的,这就违反了性质 '。
为了解决这个问题,我们在祖父节点 上递归调整颜色。
(b)N 的叔叔 U 是黑色的,且 N 是右孩子
如上图所示,对 * 进行一次左旋转调换新节点和其父节点的角色/接着,按情形处理以前的父节点 * 以解决仍然失效的性质 '。
(c)N 的叔叔 U 是黑色的,且 N 是左孩子
评论2