Ejemplos

Sistemas de archivos de computadora

Los sistemas operativos de las computadoras modernas organizan las carpetas y los archivos usando una estructura de árbol. Una carpeta contiene otras carpetas y archivos. 

Para entenderlo mejor, tomaremos el siguiente ejemplo:

La imagen anterior muestra el explorador de Windows con el despliegue de carpetas a la izquierda y los archivos a la derecha en una computadora en particular. A continuación podremos visualizar la misma estructura como un árbol con raíz. 

La raíz se llama Desktop (Escritorio). Abajo de Desktop están My Computer, Internet Explorer, y otros; en la primera imagen, podemos notar como My Computer es lo único desplegado. Abajo de My Computer están 3 ½ Floppy (A:), Micron (C:) y otros que no se muestran. Abajo de Plug_ins, que está resaltado, están los archivos Afill32.api, Aform.js y otros, que aparecen a la derecha de la imagen.

El juego TicTacToe mediante árboles de decisiones

Estudio de ciertos juegos de estrategia que pueden representarse mediante árboles. En donde cada nodo se corresponde con una configuración posible del juego (por ejemplo, estado de un tablero), y cada arco es una transición legal, o jugada, desde una configuración posible a una de sus sucesoras.

Por simplificar, consideremos que:

· Hay dos jugadores que juegan alternadamente;

· los dos jugadores están sometidos a las mismas reglas (juego simétrico);

· el azar no interviene (juego determinista);

· una partida no puede durar indefinidamente, y;

· ninguna configuración tiene un número infinito de posibles sucesoras.

La configuración inicial del juego es la raíz del árbol correspondiente y las hojas del árbol corresponden a las configuraciones terminales del juego, en las que no existe jugada siguiente:

· Bien porque uno de los jugadores ha ganado;

· Bien porque no ha ganado ninguno (situación de empate)

Los niveles impares del árbol están asociados con las configuraciones en las que debe jugar uno de los dos jugadores, mientras que los niveles pares se asocian a las configuraciones en las que debe jugar el otro.

Códigos Huffman

Los árboles binarios pueden usarse como estructuras de datos, por ello a continuación desarrollaremos brevemente la construcción de códigos de Huffman.

La manera más común de representar caracteres internamente en una computadora es usando cadenas de bits de longitud fija. Por ejemplo, ASCII, que representa los caracteres por una cadena de siete bits.

Una parte de la tabla ASCII

La idea es usar cadenas de bits cortas para representar los caracteres que se usan con más frecuencia que las cadenas de bits. Por lo cual es posible representar cadenas de caracteres, como texto y programas, en menos espacio. Un dispositivo que programa automáticamente una videocasetera, usa un código Huffman para generar números que el usuario puede introducir para elegir qué programa grabar.

Un código Huffman se define con gran facilidad mediante un árbol con raíz. Para decodificar una cadena de bits, comenzamos en la raíz y seguimos hacia abajo por el árbol hasta que se encuentra el carácter. El bit, 0 o 1, dice si debemos ir a la derecha o a la izquierda.

Para explicar esto usaremos el siguiente ejemplo: 01010111

Se inicia en la raíz. Como el primer bit es 0, primero vamos a la derecha. Luego vamos a la izquierda y a la derecha (010). En este punto se encuentra el primer carácter R. Para decodificar el siguiente carácter, vamos de nuevo a la raíz. El siguiente bit es 1, entonces vamos a la izquierda y encontramos el siguiente carácter, A (1). Los últimos bits 0111 se decodifican como T. Por lo tanto, la cadena representa las letras RAT.

Cualquier cadena de bits se puede decodificar de manera única, aun cuando los caracteres estén representados por cadenas de bits de longitud variable. Para el código Huffman definido anteriormente, el carácter A se representa por una cadena de bits de longitud 1 mientras que S y T se representan por una cadena de bits de longitud 4. (A se representa como 1, S se representa como 0110 y T como 0111).
            En resumen se podría decir que el camino de la raíz a cualquier hoja representará el código para la etiqueta de esa hoja.