Red black pseudocode redundancy tree

En introducción a Algorithms Third Edition, tienen una implementación de pseudocódigo de eliminación de árbol rojo-negro. Aquí está ...Red black pseudocode redundancy tree

RB-DELETE(T, z) 
    y = z 
    y-original-color = y.color 
    if z.left == T.nil 
     x = z.right 
     RB-TRANSPLANT(T, z, z.right) 
    elseif z.right == T.nil 
     x = z.left 
     RB-TRANSPLANT(T, z, z.left) 
    else 
     y = TREE-MINIMUM(z.right) 
     y-original-color = y.color 
     x = y.right 
     if y.p == z 
       x.p = y  // <--------- why???? 
     else 
       RB-TRANSPLANT(T, y, y.right) 
       y.right = z.right 
       y.right.p = y 
     RB-TRANSPLANT(T, z, y) 
     y.left = z.left 
     y.left.p = y 
     y.color = z.color 
    if y-original-color == BLACK 
     RB-DELETE-FIXUP(T, x)

ÁRBOL-MÍNIMO simplemente busca el valor más pequeño de un árbol, RB-TRASPLANTE toma el padre del segundo parámetro y tiene su punto con el tercer parámetro, y tiene el padre del tercer parámetro ser el padre del segundo parámetro

Por mi comentario, prueban si y.p es z y, si es así, establece x.p a y. Pero x ya está y.right, entonces esto es como decir y.right.p = y, pero y.right.p ya es y! ¿Por qué están haciendo esto?

Aquí está su explicación ...

“Cuando y del padre original es z, sin embargo, no queremos x.p para apuntar a los padres y original, ya que vamos a eliminar ese nodo del árbol. Debido a que el nodo Y se moverá hacia arriba para tomar la posición de z en el árbol, el establecimiento de XP a y en la línea 13 causas XP para que apunte a la posición original de los padres de Y, aun si x == T.nil.”

Así quieren mantener el padre x sea y ... ya es y ...

Fuente

2011-04-21 confused

Indican en el texto que x también puede ser Nil, es decir, cuando y.right es Nil. Parece que Nil está en este código también representado por un nodo, y no quieren dejar un puntero colgando.

Fuente

2011-04-21 15:17:31

Ah, ya veo! Bombilla. A eso se referían cuando dijeron que iban a aprovechar el hecho de que el nodo T.nil tiene atributos de izquierda, derecha y padre. ¡Gracias! – confused

Solo para aclarar a otros, T.nil es el nodo que representa todos los nodos de hoja en el árbol. Sin él, tendrías O (2^h) cero hojas, lo cual es una pérdida de espacio. Los atributos de T.nil, izquierda, derecha y padre, son arbitrarios. Entonces, cuando x = y.right, si x = T.nil, entonces el padre de x NO será y. Se debe establecer en y, si la última llamada RB-DELETE-FIXUP (T, x) va a funcionar correctamente. – confused

Red black pseudocode redundancy tree

Respuesta

Cuestiones relacionadas