Estructuras de Datos: Fundamentos y Tipos de Árboles en Programación

Definición de Árboles

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos; es una estructura compuesta por un dato y varios árboles.

Características Importantes

• Cada nodo solo puede ser apuntado por otro: cada nodo solo tendrá un padre.
• Punteros: todos los nodos tendrán el mismo número de punteros.
• Árbol completo: un árbol en el que cada nodo, o bien todos o ninguno de los hijos existe, se llama árbol completo.

Características del Árbol con Relación a su Tamaño

• Orden: es el número potencial de hijos que puede tener cada elemento del árbol.
• Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol.
• Nivel: se define para cada elemento del árbol como la distancia de la raíz, medida en nodos.
• Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel.

Operaciones Básicas con Árboles

• Añadir o insertar elementos.
• Buscar o localizar elementos.
• Borrar elementos.
• Moverse a través del árbol.
• Recorrer el árbol completo.

Árboles Ordenados

Árboles Binarios de Búsqueda (ABB)

Son árboles de orden 2 que mantienen una secuencia ordenada si se recorren en in-orden.

Árboles AVL

Son árboles binarios de búsqueda equilibrados.

Árboles Perfectamente Equilibrados

Son árboles binarios de búsqueda en los que el número de nodos de cada rama para cualquier nodo no difieren en más de 1.

Árboles 2-3

Son árboles de orden 3, que contienen dos claves en cada nodo y que están también equilibrados.

Árboles B

Caso general de árboles 2-3 que, para un orden m, contiene m-1 claves.

Operaciones y Comprobaciones en ABB

• Comprobar si un árbol está vacío: un árbol está vacío si su raíz es NULL.
• Calcular número de nodos: llevar siempre la cuenta de nodos en el árbol al mismo tiempo que se añaden o eliminan elementos.
• Comprobar si un nodo es hoja: hay que comprobar si tanto el árbol izquierdo como el derecho están vacíos; si ambos lo están, se trata de un nodo hoja.
• Altura de un nodo: buscar el elemento del nodo del cual queremos averiguar la altura; cada vez que avance el nodo, incrementamos la variable que contará la altura del nodo.
• Altura del árbol: hay que recorrer todo el árbol; cada vez que cambiemos de nivel, incrementamos la variable que contiene la altura del nodo actual. Cuando lleguemos al nodo hoja, comparamos su altura con la variable que contiene la altura del árbol; si es mayor, actualizamos la altura del árbol.