ARBOLES AVL
Inserción
La inserción de un elemento en un árbol AVL es idéntica que en un árbol binario de búsqueda la diferencia se encuentra en la comprobación que hay que realizar posteriormente en los árboles AVL.
En un árbol AVL tras realizar la inserción hay que comprobar que se sigue manteniendo la condición de equilibrio, o lo que es lo mismo, que la altura del subárbol izquierdo y la del subárbol derecho difieran en una unidad o sean iguales. Si se produce un desequilibrio hay que re equilibrar la estructura para que siga siendo un árbol AVL.
Vamos a ver los mecanismos de re equilibrado de los árboles AVL:
Rotación simple.
El nodo insertado es el marcado con una X. Esta inserción provoca un desequilibro en el nodo B, que se soluciona con esta rotación.
Rotación doble.
El nodo insertado puede ser una de las dos X, provocando el desequilibrio en el nodo C.
Vamos a ver dos ejemplos reales:
Rotación simple.
Rotación doble.
Borrar
El procedimiento de borrado es el mismo que en el caso de arboles binarios de búsqueda La diferencia se encuentra en el proceso de re equilibrado posterior. Este proceso es idéntico al que se realiza en la inserción, la única diferencia es que en la inserción tras realizar una rotación el árbol ya estaba equilibrado, mientras que en el borrado puede ser necesario realizar mas de una rotación.
Ejemplo:
Si eliminamos del siguiente árbol el nodo 3, el árbol se desequilibra en el nodo 2.
Tras aplicar una rotación simple, el árbol resultante es:
Otras operaciones
Las operaciones adicionales en un árbol AVl son análogas a las de arboles binarios de busqueda
No hay comentarios.:
Publicar un comentario