Árbol binario de búsqueda – Estructura, inserción y eliminación

¿Qué es un árbol binario de búsqueda?

Un árbol binario de búsqueda es una estructura de datos arborescente donde cada nodo tiene asociado una clave (1, 2, 3, 4, etc.). Los nodos de estos árboles se organizan de la siguiente forma.

Para todo nodo del árbol que no sea una hoja:

• Todas las claves del subárbol izquierdo son más pequeñas que la del nodo.
• Todas las claves del subárbol derecho son más grandes que la del nodo.
• El subárbol izquierdo también es un ABB
• El subárbol derecho también es un ABB

Veamos un ejemplo:

No debemos olvidar que el objetivo de el ABB es almacenar datos de forma ordenada. Por eso, lo que se hace es asociar a cada clave un valor, es decir, una información a guardar. Entonces, mediante la clave podremos acceder a su valor asociado. Con esta estructura de datos podremos buscar, añadir y eliminar estos valores asociados a una clave de forma eficiente.

En este árbol, por ejemplo, podríamos acceder a los nombres de una persona mediante su clave identificadora.

Operaciones de un árbol binario de búsqueda

A la hora de operar sobre esta estructura arborescente será crucial, siempre que la modifiquemos, que se siga manteniendo su estructura fundamental. Para ello existen los algoritmos que te explico a continuación.

Búsqueda

La búsqueda consistirá en encontrar la clave que nos pidan en el árbol. Conociendo su estructura, lo único que tendremos que hacer será situarnos en la raíz y mirar si la clave que estamos buscando es más pequeña o más grande. Si es más pequeña, nos moveremos al hijo izquierdo. Por otro lado, si es más grande, nos moveremos al hijo derecho. Repetiremos el proceso hasta encontrar la clave o llegar a una hoja. Este último caso implicará que la clave no se encuentra en el árbol.

EJEMPLO: Búsqueda del 6.

Nos situamos en la raíz y comparamos con la clave que buscamos.

La clave 6 era más pequeña, en consecuencia, nos hemos movido al hijo izquierdo para comparar nuevamente.

Nuestra clave ahora era mayor, por lo tanto, nos desplazamos al hijo derecho.

Inserción

Para insertar una nueva clave será fundamental colocarla en una posición en la que no afecte a la estructura del árbol binario de búsqueda. Para lograrlo, usaremos un algoritmo similar al anterior. Primero, nos situaremos en la raíz. Si la clave a insertar es menor que la clave de la raíz, nos moveremos al subárbol izquierdo. Si la clave a añadir es mayor, nos desplazaremos al subárbol derecho. Este proceso lo repetiremos hasta encontrar un nodo del cual pueda colgar la nueva clave.

EJEMPLO: Insertar clave 3 al siguiente árbol:

Este sería el resultado final:

Fíjate como según vamos comparando nos movemos a la izquierda (clave < nodo) o a la derecha (clave > nodo). Como el nodo 1 no tiene hijo derecho podemos insertar la clave 3 allí y, efectivamente, se sigue manteniendo la estructura.

Eliminación

La eliminación de una clave en un árbol binario de búsqueda es la operación más compleja. Este hecho se debe a que según el nodo que eliminemos, deberemos hacer una cosa u otra. Tenemos 4 casos:

• CASO 1: la clave no está en el árbol –> no hacemos nada
• CASO 2: la clave está en una hoja (nodo sin hijos) –> eliminamos el nodo
• CASO 3: la clave se encuentra en un nodo con un hijo –> eliminamos el nodo y lo sustituimos por su hijo
• CASO 4: la clave se encuentra en un nodo con dos hijos –> eliminamos el nodo y lo sustituimos por el mayor del subárbol izquierdo o por el menor del subárbol derecho

Te enseño un ejemplo para cada caso. Para ello operaremos sobre el siguiente árbol:

EJEMPLO 1: la clave no existe.

EJEMPLO 2: la clave se encuentra en una hoja.

EJEMPLO 3: la clave se encuentra en un nodo con un único hijo.

EJEMPLO 4: la clave se encuentra en un nodo con dos hijos.

Implementaciones

Para comprender bien los árboles binarios de búsqueda, es un buen ejercicio intentar implementarlos en el lenguaje que estés estudiando. En esta sección te muestro una posible implementación en Java y te recomiendo ciertos artículos y vídeos por si te interesan más otros lenguajes.

Árbol binario de búsqueda Java

El proyecto que hemos creado define una interfície BinarySearchTree<K, V> que será implementada en la clase LinkedBinarySearchTree<K, V>. Además, tenemos una clase Main que si la ejecutamos, interactuaremos con un menú en el que se pueden añadir claves, eliminarlas, obtener el valor asociado a una clave y mostrar el árbol en preorden.

Si quieres descargar el proyecto, te dejo aquí este enlace a GitHub.

Explicación de la implementación

Primero de todo, hemos diseñado la interfície BinarySearchTree<K, V> pensando los métodos que podrían resultarnos útiles.

public interface BinarySearchTree<K extends Comparable<? super K>, V> {
    LinkedBinarySearchTree<K, V> left();
    LinkedBinarySearchTree<K, V> right();
    void add(K key, V value);
    boolean isEmpty();
    void remove(K key);
    K getRoot();
    V getValue(K key);
    int size();
}

• left(): devuelve el subárbol izquierdo
• right(): devuelve el subárbol derecho
• getValue(K key): devuelve el valor asociado a una clave
• getRoot(): devuelve la raíz del árbol
• add(K key, V value): añade la pareja (clave, valor) al árbol
• remove(K key): elimina la clave
• isEmpty(): devuelve True si está vació
• size(): devuelve el número de claves en el árbol

Para poder implementar todos estos métodos, la solución por la que se ha optado ha sido en diseñar nodos con su clave y valor y, además, apuntadores a su hijo izquierdo, derecho y al padre. En este diagrama se ve reflejada la idea:

La clase interna Node<K, V> de LinkedBinarySearchTree<K, V> será la que nos permitirá crear estos objetos.

private static class Node<K extends Comparable<? super K>, V> {
        private final K key;
        private V value;
        private Node<K, V> left;
        private Node<K, V> right;
        private Node<K, V> parent;

        Node(Node<K, V> left, K key, V value, Node<K, V> right, Node<K, V> parent) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }

Finalmente, solo nos queda diseñar el árbol. En este caso, se ha decidido que un árbol se defina a partir de su raíz, es decir, el nodo del cual cuelgan todos los hijos. En este diagrama puedes verlo:

Si lo traducimos a código:

public class LinkedBinarySearchTree<K extends Comparable<? super K>, V>
        implements BinarySearchTree<K, V> {

    private Node<K, V> root;

    public LinkedBinarySearchTree() {
        this.root = null;
    }
    // implementación de métodos
}

Puedes observar que fuera de la clase solo se podrán crear árboles vacíos. Entonces, ¿cómo insertaremos los nodos? Pues mediante el método add que implementaremos. Si quieres entrar más en detalle para ver cómo se ha programado cada método, recuerda que todo el código está en este repositorio de Github. Aún así, si de verdad estás interesado, te recomiendo que te rompas la cabeza para programarlo tú mismo, tal y como yo he hecho.

Otros lenguajes

Te dejo aquí más información sobre árboles binarios de búsqueda en lenguajes como Javascript, C++ y Python.

• Javascript: Implementación del árbol de búsqueda binaria en Javascript
• C++: Vídeos Programación ATS (del 112 al 122)
• Python: Árbol binario de búsqueda – Estructura de datos en Python

Ejercicios resueltos de árboles binarios de búsqueda

Ejercicio 1: construir árbol binario de búsqueda

Dada la secuencia de claves 17-10-25-3-6-16-39-5-1-20, construye el árbol binario de búsqueda.

SOLUCIÓN:

Ejercicio 2: insertar y eliminar en un árbol de búsqueda binario

Partiendo siempre de este árbol:

Realiza las siguientes operaciones:

• INSERTAR 20
• ELIMINAR 14

SOLUCIÓN:

• INSERTAR 20

• ELIMINAR 14

Ejercicio 3: recursividad en árbol binario de búsqueda

En Java, diseña un método recursivo ‘suma’ que recibirá dos parámetros: un BinarySearchTree<Integer, Integer> y un entero. Este método deberá devolver la suma de los nodos que tengan una clave menor que el entero pasado como parámetro. Puedes usar los siguientes métodos:

public interface BinarySearchTree<K extends Comparable<? super K>, V> {
    LinkedBinarySearchTree<K, V> left();
    LinkedBinarySearchTree<K, V> right();
    void add(K key, V value);
    boolean isEmpty();
    void remove(K key);
    K getRoot();
    V getValue(K key);
    int size();
}

**Recuerda usar las propiedades del árbol binario de búsqueda para descartar llamadas recursivas innecesarias**

SOLUCIÓN:

static int suma(BinarySearchTree<Integer, Integer> tree, int num) {
    if (tree.isEmpty()) {
        return 0;
    } else {
        if (tree.getRoot() < num) {
            return tree.getRoot() + suma(tree.left(), num) + suma(tree.right(), num);
        } else {
            // ¡NO ES NECESARIO IR A LA DERECHA YA QUE num SIEMPRE SERÁ MÁS GRANDE!
            return suma(tree.left(), num);
        }
    }
}