Árbol
El árbol es una estructura no lineal, muy util para almazenar datos de forma jerárquica y que poden ser acesados de forma rapida.
Un árbol se puede definir como una colección de datos representados por nodos y organizados en niveles jerárquicos (en lugar de secuencias como las estructuras vistas anteriormente).
Un ejemplo de estructura en árbol son los organigramas de empresas:
La estructura más comun es de árbol binaria, que tiene en el maximo dos nodos hijos a partir del nodo inicial (llamado de raiz o root). Un nodo puede tener padres, hermanos e hijos; los nodos que tienen por lo menos un hijo son llamados de nodos internos y los nodos sin hijos son llamados de externos o hojas:
A partir de la estructura de árbol binaria (con un nodo hijo a la izquierda y uno a la derecha de la raiz) es posible estructurar la llamada BST, o árbol de busqueda binaria (binary search tree), que utiliza el principio del algoritmo de busqueda binaria para estructurar los datos de forma que los valores menores esten a la izquierda de la raiz y valores mayores a la derecha. Esta unión del algoritmo con la estructura de datos lleva una mayor eficiencia en la manipulación de datos, sea para buscar, alterar, insertar o remover elementos.
Heap binario
El heap binario es un tipo especial de árbol binaria, normalmente utilizada en computación para implementar cola de prioridades, porque en un heap puedes extraer de forma más eficiente el valor minimo o maximo de una lista. Puedes traducir heap, muy libremente, como un "grupo" o "porción" de datos.
El heap binario difiere del árbol binario en dos caracteristicas principales:
- Todos los niveles, con excepción del ultimo, tiene hijos tanto en la izquierda como en la derecha de la raíz. En el ultimo nivel, los hijos se posicionan lo más a la izquierda posible. Es lo que llamamos árbol completa.
- Puede ser un heap minimo (min heap), para extraer el menor valor del árbol, o heap maximo (max heap) para extraerse el mayor valor. Todos los nodos deben ser o
>=(en el caso del heap máximo) o<=(en el caso del heap minimo) del que los valores de nodos hijos.
Usos
La estructura de árbol tiene varios usos, como algoritmos de tomada de decisión en aprendizaje de la maquina, indexación de banco de datos, indexación y exhibición de archivos y carpetas en el explorador de archivos de los sistemas operacionales. También, es usado en colas de prioridad (tipo especial de cola donde los elementos son retirados de la cola en el nodo padrón FIFO, pero si organizados por prioridad: más prioritarios en el inicio de la cola y menos prioritarios en el final) y también en un algoritmo de ordenación especifico, el heap sort.