Implementando un árbol de búsqueda binaria

Introducción

En este laboratorio, aprenderemos cómo implementar un Árbol de Búsqueda Binaria en Java. Un Árbol de Búsqueda Binaria es una estructura de datos de árbol binario en la que el valor de cada nodo es mayor o igual que los valores en su subárbol izquierdo y menor o igual que los valores en su subárbol derecho.

Skills Graph

Creando la clase BSTNode

En primer lugar, creemos una clase Java que represente el nodo de un árbol de búsqueda binaria y la llamemos BSTNode. Un nodo en un árbol de búsqueda binaria debe tener un valor y dos nodos hijos: uno a su izquierda y uno a su derecha.

class BSTNode {
    int value;
    BSTNode leftChild;
    BSTNode rightChild;

    BSTNode(int val) {
        this.value = val;
        this.leftChild = null;
        this.rightChild = null;
    }
}

Insertando elementos en el árbol de búsqueda binaria

Para insertar elementos en el árbol de búsqueda binaria, seguimos el siguiente algoritmo:

• Si el nuevo valor es menor que el valor del nodo actual, entonces recursivamente al hijo izquierdo.
• Si el nuevo valor es mayor que el valor del nodo actual, entonces recursivamente al hijo derecho.
• Si el nodo actual es nulo, entonces agregar el nuevo valor en esta posición.

public static BSTNode insert(int value, BSTNode current) {
    if (current == null) {
        BSTNode newNode = new BSTNode(value);
        return newNode;
    } else {
        if (value < current.value)
            current.leftChild = insert(value, current.leftChild);
        else
            current.rightChild = insert(value, current.rightChild);
    }
    return current;
}

Para probar este método, cree el árbol de búsqueda binaria e inserte algunos elementos:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Imprimir el árbol para verificar la inserción
    System.out.println("Recorrido después de la inserción: ");
    inorderTraversal(root);
}

// Función para recorrer el árbol en orden
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

Salida:

Recorrido después de la inserción:
5 7 9 12 20 21

Buscando un elemento en el árbol de búsqueda binaria

Para buscar un elemento en el árbol de búsqueda binaria, seguimos el siguiente algoritmo:

• Si el valor del nodo actual coincide con el valor que estamos intentando encontrar, entonces devolver true.
• Si el valor del nodo actual es mayor que el valor que estamos intentando encontrar, entonces recursivamente al hijo izquierdo.
• Si el valor del nodo actual es menor que el valor que estamos intentando encontrar, entonces recursivamente al hijo derecho.
• Si el nodo actual es nulo entonces devolver false.

public static boolean search(int key, BSTNode current) {
    if (current == null)
        return false;
    if (current.value == key)
        return true;
    else {
        if (key < current.value)
            return search(key, current.leftChild);
        else
            return search(key, current.rightChild);
    }
}

Para probar este método, busque algunos elementos:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Buscar elementos
    System.out.println(search(7, root));
    System.out.println(search(9, root));
    System.out.println(search(17, root));
}

Salida:

true
true
false

Eliminando un elemento de un árbol de búsqueda binaria

Eliminar un elemento de un árbol de búsqueda binaria es un poco más complejo que los pasos anteriores, ya que debemos manejar diferentes casos dependiendo del tipo de nodo:

• Si el nodo no tiene hijos (un nodo hoja), simplemente elimínalo.
• Si el nodo tiene un solo hijo, reemplázalo con su único hijo.
• Si el nodo tiene dos hijos, reemplázalo con el valor mínimo del subárbol derecho o el valor máximo del subárbol izquierdo.

public static BSTNode delete(int value, BSTNode current) {
    if (current == null)
        return current;
    if (value < current.value)
        current.leftChild = delete(value, current.leftChild);
    else if (value > current.value)
        current.rightChild = delete(value, current.rightChild);
    else if (value == current.value) {
        if (current.leftChild!= null && current.rightChild!= null) {
            int min = current.rightChild.value;
            BSTNode temp = current.rightChild;
            while (temp.leftChild!= null) {
                min = temp.leftChild.value;
                temp = temp.leftChild;
            }
            current.value = min;
            current.rightChild = delete(min, current.rightChild);
        } else if (current.leftChild == null)
            return current.rightChild;
        else if (current.rightChild == null)
            return current.leftChild;
    }
    return current;
}

Para probar este método, elimine algunos nodos e imprima el árbol:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Eliminar algunos nodos
    root = delete(12, root);
    root = delete(20, root);
    root = delete(9, root);

    // Imprimir el árbol para verificar la eliminación
    System.out.println("Recorrido después de la eliminación: ");
    inorderTraversal(root);
}

Salida:

Recorrido después de la eliminación:
5 7 21

Recorriendo el árbol de búsqueda binaria

Podemos recorrer un árbol de búsqueda binaria de diferentes maneras:

• Recorrido en orden (Izquierda-Raíz-Derecha)
• Recorrido preorden (Raíz-Izquierda-Derecha)
• Recorrido postorden (Izquierda-Derecha-Raíz)
• Recorrido por niveles (BFS)

public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

public static void preorderTraversal(BSTNode current) {
    if (current == null)
        return;
    System.out.print(current.value + " ");
    preorderTraversal(current.leftChild);
    preorderTraversal(current.rightChild);
}

public static void postorderTraversal(BSTNode current) {
    if (current == null)
        return;
    postorderTraversal(current.leftChild);
    postorderTraversal(current.rightChild);
    System.out.print(current.value + " ");
}

public static void levelOrderTraversal(BSTNode root) {
    Queue<BSTNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BSTNode temp = queue.poll();
        System.out.print(temp.value + " ");
        if (temp.leftChild!= null)
            queue.add(temp.leftChild);
        if (temp.rightChild!= null)
            queue.add(temp.rightChild);
    }
}

Para probar estos métodos, imprima el árbol utilizando cada técnica de recorrido:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    System.out.print("Recorrido en orden: ");
    inorderTraversal(root);
    System.out.print("\nRecorrido preorden: ");
    preorderTraversal(root);
    System.out.print("\nRecorrido postorden: ");
    postorderTraversal(root);
    System.out.print("\nRecorrido por niveles: ");
    levelOrderTraversal(root);
}

Salida:

Recorrido en orden: 5 7 9 12 20 21
Recorrido preorden: 12 7 5 9 20 21
Recorrido postorden: 5 9 7 21 20 12
Recorrido por niveles: 12 7 20 5 9 21

Resumen

En este laboratorio, hemos aprendido cómo crear, insertar elementos en, buscar un elemento en, eliminar un elemento de y recorrer un árbol de búsqueda binaria en Java.

Primero creamos la clase BSTNode que representa un nodo en el árbol de búsqueda binaria. Luego implementamos las funcionalidades de inserción, búsqueda y eliminación utilizando algoritmos específicos de los árboles de búsqueda binaria. Finalmente, aprendimos cómo recorrer el árbol de búsqueda binaria utilizando diferentes técnicas de recorrido como el recorrido en orden, preorden, postorden y el recorrido por niveles.

Con estos conceptos, deberías ser capaz de implementar árboles de búsqueda binaria en tus propios programas de Java.