登录 注册
首页 >

红黑树

✍ dations ◷ 2024-12-23 04:54:43 #数据结构,树结构,B树

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

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

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

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

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

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量（ O ( log ⁡ n ) {\displaystyle {\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); }

注意：在余下的情形下，我们假定父节点P是其祖父G的左子节点。如果它是右子节点，情形4和情形5中的和应当对调。

情形4:父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色;接着，我们按情形5处理以前的父节点P以解决仍然失效的性质4。注意这个改变会导致某些路径通过它们以前不通过的新节点N（比如图中1号叶子节点）或不通过节点P（比如图中3号叶子节点），但由于这两个节点都是红色的，所以性质5仍有效。

 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);}

如果N和它初始的父亲是黑色，则删除它的父亲导致通过N的路径都比不通过它的路径少了一个黑色节点。因为这违反了性质5，树需要被重新平衡。有几种情形需要考虑：

情形1: N是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。

voiddelete_case1(struct node *n){        if(n->parent != NULL)                delete_case2 (n);}

注意：在情形2、5和6下，我们假定N是它父亲的左儿子。如果它是右儿子，则在这些情形下的和应当对调。

情形2： S是红色。在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），所以我们可以接下去按情形4、情形5或情形6来处理。

（注意：这里的图中没有显示出来，N是删除了黑色节点后替换上来的子节点，所以这个过程中由P->X->N变成了P->N，实际上是少了一个黑色节点，也可以理解为Parent(Black)和Silbing(Red)那么他们的孩子黑色节点的数目肯定不等，让他们做新兄弟肯定是不平衡的，还需后面继续处理。这里看英文版本的比较的明了）

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);}
通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。

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);}
个内部节点的红黑树的高度是 O ( log ⁡ n ) {\displaystyle {\text{O}}(\log n)} 。

定义：

引理：以节点 v {\displaystyle v} 为根的子树有至少 2 b h ( v ) − 1 {\displaystyle 2^{bh(v)}-1} 个内部节点。

引理的证明（通过归纳高度）：

基础： h ( v ) = 0 {\displaystyle h(v)=0}

如果 v {\displaystyle v} 的高度是零则它必定是NIL，因此 b h ( v ) = 0 {\displaystyle bh(v)=0} 。所以：

2 b h ( v ) − 1 = 2 0 − 1 = 1 − 1 = 0 {\displaystyle 2^{bh(v)}-1=2^{0}-1=1-1=0}

归纳假设： h ( v ) = k {\displaystyle h(v)=k} 的 v {\displaystyle v} 有 2 b h ( v ) − 1 − 1 {\displaystyle 2^{bh(v)-1}-1} 个内部节点暗示了h( v ′ {\displaystyle v'} ) = k+1的 v ′ {\displaystyle v'} 有 2 b h ( v ′ ) − 1 {\displaystyle 2^{bh(v')}-1} 个内部节点。

因为 v ′ {\displaystyle v'} 有h( v ′ {\displaystyle v'} )> 0所以它是个内部节点。同样的它有黑色高度要么是bh( v ′ {\displaystyle v'} )要么是bh( v ′ {\displaystyle v'} )-1（依据 v ′ {\displaystyle v'} 是红色还是黑色）的两个儿子。通过归纳假设每个儿子都有至少 2 b h ( v ′ ) − 1 − 1 {\displaystyle 2^{bh(v')-1}-1} 个内部接点，所以 v ′ {\displaystyle v'} 有：

2 b h ( v ′ ) − 1 − 1 + 2 b h ( v ′ ) − 1 − 1 + 1 = 2 b h ( v ′ ) − 1 {\displaystyle 2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1}

个内部节点。

使用这个引理我们现在可以展示出树的高度是对数性的。因为在从根到叶子的任何路径上至少有一半的节点是黑色（根据红黑树性质4），根的黑色高度至少是 h ( r o o t ) 2 {\displaystyle {\frac {h(root)}{2}}} 。通过引理我们得到：

n ⩾ 2 h ( r o o t ) 2 − 1 ↔ log ⁡ ( n + 1 ) ⩾ h ( r o o t ) 2 ↔ h ( r o o t ) ⩽ 2 log ⁡ ( n + 1 ) {\displaystyle n\geqslant 2^{\frac {h(root)}{2}}-1\leftrightarrow \;\log {(n+1)}\geqslant {\frac {h(root)}{2}}\leftrightarrow \;h(root)\leqslant 2\log {(n+1)}}

因此根的高度是 O ( log ⁡ n ) {\displaystyle {\text{O}}(\log n)} 。

相关

  • 肺动脉高血压肺高压又称肺动脉高压（Pulmonary hypertension，简称PH或PHTN），是描述肺循环内的压力升高的情形。肺高压会造成呼吸困难、晕眩、昏厥、下肢水肿，肺高压患者会因为心脏负荷增加令运
  • 过滤作用肾功能（Renal function）是描述肾脏状态及其在肾生理作用的角色。肾小球滤过率（Glomerular filtration rate/GFR、肾丝球滤过率）描述了通过肾脏过滤流体之流速。肌酸酐清除率（Crea
  • 堂兄堂亲是指跟自己父亲有血缘关系的同姓氏男性亲人及其姻亲和后代；粗略地来说，如果不考虑改姓、随母姓等特殊情况，除了父母及两人的直系后代之外，来自父亲一方同姓的血亲（父亲兄弟及
  • 血液蛋白血浆蛋白（英语：plasma proteins）——又被称为血液蛋白（英语：blood proteins）——是血浆中的蛋白质，是血液中除了血红蛋白以外的蛋白质。有时也有人用血清蛋白来称呼它，但是血浆蛋白
  • 麻黄杏仁甘草石膏汤麻黄杏仁甘草石膏汤，出自《伤寒杂病论》。简称麻杏甘石汤或麻杏石甘汤。麻黄四两（去节） 杏仁五十个（去皮尖） 炙甘草二两 石膏半斤（碎、棉裹）上四味，以水七升，先煮麻黄减二升，去上沫
  • 布兰卡港布兰卡港（西班牙语：Bahía Blanca）是位于阿根廷布宜诺斯艾利斯省东南部大西洋沿岸的一座港口城市。城市名称意为“白色海湾”。
  • 阿尔韦托·费尔南德斯阿尔韦托·安赫尔·费尔南德斯（Alberto Ángel Fernández；1959年4月2日－），阿根廷正义党籍政治家，现任阿根廷总统。费尔南德斯在2019年阿根廷总统选举中击败欲争取连任的毛里西奥
  • 撞击参数在物理学的散射问题里，撞击参数（b）的定义为一个抛射体的速度矢量与标靶物体质心的垂直距离，而当中标靶的中心U(r)是由一个正在接近的抛射体所做成。在核子物理学和经典力学里，时
  • 白克白克（1914年2月1日－1964年2月22日），出生于厦门，为台湾战后第一代导演及影评人，白色恐怖受难者。抗日战争期间，于西南第五战区文化工作委员会负责电影戏剧宣传工作。1945年，随第一批
  • 祖基菲里艾哈迈德拿督斯里祖基菲里艾哈迈德（马来语：Dzulkefly Ahmad），马来西亚雪兰莪州瓜拉雪兰莪希盟诚信党国会议员，目前是诚信党策略局主任，曾是伊斯兰党中央委员，2015年随末沙布退出伊斯兰党并
X7DCMS 鲁ICP备15002942号
新起点 今日百科 新贝范文 星座占卜 蜜桃圈