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

  1. Ruta única: entre dos nodos cualesquiera de un árbol existe exactamente una única ruta.
  2. N nodos, N-1 aristas: un árbol con N nodos tiene un total de N-1 aristas.
  3. 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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

class TreeNode:
    """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

# Crear nodos
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

def preorder_traversal(node):
    """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

from collections import deque

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:

  1. Implementainsert_into_bst(root, value)una función que inserte un valor en la posición correcta del árbol binario de búsqueda.
  2. Implementasearch_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)).
Otras extensiones