Árbol
En
informática, un árbol es una estructura de
datos ampliamente usada que emula la forma de un árbol (un conjunto
de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y
puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es
padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también
decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que
llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.
Altura de un nodo
La altura de un nodo es el número de aristas en el
camino más largo entre ese nodo y una hoja.
Altura de un árbol
Es la longitud del camino más largo que puede encontrarse en un árbol.
Nivel
El nivel de un nodo se
define por 1 + (el número de conexiones entre el nodo y la raíz).
Grado
Número de subárboles de un
nodo.
Árboles
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. Usos comunes de los árboles
binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación
de Huffman.
Los Montículos binarios
Un
caso particular y sencillo de la estructura de datos Montículo, y está basada en un árbol binario
balanceado, que puede verse como un árbol binario con dos restricciones
adicionales:
Propiedad de montículo
Cada nodo contiene un valor
superior al de sus hijos (para un montículo por máximos) o más pequeño que el
de sus hijos (para un montículo por mínimos).
Árbol semi completo
El árbol está balanceado y
en un mismo nivel las inserciones se realizan de izquierda a derecha.
Los montículos por mínimos
se utilizan frecuentemente para representar colas de prioridad.
No hay comentarios:
Publicar un comentario