La estrategia para diseñar el algoritmo de eliminación sobre árboles AVL (Árbol AVL es un término usado en computación para referirse a un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis.) es la misma que para la inserción: Se utiliza el mismo algoritmo que sobre árboles binarios de búsqueda, pero en cada recursión se detectan y corrigen errores por medio de balancear() y se actualiza la altura del nodo actual.
Recordamos un poco la idea del algoritmo de eliminación sobre árboles binarios de búsqueda. Primero se recorre el árbol para detectar el nodo a eliminar. Una vez hecho esto hay tres casos a diferenciar por su complejidad:
· Si dicho nodo es una hoja procedemos a eliminarlos de inmediato, sin más.
· Si dicho nodo tiene un sólo hijo, el nodo puede eliminarse después de ajustar un apuntador del padre para saltar el nodo. Esto se muestra en la Figura:
· Si dicho nodo tiene un sólo hijo, el nodo puede eliminarse después de ajustar un apuntador del padre para saltar el nodo. Esto se muestra en la Figura:
. Si dicho nodo tiene dos hijos el caso es un poco más complicado. Lo que se estila hacer (y que de hecho se hace en el algoritmo gracias a la función auxiliar eliminar_min()) reemplazar el nodo actual por el menor nodo de su subárbol derecho (y luego eliminar éste).
No hay comentarios.:
Publicar un comentario