假设用RB-INSERT将一个节点x插入到一棵红黑树,紧接着又用RB-DELETE将它从树中删除。结果的红黑树与初始的红黑树是否一样?证明你的答案。
RB-INSERT(T, z) 1 y ← nil[T] 2 x ← root[T] 3 while x ≠ nil[T] 4 do y ← x 5 if key[z] < key[x] 6 then x ← left[x] 7 else x ← right[x] 8 p[z] ← y 9 if y = nil[T] 10 then root[T] ← z 11 else if key[z] < key[y] 12 then left[y] ← z 13 else right[y] ← z 14 left[z] ← nil[T] 15 right[z] ← nil[T] 16 color[z] ← RED 17 RB-INSERT-FIXUP(T, z) RB-DELETE(T, z) 1 if left[z] = nil[T] or right[z] = nil[T] 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if left[y] ≠ nil[T] 5 then x ← left[y] 6 else x ← right[y] 7 p[x] ← p[y] 8 if p[y] = nil[T] 9 then root[T] ← x 10 else if y = left[p[y]] 11 then left[p[y]] ← x 12 else right[p[y]] ← x 13 if y 3≠ z 14 then key[z] ← key[y] 15 copy y's satellite data into z 16 if color[y] = BLACK 17 then RB-DELETE-FIXUP(T, x) 18 return y