Arboles resumen

Arboles
Los arboles forman una de las subclases de las graficas de uso más amplio. En la computación se hace uso amplio de los arboles, en este terreno los arboles sirven para organizar y relacionar los datos en una base de datos.
Un Árbol (libre) T es una grafica simple que satisface si v y w son vértices en T, entonces existe un único camino simple de v a w.
Un Árbol con raíz es un árbol enel cual un vértice particular se designa como la raíz.



En contraste con los árboles naturales, que tienen su raíz en la parte en la parte inferior, en la teoría de graficas se acostumbra a trazar los arboles con raíz, con su raíz en la parte superior.
Como el camino simple de la raíz a cualquier vértice dado es único, cada vértice esta en un nivel determinado de manera única.
Laaltura de un árbol con raíz es el número máximo de nivel que aparece en dicho árbol.
Códigos de Huffman
Los códigos de huffman representan los caracteres mediante cadenas de bits de longitud variable y proporcionan una alternativa para ASCII y otros códigos de longitud fija. La idea consiste en utilizar cadenas cortas de bits para los caracteres de uso frecuente y utilizar cadenas de bits demayor tamaño para representar caracteres de uso menos frecuente. De esta forma, por lo general es posible representar cadenas de caracteres, como texto y programas, en un menor espacio comparado con el espacio necesario al utilizar ASCII.
Un código Huffman se define fácilmente mediante un árbol con raíz. Para decodificar una cadena de bits comenzamos con la raíz y nos movemos hacia abajo en el árbolhasta encontrar un carácter. El bit 0 o 1 nos indica si debemos movernos hacia la izquierda o a la derecha.
Ejemplo:

Huffman dio un algoritmo para construir un código de Huffman a partir de una tabla con la frecuencia de aparición de los caracteres que se desea representar, de modo que el código represente cadenas de caracteres en un mínimo espacio, siempre que las cadenas por representartengan la frecuencia de los caracteres idéntica a la frecuencia de los caracteres en la tabla
7.2 Terminología y Caracterizaciones de los Arboles.
Un árbol genealógico se puede considerar como un árbol con raíz. Los vértices adyacentes a un vértice v y en el siguiente y en siguiente nivel hacia abajo son los hijos de v.
Una grafica sin ciclos es una grafica acíclica. Hemos mostrado que un árbol,es una grafica conexa acíclica. El reciproco también es cierto: toda grafica conexa acíclica es un árbol.
7.3 Árboles de Expansión
Un árbol T es un árbol de expansión de una grafica G si T es una subgrafica de G que contiene a todos los vértices de G.
Búsqueda a lo ancho para obtener un árbol de expansión.
Este algoritmo determina un árbol de expansión mediante el método de búsqueda a lo ancho.Entrada: una grafica conexa G con los vértices ordenados
Salida: un árbol de expansión T

La búsqueda a lo ancho se puede utilizar para verificar si una grafica arbitraria G con n vértices es conexa.
La búsqueda a lo ancho también se puede utilizar para determinar caminos de longitud mínima en una grafica sin pesos, que vallan de un vértice dado v a todos los demás vértices.

Unaalternativa a la búsqueda a lo ancho es la búsqueda a profundidad, la cual pasa a los niveles sucesivos de un árbol en la primera oportunidad posible.

7.4 Árboles de Expansión Mínimos

Sea G una grafica con pesos. Un árbol de expansión mínimo de G es un árbol de expansión de G con peso mínimo.

Analizaremos el algoritmo para determinar un árbol de expansión mínimo conocido como algoritmo de Prim.Este algoritmo construye un árbol agregando aristas de manera iterativa hasta obtener un árbol de expansión mínimo. En cada iteración agregamos una arista de peso mínimo que no forme un ciclo en el árbol en cuestión. Otro algoritmo para determinar un árbol de expansión mínimo es el Algoritmo de Kruskal.

El algoritmo de Prim es un ejemplo de algoritmo codisioso, es decir aquel que optima la...