Arbol binario y colas de prioridad

ARBOLES BINARIOS DE BÚSQUEDA

Concepto de árbol binario.
 Estas estructuras se utilizan para representar datos en forma jerárquica entre los elementos. Este tipo de estructura es un tipo de dato no lineal de dos dimensiones. Los nodos de los árboles que son los elementos o vértices contienen nodos o mas enlaces, entre los cuales contiene un nodo raíz que es el primer nodo del árbol y que asu vez cada enlace se refiere aun nodo hijo tales como hijo izquierdo e hijo derecho. Los hijos de un solo nodo se conocen como hermanos. Séle llama grado de un nodo al numero de hijos que salen de el y a los nodos con grado 0 se les llama nodos terminales u hojas. Cada numero de un árbol tiene asociado un numero de nivel que se determina por un numero de antecesores que tiene desde la raíz,teniendo en cuenta que el nivel de la raíz es 1 ó 0. Un árbol tiene profundidad o altura que es el máximo de niveles del árbol, además el árbol cuenta con peso que es el número de nodos terminales. Al conjunto de dos o más árboles se le conoce como bosque.
Este tipo de árbol tiene la característica de que los valores en cualquier subárbol izquierdo son menores que el valor de su nodo padre, y losvalores en cualquier subárbol derecho son mayores que el valores de su nodo padre.
Árbol binario es aquel en el que cada nodo tiene como máximo el grado 2. Este es equilibrado cuando la diferencia de altura entre sus subárboles de cualquier nodo es como máximo una unidad, cuando todos los nodos se encuentran a la misma altura se dice que el árbol esta equilibrado. Se llama árbol binario lleno cuandotodas sus hojas están al mismo nivel y sus nodos interiores tienen cada uno dos hijos. Un árbol binario completo es equilibrado mientras un árbol binario lleno es totalmente equilibrado.
 
Árboles binarios de búsqueda.
Dentro del tipo de árbol binario de búsqueda en cualquier nodo el valor es superior a los valores de los nodos de el subárbol (izquierdo e inferior) a el subárbol derecho. Dentrode las características de estos se puede decir que no son únicos para los datos dados.
La utilidad de este tipo de árbol es la eficiencia de búsqueda en un nodo, esta es similar a la búsqueda binaria. La supresión de un nodo requiere la liberación del espacio en la memoria que es ocupada por el mismo.
 

Búsqueda de un elemento.
Este comienza en el nodo raíz y consta de los siguientes pasos:        La clave búsqueda se compra con la clave del nodo raíz.
        Si las claves son iguales la búsqueda se detiene.
        La clave búsqueda es mayor que la clave raíz, la búsqueda se reanuda en el subárbol derecho, si la clave búsqueda es menor que la clave raíz la búsqueda se reanuda en el subárbol izquierdo.
 
Árboles binarios equilibrados.
Es aquel en el que la altura delos subárboles izquierdo y derecho de cualquier nodo no difieren en más de una unidad. Para determinar si el árbol esta equilibrado, se lleva acabo un factor de equilibrio.
El factor de equilibrio del árbol binario es la diferencia de altura entre los subárboles izquierdo y derecho, si se denota la altura del subárbol izquierdo como hI y la altura del subárbol derecho como hD, entonces el factorde equilibrio en un árbol se determina por la siguiente formula:
Fe = hD - hI.
 
Árbol binario equilibrado, árboles AVL.
Se dice que la eficiencia de búsqueda de un árbol binario para localizar una clave varia entre 0(n) y (Log(n)), dependiendo de la estructura. Esto es, se añaden claves a un árbol binario de búsqueda mediante el uso de algoritmos, la estructura del árbol va a depender delorden en el que estas se añaden, de manera que los elementos se insertan de manera creciente o decreciente, de manera que el árbol tendrá todas las ramas izquierda y derecha vacías y la búsqueda en el árbol será de modo secuencial. Para que una búsqueda resulte eficiente es importante que los árboles binarios estén equilibrados y estos sean de mínima altura.
Un árbol binario equilibrado es aquel...