Estoy buscando ayuda para comprender las eliminaciones de árboles de búsqueda binaria cuando un nodo tiene dos hijos.

Lo que sé es que cuando un nodo BST que se va a eliminar tiene dos hijos, se puede encontrar el valor más pequeño a partir del subárbol derecho o el valor más grande del subárbol izquierdo.

¿Qué subárbol debería atravesar de forma predeterminada? ¿Debería usar el subárbol derecho o izquierdo? ¿En qué condiciones debo elegir el subárbol izquierdo / derecho? ¿Cuánto importa esta elección?

Por favor, tengan paciencia conmigo, ya que soy un novato en DS y algos.

1
Rishi Surana 28 ago. 2020 a las 20:43

1 respuesta

La mejor respuesta

Si el árbol está más o menos equilibrado, no importará qué subárbol atraviese para encontrar el reemplazo.

De lo contrario, si el árbol se deja pesado, ir al subárbol derecho y elegir el valor más pequeño podría ser más rápido. Y viceversa, si el árbol es demasiado pesado.


Además, si la BST tiene solo valores únicos o si el árbol tiene duplicados, elegir el reemplazo de la raíz del subárbol izquierdo o del subárbol derecho no afectará el invariante del árbol.

1
displayName 28 ago. 2020 a las 17:54