首页 > 试题广场 >

(重建红黑树的代价)红黑树有4中基本的结构性修改(struc

[问答题]
(重建红黑树的代价)红黑树有4中基本的结构性修改(structural modification)操作:节点插入,节点删除,旋转及更改颜色。我们已经看到RB-INSERT和RB-DELETE操作仅使用O(1)次旋转,节点插入和节点删除操作来维持红黑树的性质,当它们可能需要很多次更改颜色操作。
a.设计一个n节点合法的红黑树,使得调用RB-INSERT添加第n+1个节点会引起次颜色修改,然后设计一个n节点的合法的红黑树,使得调用RB-DELETE删除一个特定节点会引起次颜色更改。
     虽然每个操作引起的颜色更改的最坏情况次数是对数的,但我们可以证明,在一个空红黑树上执行任意m个RB-INSERT和RB-DELETE操作构成的序列,最坏情况也只会引起O(m)次结构修改。注意我们将每次颜色更改都记为一次结构性修改。
b.RB-INSERT-FIXUP和RB-DELETE-FIXUP的代码的主循环都处理一些终结性的情况:一旦遇到这些情况,会导致循环在常数次操作后终止。对于RB-INSERT-FIXUP和RB-DELETE-FIXUP中处理的各种情况,指出其中哪些是终结的,哪些不是。
      我们首先分析仅仅执行插入操作引起的结构性修改。令T为一棵红黑树,定义是T中红节点数量,假定一个单位的势可以支付RB-INSERT-FIXUP三种情况的任意一种所引起的结构性修改的代价。
c.令T'表示对T应用RB-INSERT-FIXUP情况1得到的结果,证明
d.当使用RB-INSERT向一棵红黑树中插入一个节点时,我们可以将操作分解为三部分。列出RB-INSERT中第1~16行引起的结构性变化和势的变化。以及RB-INSERT-FIXUP的非终结性情况引起的变化和终结性情况引起的变化。
e.利用d证明,任意一次RB-INSERT执行所导致的结构性修改的摊还次数为O(1).
      我们希望证明,既执行插入又执行删除时,所引起的结构性修改次数为O(m)。对每个节点x,我们定义:
                           
现在定义红黑树T的势函数:
                              
且令T'为对T应用RB-INSERT-FIXUP或RB-DELETE-FIXUP的任意非终结性情况后的结果。
f.证明:对RB-INSERT-FIXUP的任意非终结性情况,有。证明:RB-INSERT-FIXUP的任意一次调用所引起的结构性修改的摊还次数为O(1)。
g.证明:对RB-DELETE-FIXUP的任意非终结性情况,有。证明:RB-DELETE-FIXUP的任意一次调用所引起的结构性修改的摊还次数为O(1)。
h.证明:任意m个RB-INSERT和RB-DELETE操作构成的序列最坏情况下执行O(m)次结构性修改。

这道题你会答吗?花几分钟告诉大家答案吧!