Árboles B: Búsqueda

Aquí tenemos un árbol B de grado 3, sus nodos puede tener como mucho 3 hijos o dos claves.

De hecho en este ejemplo tenemos un gran ejemplo de esto en el nodo 65 - 82, que está completo, tiene sus 3 hijos y sus dos claves

La posible implementación del nodo en un lenguaje sería de la siguiente forma:

Para las diferentes claves usar una colección del lenguaje que sea indexable para acceder cómodamente a sus elementos

Algunos campos como en este ejemplo el grado, puede estar directamente en la clase que represente el árbol como tal.

El número de claves y el número de hijos nos ayuda a mantenernos siempre entre las condiciones vistas anteriormente del número mínimo de hijos o de claves

Búsqueda en Árboles B

Una búsqueda en un árbol b implica:

• Buscar entre las claves contenidas en este nodo.
• Si no lo encontramos, saltar al hijo en el que pueda estar
• Si el nodo es una hoja, el valor no esta.

Vamos a ver un ejemplo con este nodo de grado 8, que tiene 7 claves y 8 hijos y queremos buscar el valor 82.

Para encontrar el elemento se recorrerán las claves del propio nodo buscando ese valor, el tipo de recorrido en el ejemplo es lineal, pero puede ser binario o cualquiera que sea más óptimo

Una vez encontrado el elemento, podemos devolver el nodo en el que lo hemos encontrado, y en la posición <this, 5>

Al buscar por ejemplo el 74, al llegar al 82 habría que mirar en los hijos de la clave anterior, dado que el valor podría estar en uno de sus descendientes

Al buscar un elemento que sea mayor a todas las claves del nodo, lo que hay que hacer es mirar en el hijo derecho de la última clave, si el valor no está ahí, significa que no lo tenemos.

En el caso en el que el nodo no tenga hijos, al superar las claves con dicho valor, no hace falta seguir buscando dado que el valor no está presente.

En este caso al buscar el 71, cuando pasemos a la clave con valor 82, nos daremos cuenta que el valor no existe.

Búsqueda y presencia en pseudo-código

Aquí hay un pequeño ejemplo en pseudocódigo de cómo buscar un valor en un nodo dado, y el método exists para devolver un boolean en vez de una tupla(nodo, índice)

public Pair<Nodo, Integer> busqueda(Nodo nodo, int valor) {
    int i = 0;

    // Recorrer las claves mientras sean menores al valor buscado
    while (i < nodo.getNumeroClaves() && nodo.getClave(i) < valor) {
        i++;
    }

    // Si encontramos el valor en el nodo actual, lo devolvemos
    if (i < nodo.getNumeroClaves() && nodo.getClave(i) == valor) {
        return new Pair<>(nodo, i); // Retornar el nodo y el índice
    }

    // Si el nodo es hoja, el valor no está en el árbol
    if (nodo.esHoja()) {
        return new Pair<>(nodo, null); // Nodo encontrado pero sin índice
    } else {
        // Continuar la búsqueda en el hijo correspondiente
        return busqueda(nodo.getHijo(i), valor);
    }
}

public boolean presencia(Nodo nodo, int valor) {
    int i = 0;

    // Recorrer las claves mientras sean menores al valor buscado
    while (i < nodo.getNumeroClaves() && nodo.getClave(i) < valor) {
        i++;
    }

    // Si encontramos el valor en el nodo actual, devolver true
    if (i < nodo.getNumeroClaves() && nodo.getClave(i) == valor) {
        return true;
    }

    // Si el nodo es hoja, el valor no está en el árbol
    if (nodo.esHoja()) {
        return false;
    } else {
        // Continuar la búsqueda en el hijo correspondiente
        return presencia(nodo.getHijo(i), valor);
    }
}