República Bolivariana de Venezuela

Decanato de Ingeniería

Universidad Fermín Toro

Cabudare – Edo Lara

MAPA CONCEPTUAL

TECNICAS DE ROTACION EN ARBOLES

BALANCEADOS

Presentado por:

Lourdes Barrios

C.I. 19.954.486

Asignatura: Análisis de Algoritmo

Prof. Ing. Diosmary Marrón

Febrero - 2013

Árboles Balanceados

Un grafo se define de la siguiente manera: Un grafo consiste de unnúmero de nodos (puntos o vértices) y un grupo de arcos que unen parejas denodos. A todos los pares de nodos unidos por un arco se les llama nodosadyacentes. Los arcos pueden tener una dirección determinada, generando asíun grafo dirigido, el cual de lo contrario sería no-dirigido. (También existen losgrafos mixtos). Por convención a los nodos de un grafo sele representa concírculos y los arcos que los conectan como líneas(no-dirigido) o flechas(dirigido).

definición

El factor de equilibrio es la diferencia entre las alturasdel árbol derecho y el izquierdo:

FE = altura subárbol derecho - altura subárbol izquierdo;Por definición, para un árbol AVL, este valor debe ser -1, 0

ó 1Si el factor de equilibrio de un nodo es:

0 -> el nodo está equilibrado y sus subárboles tienenexactamente la misma altura.1 -> el nodo está desequilibrado y su subárbol derecho es unnivel más alto.-1 -> el nodo está desequilibrado y su subárbol izquierdo es unnivel más alto.

Factor de Equilibrio

características:

-Árbol balanceado por altura: en dónde todoslos hijos o nodos hoja se intentan mantener a lamisma distancia de la raíz.-Árbol balanceado por peso: en dónde losnodos más visitados o utilizados se mantienen apoca distancia dela raíz.

ARBOLES AVL: es un árbol binario en el cual cada nodo cumple con que todos los nodos de su subárbolizquierdo son menores que la raíz y todos los nodos del subárbol derecho son mayores que la raíz.

Rotación Simple

a la Derecha:

Rotación Simple

a la Izquierda:

op rotIzq: AVL{X} -> [AVL{X}] . eq rotIzq(arbolBin(R1, I, arbolBin(R2, I2, D2))) == arbolBin(R2, arbolBin(R1, I, I2), D2) .

op rotDer: AVL{X} -> [AVL{X}] .eq rotDer(arbolBin(R1, arbolBin(R2, I2, D2), D1)) ==arbolBin(R2, I2, arbolBin(R1, D2, D)) .

Insertar

Usamos la misma técnica para insertar un nodoen un ABB ordenado trazamos una rutadesde el nodo raiz hasta un nodo hoja(donde hacemos la inserción).

Insertamos el nodo nuevo.Volvemos a trazar la ruta de regreso al nodo raíz,

ajustando el equilibrio a lo largo de ella.Si el equilibrio de un nodo llega a ser + - 2,

volvemos a ajustar los subárboles de losnodos para que su equilibrio se mantengaacorde con los lineamientos AVL (que son+- 1)

Eliminar

Al eliminar un nodo en un árbol AVL puedeafectar el equilibrio de sus nodos. Entonces hayque hacer rotaciones simples o dobles.Eliminas un nodo como lo hacemos en un árbolbinario ordenado. Al localizar el nodo quequeremos eliminar seguimos este procedimiento:

-Si el nodo es un nodo hoja, simplemente loeliminamos.-Si el nodo solo tiene un hijo, losustituimos con su hijo.-Si el nodo eliminado tiene dos hijos, losustituimos por el hijo derecho ycolocamos el hijo izquierdo en el subárbolizquierdo del hijo derecho.

Rotación Doble a la Derecha

La Rotación doble a la Derecha son dos rotaciones simples,primero rotación simple izquierda y luego rotación simple derecha.

Rotación Doble a la Izquierda

La Rotación doble a la Izquierda son dos rotaciones simples,primero rotación simple derecha y luego rotación simple izquierda