Árboles

ÁRBOLES
Los árboles forman una de las subclases gráficas que más se utilizan. En particular, la ciencia de la computación hace uso de los árboles ampliamente. En computación, los árboles son útiles para organizar y relacionar datos en una base de datos. Los árboles surgen en problemas teóricos como el tiempo óptimo para ordenar.

Al contrario de los árboles naturales, cuyas raíces se localizanabajo, en teoría de gráficas los árboles con raíces suelen dibujarse con la raíz hacia arriba. Primero se coloca la raíz v1 arriba. Abajo de la raíz y al mismo nivel, se colocan los vértices v2 y v3, a los que se puede llegar desde la raíz por una trayectoria simple de longitud 1. Abajo de estos vértices, y al mismo nivel se colocan los vértices v4, v5, v6 y v7. Se continúa así hasta dibujar elárbol completo. Como la trayectoria simple de la raíz de cualquier vértice dado es única, cada vértice está en un nivel determinado de manera única. El nivel de la raíz es el nivel 0. Se dice que los vértices debajo de la raíz están en el nivel 1, y así sucesivamente. Entonces, el nivel de un vértice v es la longitud de la trayectoria simple de la raíz a v. La altura de un árbol con raíz es elnúmero máximo del nivel que ocurre.
Sistemas de archivos por computadora
Los sistemas operativos de las computadoras modernas organizan las carpetas a la izquierda y los archivos a la derecha en una computadora particular.
Árboles de definición jerárquica.
Estos árboles se usan para mostrar las relaciones entre los registros de una base de datos.
Códigos Huffman
La manera más común de representarcaracteres internamente en una computadora es usando cadenas de bits de longitud fija. Por ejemplo, el código estándar para intercambio de información ASCII (American Standard Code for Information Interchange) representa los caracteres por una cadena de siete bits.
Los códigos Huffman, que representan caracteres por cadenas de bits de longitud variable, proporcionan alternativas al ASCII y otroscódigos de longitud fija. La idea es usar cadenas de bits cortas para representar los caracteres de uso menos frecuentes.

Árboles de expansión
Un árbol T es un árbol de expansión de una gráfica G si T es una subgráfica de G que contiene todos los vértices de G. En general, una gráfica tiene varios árboles de expansión.

Árboles binarios
Los árboles binarios están entre los tiposespeciales más importantes de árboles con raíz. Todo vértice en un árbol binario tiene cuando mucho 2 hijos. Más aun, cada hijo se designa como hijo izquierdo o un hijo derecho. Cuando se dibuja un árbol binario, un hijo izquierdo se dibuja a la izquierda, y un hijo derecho se dibuja a la derecha.
Un árbol binario completo es un árbol binario en el que cada vértice tiene dos o cero hijos. Un resultadofundamental acerca de los árboles binarios complets es el siguiente:
Si T es un árbol binario completo con i vértices internos, entonces T tiene i+1 vértices terminales y 2i+1 vértices en total.
Un torneo por eliminación sencilla es un torneo en el que se elimina a un competidor después de una derrota. La gráfica de un torneo por eliminación sencilla es un árbol binario completo. Los nombres delos competidores se listan a la izquierda. Los ganadores avanzan a la derecha. En algún momento, habrá un solo ganador en la raíz.
Un árbol de búsqueda binario es un árbol binario T en el que se asocian datos a los vértices. Los datos están arreglados de manera que para cada vértice v en T, cada dato en el subárbol de la izquierda de v es menor que el dato en v, y cada dato en el subárbol de laderecha de v es mayor que el dato en v.
Los árboles de búsqueda binaria son útiles para localizar datos. Esto es, a partir de un dato D, es fácil determinar si D es un árbol de búsqueda binaria y, si está presente, dónde se localiza. Para determinar si un dato D está en el árbol de búsqueda binaria, comenzaríamos en la raíz. Después compararíamos D repetidas veces con el dato en el vértice...