Tipos de Arboles (Binarios y HEAP)

Autor: Jesús Villasana  

Arboles Binarios

    Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre “binario”). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno.

    Como estructura de datos este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada. Recorridos con los conocidos métodos recursivos:

• Inorden
• Postorden
• Preorden

Montículo o HEAP

  Un montículo (heap) es una estructura de datos del tipo árbol con información perteneciente a un conjunto ordenado. Los montículos máximos tienen la característica de que cada nodo padre tiene un valor mayor que el de cualquiera de sus nodos hijos, mientras que en los montículos mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos.

    Puede considerarse como un árbol binario con ciertas restricciones, aunque con muchas ventajas. Un heap es un árbol binario casi completo. Se considera casi completo ya que está lleno en todos sus niveles excepto quizá el último que se va completando de izquierda a derecha. Otra diferencia es que un heap cada nodo tiene un valor menor igual (o mayor igual) que el valor asociado a cada uno de sus hijos, lo que se conoce como condición heap.

    

    Un árbol cumple la condición de montículo si satisface dicha condición y además es un árbol binario completo. Un árbol binario es completo cuando todos los niveles están llenos, con la excepción del último, que se llena desde la izquierda hacia la derecha.

    Una ventaja que poseen los montículos es que, por ser árboles completos, se pueden implementar usando arreglos, lo cual simplifica su codificación y libera al programador del uso de punteros.

   La eficiencia de las operaciones en los montículos es crucial en diversos algoritmos de recorrido de grafos y de ordenamiento (heapsort).