Árboles como un tipo especial de grafos

2.1 Componentes principales del árbol

Árbol — es un tipo especial de grafo que es acíclico y conexo. En un árbol, existe un único camino entre cualquier par de nodos, lo que hace que su estructura sea jerárquica.

Componentes principales del árbol:

1. Nodos:

• Elementos principales del árbol que contienen datos.
• Por ejemplo, cada círculo en el diagrama representa un nodo.

2. Raíz:

• Nodo que no tiene nodos padres. Es el punto de inicio del árbol.
• Por ejemplo, el nodo superior en el diagrama.

3. Hojas:

• Nodos que no tienen nodos hijos. Están en los "extremos" del árbol.
• Por ejemplo, los nodos en la parte inferior del diagrama.

4. Aristas:

• Conexiones entre nodos. Determinan las relaciones padre-hijo entre los nodos.
• Por ejemplo, las líneas que conectan nodos en el diagrama.

5. Subárboles:

• Cualquier subconjunto del árbol, consistente de un nodo y todos sus descendientes.
• Por ejemplo, una rama del árbol que comienza desde un nodo.

Características importantes del árbol:

1. Altura del árbol:

• Longitud del camino desde la raíz hasta la hoja más distante.
• Por ejemplo, el número de niveles en el diagrama.

2. Profundidad del nodo:

• Longitud del camino desde la raíz hasta un nodo dado.
• Por ejemplo, el número de niveles desde la raíz hasta un nodo específico.

2.2 Árboles binarios

Se pueden identificar diferentes tipos de árboles. Empecemos con los más sencillos.

Árbol binario — es un árbol en el que cada nodo tiene no más de dos nodos hijos, llamados hijo izquierdo y hijo derecho.

Ejemplo de un árbol binario:

Tipos especiales de árboles binarios:

Árbol binario completo:

Todos los niveles del árbol, excepto el último, están completamente llenos, y todos los nodos del último nivel se ubican lo más a la izquierda posible.

Árbol binario perfecto:

Todos los nodos internos tienen exactamente dos nodos hijos, y todas las hojas están en un mismo nivel.

Árbol binario balanceado:

La diferencia de altura de los subárboles de cualquier nodo no excede 1.

Árbol binario de búsqueda:

Para cualquier nodo, su subárbol izquierdo contiene solo nodos con valores menores, y su subárbol derecho solo nodos con valores mayores.

2.3 Árboles n-arios

Un árbol n-ario es un árbol en el que cada nodo puede tener no más de n nodos hijos.

Tipos especiales de árboles n-arios:

1. Árbol ternario (Ternary Tree):

Cada nodo tiene no más de tres nodos hijos.

2. Árbol k-ario (k-ary Tree):

Cada nodo tiene no más de k nodos hijos.

Ejemplo de un árbol 3-ario (cada nodo tiene no más de tres nodos hijos):

2.4 Ejemplos de uso de árboles

1. Sistema de archivos

Uso de árboles: Representación de la estructura jerárquica de archivos y carpetas en un sistema operativo.

El nodo raíz representa el directorio raíz, los nodos internos — las carpetas, y las hojas — los archivos. Las operaciones incluyen la creación, eliminación y movimiento de archivos y carpetas.

2. Árbol de decisiones

Uso de árboles: Análisis y aprendizaje automático para la toma de decisiones.

Los nodos internos representan preguntas o condiciones, las ramas — las respuestas posibles, y las hojas — las decisiones o acciones finales. Por ejemplo, el diagnóstico de enfermedades en medicina basado en síntomas.

3. Documento XML/HTML

Uso de árboles: Representación estructurada de datos en formato XML o HTML.

El nodo raíz representa todo el documento, los nodos internos — las etiquetas y elementos, y las hojas — los nodos de texto y atributos. Esto ayuda en el análisis y manipulación del contenido de los documentos.

4. Estructura organizativa

Uso de árboles: Representación de la jerarquía en organizaciones y empresas.

El nodo raíz representa al director general, los nodos internos — gerentes y departamentos, y las hojas — empleados. Esto ayuda a visualizar y gestionar la estructura organizativa.

5. Juego de ajedrez

Uso de árboles: Representación de los movimientos posibles en el juego.

El nodo raíz representa el estado inicial del juego, los nodos internos — movimientos posibles, y las hojas — estados finales del juego. Esto ayuda en la planificación de estrategias y toma de decisiones en programas de ajedrez.