13.4 Deletion

13.4-1

Argue that after executing \(\text{RB-DELETE-FIXUP}\), the root of the tree must be black.

• Case 1: transform to 2, 3, 4.
• Case 2: if terminates, the root of the subtree (the new \(x\)) is set to black.
• Case 3: transform to 4.
• Case 4: the root (the new \(x\)) is set to black.

13.4-2

Argue that if in \(\text{RB-DELETE}\) both \(x\) and \(x.p\) are red, then property 4 is restored by the call to \(\text{RB-DELETE-FIXUP}(T, x)\).

Suppose that both \(x\) and \(x.p\) are red in \(\text{RB-DELETE}\). This can only happen in the else-case of line 9. Since we are deleting from a red-black tree, the other child of y.p which becomes \(x\)'s sibling in the call to \(\text{RB-TRANSPLANT}\) on line 14 must be black, so \(x\) is the only child of \(x.p\) which is red. The while-loop condition of \(\text{RB-DELETE-FIXUP}(T, x)\) is immediately violated so we simply set \(x.color = black\), restoring property 4.

13.4-3

In Exercise 13.3-2, you found the red-black tree that results from successively inserting the keys \(41, 38, 31, 12, 19, 8\) into an initially empty tree. Now show the red-black trees that result from the successive deletion of the keys in the order \(8, 12, 19, 31, 38, 41\).

• initial:

  

• delete \(8\):

  

• delete \(12\):

  

• delete \(19\):

  

• delete \(31\):

  

• delete \(38\):

  

• delete \(41\):

  

13.4-4

In which lines of the code for \(\text{RB-DELETE-FIXUP}\) might we examine or modify the sentinel \(T.nil\)?

When the node \(y\) in \(\text{RB-DELETE}\) has no children, the node \(x = T.nil\), so we'll examine the line 2 of \(\text{RB-DELETE-FIXUP}\).

When the root node is deleted, \(x = T.nil\) and the root at this time is \(x\), so the line 23 of \(\text{RB-DELETE-FIXUP}\) will draw \(x\) to black.

13.4-5

In each of the cases of Figure 13.7, give the count of black nodes from the root of the subtree shown to each of the subtrees \(\alpha, \beta, \ldots, \zeta\), and verify that each count remains the same after the transformation. When a node has a \(color\) attribute \(c\) or \(c'\), use the notation \(\text{count}\(c\)\) or \(\text{count}(c')\) symbolically in your count.

Our count will include the root (if it is black).

• Case 1: For each subtree, it is \(2\) both before and after.

• Case 2:

  • For \(\alpha\) and \(\beta\), it is \(1 + \text{count}\(c\)\) in both cases.
  • For the rest of the subtrees, it is from \(2 + \text{count}\(c\)\) to \(1 + \text{count}\(c\)\).

  This decrease in the count for the other subtreese is handled by then having \(x\) represent an additional black.

• Case 3:

  • For \(\epsilon\) and \(\zeta\), it is \(2+\text{count}\(c\)\) both before and after.
  • For all the other subtrees, it is \(1+\text{count}\(c\)\) both before and after.

• Case 4:

  • For \(\alpha\) and \(\beta\), it is from \(1 + \text{count}\(c\)\) to \(2 + \text{count}\(c\)\).
  • For \(\gamma\) and \(\delta\), it is \(1 + \text{count}\(c\) + \text{count}(c')\) both before and after.
  • For \(\epsilon\) and \(\zeta\), it is \(1 + \text{count}\(c\)\) both before and after.

This increase in the count for \(\alpha\) and \(\beta\) is because \(x\) before indicated an extra black.

13.4-6

Professors Skelton and Baron are concerned that at the start of case 1 of \(\text{RB-DELETE-FIXUP}\), the node \(x.p\) might not be black. If the professors are correct, then lines 5–6 are wrong. Show that \(x.p\) must be black at the start of case 1, so that the professors have nothing to worry about.

At the start of case 1 we have set \(w\) to be the sibling of \(x\). We check on line 4 that \(w.color == red\), which means that the parent of \(x\) and \(w\) cannot be red. Otherwise property 4 is violated. Thus, their concerns are unfounded.

13.4-7

Suppose that a node \(x\) is inserted into a red-black tree with \(\text{RB-INSERT}\) and then is immediately deleted with \(\text{RB-DELETE}\). Is the resulting red-black tree the same as the initial red-black tree? Justify your answer.

No, the red-black tree will not necessarily be the same.

• Example 1:

  • initial:

    

  • insert \(1\):

    

  • delete \(1\):

    

• Example 2:

  • initial:

    

  • insert \(1\):

    

  • delete \(1\):

    

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用