ARBOLES AVL ROTACION DOBLE

ARBOLES AVL ROTACION DOBLE

1. Arboles avl : rotación doble INTEGRANTES: Maycol Enríquez Juan David Ascencio PROFESOR: ING. Víctor Viera Estructura de datos ii

2. ¿Cómo se hace? Un Árbol AVL es un tipo de Árbol Binario que se encuentra balanceado es decir esta en equilibrio, en términos de búsqueda esta bien optimizado a comparación de un árbol que se encuentre en desequilibrio debido a que le tomara mas “pasos/procesos” llegar a su nodo objetivo. ¿Qué es? El método que utilizan este tipo de árbol es hacer un reequilibrado, este concretamente se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse 4 casos para reequilibrar un árbol: Rotación simple a la Derecha. Rotación simple a la Izquierda. Rotación Doble a la Derecha. Rotación Doble a la Izquierda.

3. Cosas a tener en cuenta Decimos que un Árbol Binario se encuentra en equilibrio si para todo Nodo la altura de sus Sub-árboles izquierdo y derecho pueden diferir 1 unidad, nombrando este valor como Factor de equilibrio(FE). La formula del Factor de equilibrio es: FE=Altura Sub-árbol Derecho – Altura Sub-árbol Izquierdo ; siendo el FE=0 Si se esta evaluando un Nodo Hoja. Altura= Nivel del nodo + 1 En caso de que la Rotación S imple Derecha o Izquierda, No funciones se utiliza la rotación doble

4. ROTACION DOBLE A LA DERECHA Para hacer una Rotación Doble Derecha partimos de que la parte izquierda del árbol esta en desequilibrio siendo la parte derecha la que esta “Cargada”, también se debe tener encuentra que el FE objetivo debe ser mayor a 1 y que su Sub-Nodo Derecho tenga un FE<0, es decir que sea negativo, al cumplirse todas estas condiciones decimos que para equilibrar ese sector del árbol se debe hacer una RDD . Formula: RDD= Rotación Doble Derecha RSD= Rotación Simple Derecha RSI= Rotación Simple Izquierda RDD= RSD y RSI

5. ROTACION DOBLE A LA IZQUIERDA Para hacer una Rotación Doble Izquierda partimos de que la parte Derecha del árbol esta en Desequilibrio siendo la parte Izquierda la que esta “Cargada” , también se debe tener encuentra que el FE objetivo debe ser mayor a -1 y que su Sub-Nodo Izquierdo tenga un FE>0 es decir que sea Positivo, al cumplirse todas estas condiciones decimos que para equilibrar ese sector del árbol se debe hacer una RDI . Formula: RDI= Rotación Doble Izquierda RSI= Rotación Simple Izquierda RSD= Rotación Simple Derecha RDI= RSI y RSD

6. Arboles avl : rotación doble INTEGRANTES: Maycol Enríquez Juan David Ascencio PROFESOR: ING. Víctor Viera Estructura de datos ii