Saltar al contenido
wandres.dev
Iniciar sesión

Modelo por capas

Los tres casos

Para borrar el nodo con clave k, primero se busca. Después, según cuántos hijos tenga:

  1. Sin hijos (hoja): el enlace del padre pasa a ser nada.
  2. Un hijo: el enlace del padre pasa a apuntar a ese hijo. Todo el subárbol del hijo estaba del mismo lado del padre que k, así que el invariante se mantiene.
  3. Dos hijos: se busca el sucesor de k (la clave siguiente en orden: la menor del subárbol derecho), se copia en el nodo de k, y se borra el sucesor de su sitio original.

El sucesor nunca tiene hijo izquierdo (si lo tuviera, ese hijo sería menor y sería el sucesor), así que borrarlo es el caso 1 o el 2.

Los tres casos de borradoTres filas, cada una con el árbol antes y después. Caso 1: se borra la hoja 20 y el enlace de su padre 30 pasa a ser nada. Caso 2: se borra 30, que tiene un solo hijo, 40; el padre 50 apunta ahora directamente a 40. Caso 3: se borra 30, con hijos 20 y 40; su sucesor es 40, que se copia en el nodo de 30, y la hoja 40 original se quita; queda 40 con 20 a su izquierda.1. Sin hijos: borrar 2020304030402. Un hijo: borrar 303040507040*50703. Dos hijos: borrar 30 (sucesor: 40)20304050702040*5070
Borde grueso: el nodo que se borra (y el sucesor, en el caso 3). Asterisco: el nodo que ocupa el lugar del borrado.
Un BST tiene raíz 50, con hijo izquierdo 30. Su hijo derecho es 80, que tiene hijo izquierdo 60 (con hijo derecho 65) e hijo derecho 90. ¿Cuál es el sucesor de 50?