Chapter 13, Problem 2P

(a)

Program Plan Intro

To argue that the RB-INSERT and RB-DELETE can maintain the bh attribute without requiring extra storage or without increasing the running time of the execution.

(b)

Program Plan Intro

To describe an algorithm that finds a black node y in $T1$ with the largest key from black height in $T2.bh$ .

(c)

Program Plan Intro

To describe how $Ty\cup \left\{x\right\}\cup T2$ can replace $Ty$ in $O(1)$ time without destroying the binary-search-tree property.

(d)

Program Plan Intro

To explain theenforce properties 2 and 4 in $O(\lg n)$ time and also describe the color followed by property 1, 3 and 5.

(e)

Program Plan Intro

To argue that no generality is lost by making the assumption in part b and describe the symmetric situation that arises $T1.bh\le T2.bh$ .

(f)

Program Plan Intro

To argue the running time of RB-JOIN is $O(\lg n)$ .