Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

ÁRBOLES AVL

No description
by

susana Hidalgo Hurtado

on 20 September 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ÁRBOLES AVL

Árboles AVL Integrantes:
Daniel Garcia
Alejandra Avendaño
Claudia Penagos
Susana Hidalgo Qué es un árbol AVL? Es un árbol binario de busqueda, en la cual la diferencia de las alturas de los subárboles de cada nodo es uno. Los árboles AVL siempre estan en equilibrio de tal modo que para conseguir esta propiedad, la inserción y el borrado de los nodos se ha de realizar de una forma especial... Fue ideado por los matemáticos rusos Adelson-Velskii y Landis Un árbol AVL se representa de la siguiente manera: Características:
- La diferencia entre las alturas de los subárboles derecho e izquierdo no debe excederse en más de 1.
- Cada nodo tiene asignado un peso de acuerdo a las alturas de sus subárboles
- Un nodo tiene un peso de 1 si su subárbol derecho es más alto, -1 si su subárbol izquierdo es más alto y 0 si las alturas son las mismas. Insertar
Rotación simple (derecha -izquierada)
Rotacion doblre (derecha - izquierada)
Eliminar. Operaciones básicas de un árbol 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 reequilibrar la estructura para que siga siendo un árbol AVL. El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio.




los mecanismos de reequilibrado de los árboles AVL son:

Rotación simple y rotación doble. INSERCIÓN : Al eliminar un nodo en un árbol AVL puede afectar el equilibrio de sus nodos. Entonces hay que hacer rotaciones simples o dobles.
Eliminas un nodo como lo hacemos en un árbol binario ordenado. Al localizar el nodo que queremos eliminar seguimos este procedimiento:
Si el nodo es un nodo hoja, simplemente lo eliminamos.
Si el nodo solo tiene un hijo, lo sustituimos con su hijo.
Si el nodo eliminado tiene dos hijos, lo sustituimos por el hijo derecho y colocamos el hijo izquierdo en el subárbol izquierdo del hijo derecho. Eliminación. Si el equilibrio del padre del nodo eliminado cambia de 0 a +-1 el algoritmo concluye.
Si el padre del nodo eliminado cambio de +-1 a 0, la altura del árbol ha cambiado y se afecte el equilibrio de su abuelo.
Si el equilibrio del padre del nodo eliminado cambia de +- 1 a +- 2 hay que hacer una rotación. Después de concluirla, el equilibrio del padre podría cambiar, lo que, a su vez, podría forzarnos a hacer otros cambios (y probables rotaciones) en toda la ruta hacia arriba a medida que ascendemos hacia la raíz. Si encontramos en la ruta un nodo que cambie de 0 a +- 1 entonces terminamos Cuando hemos eliminado el nodo.... Rotaciones
Esta rotación se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2.
Existen dos tipos de rotaciones:
R-otacion Simple a la Derecha.
-Rotacion Simple a la Izquierda.
-Rotacion doble a la Derecha.
-Rotacion doble a la Izquierda. ROTACIÓN SIMPLE A LA DERECHA De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d). ROTACIÓN SIMPLE A LA IZQUIERDA. De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i). ROTACIÓN DOBLE A LA DERCHA Esta operación consta de dos rotaciones simples; el proceso que se sigue es primero la rotación simple a la izquierda y luego la rotación simple a la derecha. ROTACIÓN DOBLE A LA IZQUIERDA En esta tambien se emplean dos rotaciones simples solo que el orden de ellas cambia a primero se realiza la rotación de la derecha y luego la de la izquierda A B C D E F B A C D E F 1 2 3 4 5 6 7 8 9 10 1 2 3 4 7 6 5 8 10 9 Codigo Java
Full transcript