Árboles Binarios (1)
Fecha: August 26th, 2009 | Categoría: Informatica | 1 Comment »| PHP Error Message |
Warning: fopen(/home/a7809463/public_html//wp-content/cache/tex_473ecce5b3494c99ce76c616d5d3cb8c.png) [function.fopen]: failed to open stream: Permission denied in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 100
| PHP Error Message |
Warning: fputs(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 101
| PHP Error Message |
Warning: fclose(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 102
| PHP Error Message |
Warning: fopen(/home/a7809463/public_html//wp-content/cache/tex_f99384dad5d2a31cf09da7ec3b60356a.png) [function.fopen]: failed to open stream: Permission denied in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 100
| PHP Error Message |
Warning: fputs(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 101
| PHP Error Message |
Warning: fclose(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 102
| PHP Error Message |
Warning: fopen(/home/a7809463/public_html//wp-content/cache/tex_c5bf510b9cfdc1a281d9c3b8ac8f8624.png) [function.fopen]: failed to open stream: Permission denied in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 100
| PHP Error Message |
Warning: fputs(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 101
| PHP Error Message |
Warning: fclose(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 102
| PHP Error Message |
Warning: fopen(/home/a7809463/public_html//wp-content/cache/tex_beeaca79dbf0d3d79426af06aa19e00c.png) [function.fopen]: failed to open stream: Permission denied in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 100
| PHP Error Message |
Warning: fputs(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 101
| PHP Error Message |
Warning: fclose(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 102
| PHP Error Message |
Warning: fopen(/home/a7809463/public_html//wp-content/cache/tex_d14ae1908567d6b9ed5ba99bb6736ab8.png) [function.fopen]: failed to open stream: Permission denied in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 100
| PHP Error Message |
Warning: fputs(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 101
| PHP Error Message |
Warning: fclose(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 102
| PHP Error Message |
Warning: fopen(/home/a7809463/public_html//wp-content/cache/tex_d14ae1908567d6b9ed5ba99bb6736ab8.png) [function.fopen]: failed to open stream: Permission denied in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 100
| PHP Error Message |
Warning: fputs(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 101
| PHP Error Message |
Warning: fclose(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 102
| PHP Error Message |
Warning: fopen(/home/a7809463/public_html//wp-content/cache/tex_55db972f914bfbd212787407e11ad2e7.png) [function.fopen]: failed to open stream: Permission denied in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 100
| PHP Error Message |
Warning: fputs(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 101
| PHP Error Message |
Warning: fclose(): supplied argument is not a valid stream resource in /home/a7809463/public_html/wp-content/plugins/latex/latex.php on line 102
Quisiera introducir el concepto de árboles binarios y usos más interesantes, con una mirada tal vez muy poco pragmática pero enfocada en sus aplicaciones.
Empecemos por el principio: Un árbol es un grafo. Un grafo es un conjunto de nodos (o vértices, o puntos, o entes, o personas…) y un conjunto de aristas (edges a partir de ahora porque estoy muy acostumbrado a hablar de edges), donde estas aristas describen relaciones entre los nodos. Cada edge tiene dos finales, ambos finales son en nodos del grafo (no pueden no pertenecer al conjunto de nodos). Matemáticamente, esto es 
Es más fácil verlo en un dibujito:
(robado de algún blog por ahí, una de los primeros results de google images)
Donde los circulitos son nodos, y las lineas son edges. Algo curioso particular de este ejemplo es que los nodos están pintados, lo cual es una típica ampliación de la definición de un grafo para hacer más útil este modelo de representación de algún sistema más complejo. Nótese también que los nodos tienen nombre (en este caso, el número es un nombre).
Los árboles son grafos particulares que no tienen ciclos. Esto tiene algunas propiedades interesantes, entre ellas, que sólo existe un camino de un nodo a otro (un camino es un subconjunto de edges que “nos lleva” de un nodo a otro). Además, generalmente se asocia un árbol con un concepto de “raiz” o root más comúnmente, para definir relaciones de “padres e hijos” entre los nodos.
Otro dibujito de un grafo, en este caso un árbol:
Acá los nodos no están coloreados, ni tienen numeritos. Es un ejemplo menos estético pero sirve para mostrar mi idea. El nodo de más arriba, yo lo voy a llamar “root”. Se vé que tiene tres “hijos”, que son los que estarían en lo que voy a llamar el “primer nivel” de mi árbol. El root tiene nivel cero.
Un árbol binario tiene propiedades interesantes. “Binario” significa que cada nodo puede tener hasta 2 hijos inclusive: me interesarán particularmente los árboles binarios completos, esto es, los árboles binarios en los que todos los nodos tienen 2 hijos excepto para el penúltimo nivel, donde pueden tener 2, 1, o ningún hijo, y para el último nivel, que tendrán cero hijos cada nodo.
¿Qué se puede decir de un árbol binario completo? Una propiedad que creo que es la más importante es que la altura de un árbol con N nodos tendrá una altura, es decir, una cantidad de niveles igual a 
.
Heaps
Mi primer ejemplo de árbol binario superútil es la Heap (Parva). Cada nodo tiene asociado un valor. Diremos que un nodo tiene propiedad de “Heap” si se cumple una de estas dos condiciones:
- El nodo no tiene hijos
- Sus hijos tienen un valor asociado mayor al del nodo, y éstos cumplen la propiedad de Heap.
Voy a abreviar “El nodo N tiene propiedad de Heap” como 
. Si tenemos un árbol tal que 
[aunque basta preguntar por 
], y agregamos un nuevo nodo en el primer lugar “incompleto” de nuestro árbol binario, podemos mantener con 
operaciones. Lo que haremos es intercambiar la posición de nuestro nuevo nodo con el padre, mientras el valor del padre sea mayor a nuestro nuevo nodo.
Ejemplito (esta vez no plagié a nadie, el dibujo lo hice yo):
Tenemos una heap. Agregamos un 6 abajo del 15 en la rama izquierda. Esto nos hace perder la propiedad de Heap en 3 nodos. Intercambian los lugares el 6 y el 15, y ahora se cumple H(15). Pero todavía no se cumple el nodo con valor 9 sea heap. Intercambiamos las posiciones del nodo con valor 6 y el nodo con valor 9, y ahora si, tenemos una Heap.
¿Para qué es útil esto? Es la estructura básica detrás de las colas de prioridad. En una cola de prioridad, queremos obtener lo más rápido posible el menor valor de un grupo de numeros, por ejemplo, cuando estamos implementando el Algoritmo de Dijkstra usando una lista de adyacencias. Para eliminar nodos, hacemos algo parecido, agarramos el valor de más arriba y lo guardamos, le ponemos el valor del último elemento de nuestro árbol incompleto, eliminamos nuestro último elemento y vamos bajándolo haciendo swaps con el menor elemento que vallamos encontrando hasta recuperar nuestra propiedad de heap.
Hay un detalle muy interesante de implementación de una heap. Si llamamos al Root 1, a sus hijos 2 y 3, a sus nietos 4, 5, 6, 7, etc… vemos que con simples operaciones podemos encontrar los “familiares” de un nodo. Y como los nombres son consecutivos, nos hacemos los locos y metemos toda la heap en un solo array.
Acá hay una implementación ejemplo, escrita en c por mí, en un estilo que no estoy acostumbrado a usar (practicando para Programación Imperativa): heap
Coming up en un próximo post: Árboles de búsqueda binaria, Range Minimum Query y Fenwick trees.
[...] La Heap es una estructura de datos indispensable para todo programador/algoritmista que pretenda competir en lugares como Topcoder, ACM-ICPC, Google Code Jam, IOI, etc. Fué revisada en el post anterior (heaps, arboles binarios 1) [...]