24.11.2022 borra_en_arbol_rn( A, z ) 1 y = z 2 color-original-y = y.color 3 if z.izq == A.nil 4 x = z.der 5 transplantar_rn( A, z, z.der ) # El primer caso está resuelto 6 else 7 if z.der == A.nil 8 x = z.izq 9 transplantar_rn( A, z, z.izq ) # El segundo caso está resuelto 10 else 11 y = minimo_arbol( z.der ) 12 color-original-y = y.color 13 x = y.der 14 if y.p == z 15 x.p = y 16 else 17 transplantar_rn( A, y, y.der ) 18 y.der = z.der 19 y.der.p = y 20 transplantar_rn( A, z, y ) 21 y.izq = z.izq 22 y.izq.p = y 23 y.color = z.color 24 if color-original-y == NEGRO 25 corregir_borra_en_arbol_rn( T, x ) Aunque este código tiene casi el doble de líneas que en anterior borra_en_nodo(), los dos tienen casi la misma estructura. Se cambió los NIL por A.nil y las llamadas a transplantar() por transplantar_rn(). Otras diferencias en el código: * Se tiene en nodo 'y' como el nodo que será removido del árbol o el que será movido dentro del árbol. En la línea 1, será el nodo que será removido cuando z tiene menos de dos hijos y su remoción es directa. Cuando z tiene dos hijos, en la línea 9, 'y' apunta al sucesor de 'z', junto como en borra_arbol(), y 'y' será movido a la posición de 'z' en el árbol. * Debido a que el color del nodo 'y' puede cambiar, la variable color-original-y almacena el color de 'y' antes de que este cambio ocurra. En las líneas 2 y 12 se asigna esta variable inmediatamente después de asignar 'y'. Cuando 'z' tiene dos hijos, entonces 'y' != 'z' y el nodo 'y' se mueve dentro de la posición original del nodo 'z' en el árbol rojo y negro; en la línea 23: 23 y.color = z.color se pone el color de 'y' igual al color de 'z'. Se necesita salvar el color original de 'y' para poder probarlo al final de borra_en_arbol_rn( ); si este fue negro, entonces remover o mover 'y' podría causar volaciones a las propiedades del árbol. * Como ya se dijo, se mantiene al nodo 'x' que se mueve en la posición original del nodo 'y'. Los asignamientos en las líneas 4, 8 y 13 ponen x para apuntar al hijo únivo de 'y', o, si 'y' no tiene hijos, al sentinela A.nil. (se tiene que recordar que 'y' no tiene hijo a la izquierda). * Ya que el nodo 'x' se mueve a la posición original de 'y', el atributo x.p se pone siempre a apuntar a la posición original en el árbol del padre de 'y', aún si 'x' es, de hecho, el sentinela A.nil. A menos que 'z' es el padre original de 'y' (lo cual ocurre solamente cuando 'z' tiene dos hijos y su sucesor 'y' es el hijo a la derecha de 'z'), la asignación x.p toma lugar en la línea 6 de transplantar_rn(). Observe que cuando se llama a transplantar_rn() en las líneas 5, 9 o 17 el tercer parámetro que se pasa es lo mismo que 'x'. * Cuando el padre original de 'y' es 'z', sin embargo, no queremos que x.p apunte al padre original de 'y', ya que se esta removiendo ese nodo del árbol. Debido al nodo 'y' se moverá hacia arriba para tomar la posición de 'z' en el árbol, poniendo x.p a 'y' en la línea 15 cause que x.p apunte a la posición originak del padre de 'y', aún si x = A.nil. * Finalmente, si el nodo 'y' fue negro, podríamos introducir una o más violaciones de las propiedades del árbol rojo y negro, de esta forma se llama a corregir_borra_en_arbol_rn( T, x ) en la línea 25 para reestablecer las propiedades del árbol. Si 'y' fue rojo, las propiedades del árbol aún se mantienen cuando se remueve o mueve 'y', por las siguientes razones: 1. No se han cambiado los alturas negras en el árbol. 2. Los nodos rojos no se han hecho adyacentes. Debido a que 'y' toma el lugar de 'z' en el árbol, junto con el color de 'z', no se pueden tener dos nodos rojos adyacentes en la posición nueva de 'y' en el árbol. Además, si 'y' no fue el hijo a la derecha de 'z', entonces el hijo 'x' original a la derecha de 'y' reemplaza a 'y' en el árbol. Si 'y' es rojo entonces 'x' debe ser negro y así reemplazar 'y' por 'x' no puede causar que dos nodos rojos sean adyacentes. 3. Ya que 'y' podría no haber estado en la raíz si este fue rojo, la raíz permanece como negra. corregir_borra_en_arbol_rn( A, x ) 1 while x != A.raiz and x.color == NEGRO 2 if x == x.p.izq 3 w = x.p.der 4 if w.color == ROJO # Caso 1 5 w.color = NEGRO # Caso 1 6 x.p.color = ROJO # Caso 1 7 rota_izquierda( A, x.p ) # Caso 1 8 w = x.p.der # Caso 1 9 if w.izq.color == NEGRO and w.der.color == NEGRO 10 w.color = ROJO # Caso 2 11 x = x.p # Caso 2 12 else 13 if w.der.color == NEGRO 14 w.izq.color == NEGRO # Caso 3 15 w.color = ROJO # Caso 3 16 rotar_derecha( A, w ) # Caso 3 17 w = x.p.der # Caso 3 18 w.color = x.p.color # Caso 4 19 x.p.color = NEGRO # Caso 4 20 w.der.color = NEGRO # Caso 4 21 rotar_izquieda(A, x.p) # Caso 4 22 x = A.raiz # Caso 4 23 else 24 w = x.p.izq 25 if w.color == ROJO 26 w.color = NEGRO 27 x.p.color = ROJO 28 rota_derecha( A, x.p ) 29 w = x.p.izq 30 if w.der.color == NEGRO and w.izq.color == NEGRO 31 w.color = ROJO 32 x = x.p 33 else 34 if w.izq.color == NEGRO 35 w.der.color == NEGRO 36 w.color = ROJO 37 rotar_izquierda( A, w ) 38 w = x.p.izq 39 w.color = x.p.color 40 x.p.color = NEGRO 41 w.izq.color = NEGRO 42 rotar_derecha(A, x.p) 43 x = A.raiz 44 x.color = NEGRO