13.3 Insertion

13.3-1

In line 16 of \(\text{RB-INSERT}\), we set the color of the newly inserted node \(z\) to red. Observe that if we had chosen to set \(z\)'s color to black, then property 4 of a red-black tree would not be violated. Why didn't we choose to set \(z\)'s color to black?

If we chose to set the color of \(z\) to black then we would be violating property 5 of being a red-black tree. Because any path from the root to a leaf under \(z\) would have one more black node than the paths to the other leaves.

13.3-2

Show the red-black trees that result after successively inserting the keys \(41, 38, 31, 12, 19, 8\) into an initially empty red-black tree.

insert \(41\):

insert \(38\):

insert \(31\):

insert \(12\):

insert \(19\):

insert \(8\):

13.3-3

Suppose that the black-height of each of the subtrees \(\alpha, \beta, \gamma, \delta, \epsilon\) in Figures 13.5 and 13.6 is \(k\). Label each node in each figure with its black-height to verify that the indicated transformation preserves property 5.

(Removed)

13.3-4

Professor Teach is concerned that \(\text{RB-INSERT-FIXUP}\) might set \(T.nil.color\) to \(\text{RED}\), in which case the test in line 1 would not cause the loop to terminate when \(z\) is the root. Show that the professor's concern is unfounded by arguing that \(\text{RB-INSERT-FIXUP}\) never sets \(T.nil.color\) to \(\text{RED}\).

First observe that \(\text{RB-INSERT-FIXUP}\) only modifies the child of a node if it is already \(\text{RED}\), so we will never modify a child which is set to \(T.nil\). We just need to check that the parent of the root is never set to \(\text{RED}\).

Since the root and the parent of the root are automatically black, if \(z\) is at depth less than \(2\), the while loop will be broken. We only modify colors of nodes at most two levels above \(z\), so the only case we need to worry about is when \(z\) is at depth \(2\). In this case we risk modifying the root to be \(\text{RED}\), but this is handled in line 16. When \(z\) is updated, it will be either the root or the child of the root. Either way, the root and the parent of the root are still \(\text{BLACK}\), so the while condition is violated, making it impossibly to modify \(T.nil\) to be \(\text{RED}\).

13.3-5

Consider a red-black tree formed by inserting \(n\) nodes with \(\text{RB-INSERT}\). Argue that if \(n > 1\), the tree has at least one red node.

Case 1: \(z\) and \(z.p.p\) are \(\text{RED}\), if the loop terminates, then \(z\) could not be the root, thus \(z\) is \(\text{RED}\) after the fix up.
Case 2: \(z\) and \(z.p\) are \(\text{RED}\), and after the rotation \(z.p\) could not be the root, thus \(z.p\) is \(\text{RED}\) after the fix up.
Case 3: \(z\) is \(\text{RED}\) and \(z\) could not be the root, thus \(z\) is \(\text{RED}\) after the fix up.

Therefore, there is always at least one red node.

13.3-6

Suggest how to implement \(\text{RB-INSERT}\) efficiently if the representation for red-black trees includes no storage for parent pointers.

Use stack to record the path to the inserted node, then parent is the top element in the stack.

Case 1: we pop \(z.p\) and \(z.p.p\).
Case 2: we pop \(z.p\) and \(z.p.p\), then push \(z.p.p\) and \(z\).
Case 3: we pop \(z.p\), \(z.p.p\) and \(z.p.p.p\), then push \(z.p\).

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