Definicion:
Es una estructura de datos no lineal para organizacion de informacion por niveles.
Organizacion por jerarquia (diferenciacion entre elementos mayores y menores)
Aplicacion:
Estructuras organizacionales, tecnologica, ecpresiones aritmeticas, directorios,busqueda y ordenamiento.
Terminologia:
Nodo: Cada componente de un arbol, la comunicacion es descendiente, raiz hacia las hojas.
Subarbol: Es un nodo con sus descendientes.
Niveles: Posicion nodo en una linea horizontal
Peso: Cantidad de hojas
Altura: Cantidad de niveles
Nodo entero: tiene padres e hijos
Arbol general: Un arbol tienehijos indeterminadamente
Implementacion:
Estatica ( vectores)
Dinamica (Nodos)
Arboles Binarios
Son aquellos que tienen maximo 2 hilos por nodos.
Completo: Todos los nodos tienen 1 o 0 hijos
Balanceado: La diferencia entre las alturas de los subarboles para todos los nodos
Degenerado: Todos los nodos solo tienen un descendiente excepto las hojas
Lleno: Todos los niveles tienen el maximo de nodos 2n-1
Implementacion:
Funciones de recorrido
Arbol de expresiones
Arbol binario completo que se utiliza para representar y evaluar expresiones aritmeticas, en estos, las hojas son los operandos y el resto de nodos los operadores.
EXPRESION: a+b*c
Arboles abb:
Arbol binario de busqueda, contiene un algoritmo que permite ordenar y hacer mas eficiente, el proceso de busqueda, que en las estructuras vistas anteriormente.
mayor eficiencia,menor numero de comparacion es al buscar un elemento.
en el proceso de búsqueda cuando se avanza se hace un descarte del 50%
Avl, operaciones
Insertar: se aplica inicialmente la misma regla de los ABB,pero adicionalmente se calcula el FACTOR DE EQUILIBRIO en la rama de la insercion.
FE= hSi(Altura subarbol izquierdo)- hSd(Altura subarbol derecho)
Comenzando por la hoja y subimos por la raiz. si se encuentran un nodo "FE=0" o llegamos a la raiz con FE normal en balance, paramos si un nodo presenta FE fuera de un rango de balance, se produce una restauracion del arbol dependiendo de los siguientes casos:
Casos de rotacion IZQUIERDA- IZQUIERDA (I.I)
Insertar c,b,a
Caso de rotacion DERECHA- DERECHA( D.D)
Insertar: a,b,c
Caso de rotacion IZQUIERDA - DERECHA (I.D)
Insertar:c,a,b
Insertar a,c,b
EJERCICIO:
INSERTAR EN EL ARBOL AVL LAS SIGUIENTES CLAVES:
8,15,5,17,23,29,39,36,30,44,3,4,9,11
0 comentarios :
Publicar un comentario