Tree

红黑树

January 11, 2022
Tree, Red-Black-Tree
Data-Struct

树,保持高效在于平衡,高度低。 红黑树如何做到的呢? 定义 # wiki # 红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明,被称为"对称二叉B树",它现代的名字源于Leo J. Guibas和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在O(log n)时间内完成查找、插入和删除,这里的n是树中元素的数目。 性质 # 红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求: 节点是红色或黑色。 根是黑色。 所有叶子都是黑色(叶子是NIL节点)。 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。) 从**任一节点到其每个叶子**的所有简单路径都包含**相同数目的黑色节点**。 一句话概况:或红或黑,首尾皆黑,红子必黑,任一点至所有尾含黑同数。 为确保任一点至所有尾含黑同数,路径中必须插入红点,而在哪个位置插呢(必须考虑红子必黑原则)? 这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。 要知道为什么这些性质确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。 在很多树数据结构的表示中,一个节点有可能只有一个子节点,而叶子节点包含数据。用这种范例表示红黑树是可能的,但是这会改变一些性质并使算法复杂。为此,本文中我们使用"nil叶子"或"空(null)叶子",如上图所示,它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略,导致了这些树好像同上述原则相矛盾,而实际上不是这样。与此有关的结论是所有节点都有两个子节点,尽管其中的一个或两个可能是空叶子。 实现 # 操作 # 因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为O(log n)次。 我们首先以二叉查找树的方法增加节点并标记它为红色。(如果设为黑色,就会导致根到叶子的路径上有一条路上,多一个额外的黑节点,这个是很难调整的。但是设为红色节点后,可能会导致出现两个连续红色节点的冲突,那么可以通过**颜色调换(color flips)和 树旋转**来调整。) 树旋转 # 对二叉树的一种操作,不影响元素的顺序,但会改变树的结构,将一个节点上移、一个节点下移。树旋转会改变树的形状,因此常被用来将较小的子树下移、较大的子树上移,从而降低树的高度、提升许多树操作的效率。 对一棵树进行旋转时,这棵树的根节点是被旋转的两棵子树的父节点,称为旋转时的根(英语:root);如果节点在旋转后会成为新的父节点,则该节点为旋转时的转轴(英语:pivot)。 上图中,树的右旋操作以 Q 为根、P 为转轴,会将树顺时针旋转。相应的逆操作为左旋,会以 Q 为转轴,将树逆时针旋转。 理解树旋转过程的关键,在于理解其中不变的约束。旋转操作不会导致叶节点顺序的改变(可以理解为旋转操作前后,树的中序遍历结果是一致的),旋转过程中也始终受二叉搜索树的主要性质约束:右子节点比父节点大、左子节点比父节点小。尤其需要注意的是,进行右旋转时,旋转前根的左节点的右节点(例如上图中以 Q 为根的 B 节点)会变成根的左节点,根本身则在旋转后会变成新的根的右节点,而在这一过程中,整棵树一直遵守着前面提到的几个约束。相反的左旋转操作亦然。 如果将根记为 Root、转轴记为 Pivot、子节点中与旋转方向相同的一侧记为 RS(旋转侧,英语:Rotation Side)、旋转对侧记为 OS(英语:Opposite Side),则上图中 Q 节点的 RS 为 C、OS 为 P,将其右旋转的伪代码为: Pivot = Root.OS Root.OS = Pivot.RS Pivot.RS = Root Root = Pivot 该操作为常数时间复杂度。 ...