文档介绍：记忆过往
总有一个人需要这些知识。本博客信息正在迁往
/
[置顶] 数据结构:红黑树
分类: Algorithms Data structs 2012-10-21 00:38 31358人阅读评论(1) 收藏举报
数据结构nulldeletestructinsert扩展
一、定义
    红黑树是一种特殊的二叉查找树,它的每一个结点都被标记为红色或者黑色。是在计算机
科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的,
他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的
一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效
的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。在C++ STL中,
很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体。
二、性质
    将一棵标准二叉树的所有空指针用外部结点替代,就生成了一棵扩展二叉树。红黑树以扩
展二叉树为基础,又加入了以下性质:
根结点和所有外部结点都是黑色;
所有从根结点至外部结点的路径上,不能包含两个连续的红色结点;
所有从根结点至外部结点的路径上,包含相同数目的黑色结点。
    我们可以把所有指向黑色结点标记为黑色,把所有指向红色结点的指针标记为红色,从而
获得红黑树的一种等价的定义:
从内部结点指向外部结点的指针都为黑色;
所有从根结点到外部结点的路径上,不能包含两个连续的红色指针;
所有从根结点到外部结点的路径上,包含相同数目的黑色指针。
        我们可以根据指针的颜色推断出结点的颜色,反之亦然。这些约束强制了红黑树的关
键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平
衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高
度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

1
三、操作
    因为每一个红黑树也是一个特化的二叉搜索树,因此红黑树上的只读操作与普通二叉搜索
树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。
恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于
插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 。
1、插入
    我们首先以二叉搜索树的方法增加节点并标记它为红色。(如果设为黑色,就会导致根到
叶子的路径上有一条路上,多一个额外的黑节点,这个是很难调整的。但是设为红色节点后,可能
会导致出现两个连续红色节点的冲突,那么可以通过颜色调换(color flips)和树旋转来调
整。) 下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样,我们将使用术
语叔父节点来指一个节点的父节点的兄弟节点。注意:
    性质1 节点是红色或黑色。所有叶子都是黑色。总是保持着。
    性质2 每个红色节点的两个子节点都是黑色。只在增加红色节点、重绘黑色节点为红色,
或做旋转时受到威胁。
    性质3 从每个叶子到根的所有路径都包含相同数目的黑色节点。只在增加黑色节点、重绘
红色节点为黑色,或做旋转时受到威胁。
    在下面的示意图中,将要插入的节点标为N,N的父节点标为P,N的祖父节点标为G,N的叔
父节点标为U。在图中展示的任何颜色要么是由它所处情形所作的假定,要么是这些假定所暗含
的。
情形1: 新节点N位于树的根上,没有父节点。在这种情形下,我们把它重绘为黑色以满足性质1 根
是黑色。因为它在每个路径上对黑节点数目增加一,性质3符合。
情形2: 新节点的父节点P是黑色,所以性质2没有失效(新节点是红色的)。在这种情形下,树仍
是有效的。性质3受到威胁,因为新节点N有两个黑色叶子儿子;但是由于新节点N是红色,通过它
的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点,所以这个性
质依然满足。
2
注意: 在下列情形下我们假定新节点有祖父节点,因为父节点是红色;并且如果它是
根,它就应当是黑色。所以新节点总有一个叔父节点,尽管在情形4和5下它可能是叶子。
情形3: 如果父节点P和叔父节点U二者都是红
色,则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质3)