红黑树

✍ dations ◷ 2025-08-07 22:02:02 #数据结构,树结构,B树

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 ${\text{O}}(\log n)$ 属性的二叉查找树，颜色为或。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

下面是一个具体的红黑树的图例：

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些性质并使算法复杂。为此，本文中我们使用"nil叶子"或"空（null）叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量（ ${\text{O}}(\log n)$ 来指一个节点的父节点的兄弟节点。注意：

在下面的示意图中，将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U。在图中展示的任何颜色要么是由它所处情形这些所作的假定，要么是假定所暗含（imply）的。

对于每一种情形，我们将使用C示例代码来展示。通过下列函数，可以找到一个节点的叔父和祖父节点：

 node* grandparent(node *n){     return n->parent->parent; } node* uncle(node *n){     if(n->parent == grandparent(n)->left)         return grandparent (n)->right;     else         return grandparent (n)->left; }

情形1:新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合。

 void insert_case1(node *n){     if(n->parent == NULL)         n->color = BLACK;     else         insert_case2 (n); }

情形2:新节点的父节点P是黑色，所以性质4没有失效（新节点是红色的）。在这种情形下，树仍是有效的。性质5也未受到威胁，尽管新节点N有两个黑色叶子子节点；但由于新节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。

 void insert_case2(node *n){     if(n->parent->color == BLACK)         return; /* 树仍旧有效*/     else         insert_case3 (n); }

注意：在下列情形下我们假定新节点的父节点为红色，所以它有祖父节点；因为如果父节点是根节点，那父节点就应当是黑色。所以新节点总有一个叔父节点，尽管在情形4和5下它可能是叶子节点。

情形3:如果父节点P和叔父节点U二者都是红色，（此时新插入节点N做为P的左子节点或右子节点都属于情形3，这里右图仅显示N做为P左子的情形）则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色（用来保持性质5）。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G可能是根节点，这就违反了性质2，也有可能祖父节点G的父节点是红色的，这就违反了性质4。为了解决这个问题，我们在祖父节点G上递归地进行情形1的整个过程。（把G当成是新加入的节点进行各种情形的检查）

void insert_case3(node *n){ if(uncle(n) != NULL && uncle (n)->color == RED) { n->parent->color = BLACK; uncle (n)->color = BLACK; grandparent (n)->color = RED; insert_case1(grandparent(n)); } else insert_case4 (n); }

void insert_case4(node *n){ if(n == n->parent->right && n->parent == grandparent(n)->left) { rotate_left(n); n = n->left; } else if(n == n->parent->left && n->parent == grandparent(n)->right) { rotate_right(n); n = n->right; } insert_case5 (n); }

voiddelete_one_child(struct node *n){ /* * Precondition: n has at most one non-null child. */ struct node *child = is_leaf(n->right)? n->left : n->right; replace_node(n, child); if(n->color == BLACK){ if(child->color == RED) child->color = BLACK; else delete_case1 (child); } free (n);}

voiddelete_case2(struct node *n){ struct node *s = sibling (n); if(s->color == RED){ n->parent->color = RED; s->color = BLACK; if(n == n->parent->left) rotate_left(n->parent); else rotate_right(n->parent); } delete_case3 (n);}

voiddelete_case3(struct node *n){ struct node *s = sibling (n); if((n->parent->color == BLACK)&&(s->color == BLACK)&&(s->left->color == BLACK)&&(s->right->color == BLACK)) { s->color = RED; delete_case1(n->parent); } else delete_case4 (n);}

红黑树

相关