ARBOLES AVL

Arboles AVL

Es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1.

Arboles AVL

Reglas de la rotación de un árbol y sus clases de rotación

·        Arboles binario de búsqueda

·        Arboles balanceados

·        Inserción des balanceado retiro

·        La diferencia en alturas

A izquierda à A derecha

Esta abajo en el rango de -1  a 1 

·        F.B factor de equilibrio

·        Si hay des balance 

                       Rotaciones por la izquierda

Rotaciones por la derecha
doble rotación por la izquierda
doble rotación de la derecha

·        En orden debe ser igual antes y después de la rotación 

Como hacer una rotación

Se realiza una rotación a la izquierda cuando el árbol queda des balanceado a la derecha y es el ajuste de dos apuntadores.

Después de una altura no permitida

Como hacer una doble rotación a la izquierda

Se hace una doble rotación a la izquierda si se cumple

1.   El nodo indicado por P tiene un factor de balance menor que uno (1)

2.   El nodo indicado por Q tiene un factor de balance igual a uno (1)

Hay que hacer una simple rotación a la derecha desde Q y una simple rotación a la izquierda desde P

Como hacer una rotación a la Derecha

1.   El nodo indicado por P tiene factor de equilibrio mayor que uno

2.   El nodo indicado por Q tiene el factor de equilibrio igual a 1

Como hacer una doble rotación a la Derecha

1.   El nodo indicado por P tiene un factor de mayor que uno(1)

2.   El nodo indicado por Q tiene factor de equilibrio igual a meno uno (1)