首页 > 试题广场 >

说明如果红黑树的表示中不提供父指针,应当如何有效的实现RB-

[问答题]
说明如果红黑树的表示中不提供父指针,应当如何有效的实现RB-INSERT。
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)

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