Estructura de árbol
Un árbol (Tree) es unano linealestructura de datos que simula la jerarquía de ramas de los árboles en la naturaleza. A diferencia de las estructuras lineales como los arreglos y las listas enlazadas, donde los elementos van uno tras otro, los elementos de datos en un árbol (llamadosnodos) tienen una relación jerárquica explícita de uno a muchos.
Estructura de árboles como un árbol real:
- Nodo raíz: la raíz del árbol, el único nodo sin padre
- Nodo hijo: un nodo que se ramifica desde otro nodo
- Nodo hoja: un nodo sin hijos, como las hojas de un árbol
- Ruta (camino): el recorrido de un nodo a otro
- Profundidad: la longitud de la ruta desde el nodo raíz hasta ese nodo
- Altura: la longitud de la ruta desde ese nodo hasta la hoja más lejana
Analogía con la vida cotidiana:
- Árbol genealógico: abuelos → padres → hijos → nietos
- Organigrama: CEO → director → gerente → empleado
- Sistema de archivos: directorio raíz → subdirectorios → archivos
- Clasificación de libros: categoría general → subcategoría → libros específicos
| Tipo de estructura | Eficiencia de búsqueda | Eficiencia de inserción | Eficiencia de eliminación | Orden |
|---|---|---|---|---|
| Arreglo (Array) | O(n) | O(n) | O(n) | Ninguno |
| Lista enlazada | O(n) | O(1) | O(1) | Ninguno |
| Tabla hash | O(1) | O(1) | O(1) | Ninguno |
| Árbol de búsqueda binaria | O(log n) | O(log n) | O(log n) | tener |
Terminología básica
Antes de profundizar, familiaricémonos con la terminología básica de los árboles:

- Nodo (Node): cada elemento del árbol. Contiene los datos almacenados y los enlaces a sus nodos hijos.
- Nodo raíz (Root): el nodo en la cima del árbol, el punto de partida de todo el árbol. Un árbol tiene exactamente un nodo raíz.
- Nodo padre y nodo hijo (Parent & Child): si un nodo A se conecta a un nodo B inferior, entonces A es elpadre, B es elhijo. Un nodo padre puede tener varios nodos hijos.
- Nodos hermanos (Siblings): los nodos que comparten el mismo padre son hermanos entre sí.
- Nodo hoja (Leaf): un nodo sin hijos, también llamado nodo terminal.
- Arista (Edge): la línea que conecta dos nodos y representa la relación entre ellos.
- Ruta (Path): la secuencia de nodos que se recorren desde el nodo raíz hasta un nodo específico.
- Altura (Height): en la ruta más larga desde un nodo hasta su hoja más lejana, elnúmero de aristas. La altura del árbol es la altura del nodo raíz.
- Profundidad (Depth): en la ruta desde el nodo raíz hasta un nodo, elnúmero de aristas. La profundidad del nodo raíz es 0.
- Nivel (Level): todos los nodos con la misma profundidad pertenecen al mismo nivel. El nodo raíz está en el nivel 0.
Propiedades básicas de los árboles
- Ruta única: entre dos nodos cualesquiera de un árbol existe exactamente una única ruta.
- N nodos, N-1 aristas: un árbol con N nodos tiene un total de N-1 aristas.
- Acíclico: en un árbol no existen ciclos (es decir, partiendo de un nodo y siguiendo las aristas no se puede volver a ese nodo).
¿Por qué se necesitan los árboles? — Ventajas y aplicaciones de los árboles
Quizás te preguntes: con los arreglos y las listas enlazadas, ¿por qué se necesitan los árboles? La respuesta está en la eficiencia.
- Arreglo: búsqueda rápida (mediante índice), pero inserción y eliminación lentas (requiere mover muchos elementos).
- Lista enlazada: inserción y eliminación rápidas, pero búsqueda lenta (requiere recorrer desde el principio).
- Árbol (especialmente el árbol de búsqueda binaria): mantiene los datos ordenados, ofrece una velocidad de búsqueda mucho mayor que las listas enlazadas y operaciones de inserción/eliminación más eficientes que los arreglos.
Escenarios de aplicación práctica:
- Sistema de archivos: las carpetas y los archivos en una computadora se organizan en forma de árbol.
- Índices de bases de datos: los árboles B y B+ son las estructuras de datos centrales para que las bases de datos logren consultas eficientes.
- Organigrama: gestión jerárquica de una empresa o departamento.
- Árbol de decisión: modelos de clasificación en inteligencia artificial y aprendizaje automático.
- HTML DOM: el modelo de objetos del documento (DOM) de una página web es un árbol.
Árbol binario: el miembro más importante de la familia de los árboles
Un árbol binario (Binary Tree) es un árbol en el que cada nodo tiene como máximo dos hijos, a los que normalmente se les llamahijo izquierdoyhijo derecho, y es la base de muchas estructuras de árbol potentes (como el árbol de búsqueda binaria, el montículo y el árbol AVL).
La estructura básica es la siguiente:

Terminología básica del árbol binario
| Término | Definición | Analogía cotidiana |
|---|---|---|
| Nodo | Unidad básica que contiene datos y punteros | Una persona en la familia |
| Nodo raíz | Nodo en la cima del árbol | El antepasado de la familia |
| Nodo padre | Nodo que tiene hijos | Padres |
| Nodo hijo | Nodo apuntado por el nodo padre | Hijos |
| Nodos hermanos | Hijos del mismo padre | Hermanos |
| Nodo hoja | Nodo sin hijos | Persona sin hijos en la familia |
| Profundidad | Número de aristas desde la raíz hasta ese nodo | Número de generaciones |
| Altura | Número de aristas desde ese nodo hasta la hoja más lejana | Generaciones que continúa esa familia |
Tipos de árboles binarios
| Tipo | Características | Complejidad temporal | Escenarios de aplicación |
|---|---|---|---|
| Árbol binario ordinario | Cada nodo tiene como máximo 2 hijos | O(n) | Árbol de expresión |
| Árbol binario lleno | Cada nodo tiene 0 o 2 hijos | O(n) | Codificación de Huffman |
| Árbol binario completo | Todos los niveles están llenos excepto el último | O(n) | Implementación de montículos |
| Árbol de búsqueda binaria | izquierda < raíz < derecha | O(log n) en promedio | Búsqueda, ordenación |
| Árbol binario equilibrado | Diferencia de altura entre el subárbol izquierdo y derecho ≤ 1 | O(log n) | Índices de bases de datos |
| Árbol rojo-negro | Árbol equilibrado con colores | O(log n) | Núcleo de Linux |
Operaciones del árbol de búsqueda binaria
| Operación | Descripción | Complejidad temporal |
|---|---|---|
| Búsqueda | Encontrar un nodo por su valor | O(log n) en promedio, O(n) en el peor caso |
| Inserción | Insertar un nuevo nodo | O(log n) en promedio, O(n) en el peor caso |
| Eliminación | Eliminar un nodo específico | O(log n) en promedio, O(n) en el peor caso |
| Recorrido | Visitar todos los nodos | O(n) |
Recorridos del árbol binario
El recorrido consiste en visitar cada nodo del árbol siguiendo cierta regla, y cada nodo se visita solo una vez. Esta es la base de los algoritmos relacionados con árboles. Hay principalmente cuatro formas:
Recorrido en preorden (Pre-order):Raíz -> Izquierda -> Derecha
- Primero se visita el nodo raíz, luego se recorre recursivamente en preorden el subárbol izquierdo y, por último, se recorre recursivamente en preorden el subárbol derecho.
- Aplicaciones: copiar un árbol, obtener la expresión prefija.
Recorrido en inorden (In-order):Izquierda -> Raíz -> Derecha
- Primero se recorre recursivamente en inorden el subárbol izquierdo, luego se visita el nodo raíz y, por último, se recorre recursivamente en inorden el subárbol derecho.
- Aplicaciones: en unárbol binario de búsqueda, el recorrido en inorden generaráen orden ascendentetodos los valores.
Recorrido en postorden (Post-order):Izquierda -> Derecha -> Raíz
- Primero se recorre recursivamente en postorden el subárbol izquierdo, luego se recorre recursivamente en postorden el subárbol derecho y, por último, se visita el nodo raíz.
- Aplicaciones: eliminar un árbol, calcular el tamaño de un directorio.
Recorrido por niveles (Level-order):Por niveles, de izquierda a derecha
- Comenzando desde el nodo raíz, se visitan los nodos nivel a nivel.
- Aplicaciones: procesar datos por niveles (por ejemplo, imprimir un organigrama).Normalmente se implementa con la ayuda de una cola (Queue)。

Ejemplo: para el árbol binario de la siguiente figura, los resultados de los recorridos son:
1
/ \
2 3
/ \ \
4 5 6
- Preorden:1, 2, 4, 5, 3, 6
- Inorden:4, 2, 5, 1, 3, 6
- Postorden:4, 5, 2, 6, 3, 1
- Por niveles:1, 2, 3, 4, 5, 6
Práctica: implementar un árbol binario en Python
¡Basta de teoría, pongámonos a escribir código! Implementaremos una clase sencilla de nodo de árbol binario y completaremos las operaciones de inserción y recorrido.
Paso 1: definir la clase Nodo
Cada nodo necesita almacenar datos y apuntar a sus nodos hijos izquierdo y derecho.
Ejemplo
"""Clase de nodo de árbol binario"""
def __init__(self, value):
self.value = value # Datos almacenados en el nodo
self.left = None # Apunta al nodo hijo izquierdo
self.right = None # Apunta al nodo hijo derecho
def __str__(self):
"""Para imprimir fácilmente la información del nodo"""
return f"Node({self.value})"
Paso 2: construir un árbol de ejemplo
Construyamos manualmente el árbol de la figura de ejemplo anterior.
Ejemplo
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
# Construir las relaciones de conexión (Links)
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.right = node6
print(f"Nodo raíz: {root}")
print(f"Hijo izquierdo del nodo raíz: {root.left}")
print(f"Hijo derecho del nodo raíz: {root.right}")
Paso 3: implementar algoritmos de recorrido (versión recursiva)
La recursión es la forma más intuitiva de implementar los recorridos de un árbol.
Ejemplo
"""Recorrido en preorden: raíz -> izquierda -> derecha"""
if node is None:
return
print(node.value, end=' ') # 1. Visitar el nodo raíz
preorder_traversal(node.left) # 2. Recorrer el subárbol izquierdo
preorder_traversal(node.right) # 3. Recorrer el subárbol derecho
def inorder_traversal(node):
"""Recorrido en inorden: izquierda -> raíz -> derecha"""
if node is None:
return
inorder_traversal(node.left) # 1. Recorrer el subárbol izquierdo
print(node.value, end=' ') # 2. Visitar el nodo raíz
inorder_traversal(node.right) # 3. Recorrer el subárbol derecho
def postorder_traversal(node):
"""Recorrido en postorden: izquierda -> derecha -> raíz"""
if node is None:
return
postorder_traversal(node.left) # 1. Recorrer el subárbol izquierdo
postorder_traversal(node.right) # 2. Recorrer el subárbol derecho
print(node.value, end=' ') # 3. Visitar el nodo raíz
print("\n--- Demostración de recorridos ---")
print("Resultado del recorrido en preorden:", end=' ')
preorder_traversal(root) # Salida: 1 2 4 5 3 6
print("\nResultado del recorrido en inorden:", end=' ')
inorder_traversal(root) # Salida: 4 2 5 1 3 6
print("\nResultado del recorrido en postorden:", end=' ')
postorder_traversal(root) # Salida: 4 5 2 6 3 1
Paso 4: implementar el recorrido por niveles (usando una cola)
El recorrido por niveles necesita apoyarse en la propiedad "primero en entrar, primero en salir" de la cola.
Ejemplo
def level_order_traversal(root):
"""Recorrido por niveles: usando una cola"""
if root is None:
return
queue = deque([root]) # Inicializar la cola y colocar el nodo raíz
while queue:
current_node = queue.popleft() # 1. Extraer el nodo del lado izquierdo de la cola
print(current_node.value, end=' ') # 2. Visitar el nodo
# 3. Agregar los nodos hijos (si existen) al lado derecho de la cola en orden
if current_node.left:
queue.append(current_node.left)
if current_node.right:
queue.append(current_node.right)
print("\nResultado del recorrido por niveles:", end=' ')
level_order_traversal(root) # Salida: 1 2 3 4 5 6
Ejercicios y desafíos
¡Felicidades por completar el aprendizaje básico! Para dominar realmente los árboles, la práctica es esencial.
Ejercicio 1: calcular la altura del árbol
Escribe una funcióntree_height(node)que reciba el nodo raíz de un árbol y devuelva la altura de este (la altura de un árbol vacío puede ser -1 o 0, según la convención; en este ejemplo la definimos como el número de aristas).
Pista: Altura del árbol = 1 + max(altura del subárbol izquierdo, altura del subárbol derecho). Este es un problema clásico de recursión.
Ejercicio 2: buscar un valor en el árbol binario
Escribe una funciónsearch_in_tree(node, target_value)que busque en el árbol binario dado si existe un nodo con valor igual atarget_value. Si lo encuentra, devuelveTrue; de lo contrario, devuelveFalse。
Pista: Puedes usar cualquiera de los métodos de recorrido y comparar su valor al visitar cada nodo.
Desafío: árbol de búsqueda binaria (BST)
Esta es una variante clásica del árbol binario. En un árbol binario de búsqueda, para cualquier nodo:
- suEl subárbol izquierdocontiene todos los nodos cuyos valores son menores que<el valor de ese nodo.
- suEl subárbol derechocontiene todos los nodos cuyos valores son mayores que>el valor de ese nodo.
Tu desafío es:
- Implementa
insert_into_bst(root, value)una función que inserte un valor en la posición correcta del árbol binario de búsqueda. - Implementa
search_in_bst(root, value)una función que aproveche las propiedades del BST para realizar una búsqueda eficiente (complejidad temporal promedio O(log N)).