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

AA tree

No description
by

carlos Orlando Baron Suarez

on 11 April 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of AA tree

Arbol AA Eliminacion Que es? Inventor Es un tipo de árbol binario de búsqueda auto-balanceable y
se utiliza para almacenar y recuperar informaciòn ordenada de manera eficiente. Comparación Este arbol es una variacion de el Arbol Rojo- Negro, que a su vez mejora el arbol binario de busqueda. Algoritmos Fue Arne Anderson Insercion Metodo de Balanceo Al ser un arbol binario este se debe balancear esto se realiza por medio de los niveles, que estan en cada nodo.
El manejo de niveles se dan con las siguientes propiedades: El nivel de un hijo izquierdo debe ser menor que el nivel de su padre.
El nivel de un hijo derecho debe ser menor o igual al nivel de su padre. El nivel de un nieto derecho debe ser menor que el nivel de su abuelo.
Las hojas son de nivel 1. Los nodos que no son hojas deben tener dos hijos.
El número de nodos visitados, desde la raíz hasta las hojas, por la vía más larga debe ser a lo más el doble del número de nodos recorridos por la vía más corta. Esto asegura un costo logarítmico para las operaciones. Torsion (Skew) Es una rotacion derecha que se realiza cuando una inserción o un borrado genera un enlace horizontal izquierdo. Division (Split) La división es una rotación izquierda condicional que tiene lugar cuando una inserción o un borrado crea dos enlaces horizontales derechos Para la inserción se tiene en cuenta el metodo de busqueda y el metodo de balanceo. Rendimiento El rendimiento de un árbol AA es equivalente al de un árbol rojo-negro. Un árbol AA realiza más rotaciones que un árbol rojo-negro, pero la mayor sencillez de sus algoritmos tiende a hacerlos más rápidos, y estos factores se compensan resultando en un rendimiento similar.
Un árbol rojo-negro es más constante en su rendimiento que un árbol AA, pero un árbol AA tiende a ser más llano lo que produce unos tiempos de búsqueda ligeramente más pequeños.
En el caso de que sea de menor a mayor, primero se busca si el nodo es mayor o menor al nodo raiz, en caso de que sea menor busca por la parte izquierda del arbol, en caso contrario por la parte derecha. Para la busqueda como la mayoria de los arboles binarios, se da segun si es mayor o menor el nodo. En caso que sea de mayor a menor, se invierte lo hecho en el anterior caso. Aplicaciones Este tipo de árbol Binario de búsqueda auto-balanceable es utilizado para almacenar y recuperar información ordenada de manera eficiente. Se usa cuando se debe almacenar y retirar gran cantidad de información y se requiere obtenerla de la forma más óptima posible. Para el metodo de eliminación, tambien depende del metodo de busqueda y el de balanceo. Busqueda Propieades Del Arbol AA Muchas
Gracias!!! Es un árbol binario de búsqueda que intenta mantener su altura, o el numero de niveles de nodos bajo la raíz tan pequeños como sea posible en todo momento Andrés Guillermo Hernández Villa
Carlos Orlando Barón Suárez
Full transcript