Saltar al contenido principal

Árboles Binarios

Un árbol binario es una estructura de datos jerárquica donde cada nodo tiene como máximo dos hijos, denominados comúnmente como:

  • Hijo izquierdo (left)
  • Hijo derecho (right)

Los árboles binarios son la base para estructuras más complejas como árboles de búsqueda binaria, AVL, Red-Black, heaps, entre otros.

Propiedades del árbol binario​

ConceptoDefinición
Altura de un nodoDistancia desde ese nodo hasta la hoja más profunda.
Altura del árbolAltura de la raíz.
Nivel de un nodoNúmero de aristas desde la raíz hasta el nodo.
Nodo hojaNodo sin hijos.
Nodo internoNodo con al menos un hijo.
Árbol binario completoTodos los niveles completos excepto el último, que se llena de izquierda a derecha
Árbol binario perfectoTodos los niveles completamente llenos.
Árbol binario llenoTodos los nodos tienen 0 o 2 hijos.
Árbol binarioAltura de subárboles difiere como máximo en 1.

Tipos de recorrido (transversal)​

TipoOrden
InordenIzquierda → Raíz → Derecha
PreordenRaíz → Izquierda → Derecha
PostordenIzquierda → Derecha → Raíz
Por nivelesNivel por nivel (BFS)

Diagrama de clases​

El siguiente diagrama aplica para un árbol binario básico.

Ejemplo técnico​

BinaryNode.java
package domain;

public class BinaryNode {
    public int value;
    public BinaryNode left;
    public BinaryNode right;

    public BinaryNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
BinaryTree.java
package application;

import domain.BinaryNode;

public class BinaryTree {
    public BinaryNode root;

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private BinaryNode insertRec(BinaryNode node, int value) {
        if (node == null) return new BinaryNode(value);
        if (value < node.value) node.left = insertRec(node.left, value);
        else if (value > node.value) node.right = insertRec(node.right, value);
        return node;
    }

    public boolean search(int value) {
        return searchRec(root, value);
    }

    private boolean searchRec(BinaryNode node, int value) {
        if (node == null) return false;
        if (node.value == value) return true;
        return value < node.value ? searchRec(node.left, value) : searchRec(node.right, value);
    }

    public void inOrder() {
        inOrderRec(root);
        System.out.println();
    }

    private void inOrderRec(BinaryNode node) {
        if (node != null) {
            inOrderRec(node.left);
            System.out.print(node.value + " ");
            inOrderRec(node.right);
        }
    }

    public void preOrder() {
        preOrderRec(root);
        System.out.println();
    }

    private void preOrderRec(BinaryNode node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preOrderRec(node.left);
            preOrderRec(node.right);
        }
    }

    public void postOrder() {
        postOrderRec(root);
        System.out.println();
    }

    private void postOrderRec(BinaryNode node) {
        if (node != null) {
            postOrderRec(node.left);
            postOrderRec(node.right);
            System.out.print(node.value + " ");
        }
    }

    public void delete(int value) {
        root = deleteRec(root, value);
    }

    private BinaryNode deleteRec(BinaryNode node, int value) {
        if (node == null) return null;

        if (value < node.value) {
            node.left = deleteRec(node.left, value);
        } else if (value > node.value) {
            node.right = deleteRec(node.right, value);
        } else {
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;

            BinaryNode minRight = findMin(node.right);
            node.value = minRight.value;
            node.right = deleteRec(node.right, minRight.value);
        }
        return node;
    }

    private BinaryNode findMin(BinaryNode node) {
        while (node.left != null) node = node.left;
        return node;
    }
}

Aplicaciones Reales​

  • Árboles de decisión (IA, ML).
  • Árboles de expresión en compiladores.
  • Representación de bases de datos jerárquicas.
  • Autocompletado y búsqueda.
  • Indexación binaria (BST).
  • Representación de expresiones matemáticas.

Referencias​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
  • Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.
  • Weiss, M. A. (2020). Data Structures and Algorithm Analysis in Java (4th ed.). Pearson.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.