Preguntas sobre Árboles Binarios

¿Qué operaciones se está realizando?

Estructura de un Árbol Binario de Búsqueda

Operación de Inserción

Operación de Búsqueda

La búsqueda de un nodo debe realizarse por medio de la clave(key). Los pasos son: Si el nodo root es null, la clave buscada es igual a la clave del root, retornar el nodo root y finalizar. Si la clave buscada es menor a la clave del root, buscar de forma recursiva a la izquierda. Caso contrario buscar de forma recursiva a la derecha. La búsqueda finaliza devolviendo null o el nodo que tenga la clave buscada.

Se debe buscar el nodo a eliminar. La búsqueda del nodo debe realizarse por medio de la clave(key). Los pasos son: Si el nodo root es null se devuelve null. Si la clave buscada es menor a la clave del root, asignar el nodo izquierdo de forma recursiva. Si la clave buscada es mayor a la clave del root, asignar el nodo derecho de forma recursiva. Si el nodo no tiene hijos, devolver null. La búsqueda finaliza devolviendo null el último nodo revisado. Si el nodo es hoja, se devuelve null a su padre.

Ejemplo: Eliminar nodo 6. 6 > 5, por lo tanto, el nodo de la derecha se asigna al resultado del siguiente nivel de la derecha. 6 < 7, por lo tanto, el nodo de la izquierda se asigna al resultado del siguiente nivel de la izquierda. 6 = 6 y no tiene hijos, por lo tanto, devuelve null.

Ejemplo: Eliminar nodo 7. 7 > 5, por lo tanto, el nodo de la derecha se asigna al resultado del siguiente nivel de la derecha. 7 = 7, por lo tanto, se verifica si el nodo tiene hijos. El nodo 7 sí tiene hijos. Como no tiene hijos a la derecha, retorna el nodo de la izquierda.

Eliminación de Nodo Padre con 2 Hijos. Se debe buscar el nodo a eliminar. La búsqueda del nodo debe realizarse por medio de la clave (key). Los pasos son: Si el nodo root es null se devuelven null. Si la clave buscada es menor a la clave del root, asignar el nodo izquierdo de forma recursiva. Si la clave buscada es mayor a la clave del root, asignar el nodo derecho de forma recursiva. Si el nodo tiene 2 hijos, buscar el nodo con menor valor del subárbol de la derecha y reemplazar la clave. Luego eliminar el nodo con la clave copiada. La búsqueda finaliza devolviendo el nodo con la clave cambiada o el último nodo revisado. Si el nodo padre tiene 2 hijos, copiar su clave del valor del nodo con el valor más bajo del nodo de la derecha.

Eliminación de 1 Hoja. Ejemplo: Eliminar nodo 5. Se encuentra que el menor valor del subárbol de la derecha es el nodo 6. El nodo 5, copiar la clave y el valor del nodo 6 y se inicia una eliminación del nodo 6 original.