Cuando nos adentramos en el estudio de los Árboles B, es fundamental entender cómo se estructura cada nodo y cómo se realiza la operación de búsqueda dentro de ellos. En un Árbol B de grado 3, por ejemplo, cada nodo puede tener hasta tres hijos y dos claves. Visualizar un nodo completo, como el que contiene las claves 6 y 5 con sus tres hijos, nos ayuda a comprender que la estructura es recursiva: cada nodo apunta a subárboles que a su vez tienen sus propias raíces y descendientes, hasta llegar a nodos hoja sin hijos.
Para representar un nodo, podemos pensar en dos colecciones principales: un array de claves ordenadas y un array de punteros a hijos, que son otros nodos. En nuestros ejemplos, trabajaremos con arrays de enteros para las claves, pero podrían ser de cualquier tipo. Además, es útil almacenar el grado del nodo, que indica el máximo número de hijos que puede tener, así como el número actual de claves e hijos que contiene. Esto nos permite controlar que el nodo cumple con las restricciones del Árbol B, donde el número de claves y de hijos debe estar dentro de ciertos límites.
La operación de búsqueda en un Árbol B se basa en localizar un valor dentro de un nodo o, si no está presente, en buscar recursivamente en el hijo más adecuado. Dado un nodo y un valor, la búsqueda devuelve las coordenadas del valor dentro del nodo si se encuentra, o indica que no está presente. Para buscar dentro de un nodo, simplemente realizamos una búsqueda en el array de claves ordenadas. Si el valor no está, debemos decidir a qué hijo dirigirnos para continuar la búsqueda.
Aunque existen algoritmos más eficientes, para facilitar la comprensión podemos usar una búsqueda lineal en el array de claves. Esta consiste en recorrer las claves una a una hasta encontrar el valor o hasta que una clave sea mayor o igual al valor buscado. Al aprovechar que las claves están ordenadas, podemos detener la búsqueda tan pronto como encontremos una clave mayor que el valor, ya que no tiene sentido seguir buscando más allá.
Por ejemplo, si buscamos el valor 82 en un nodo con claves ordenadas, iteramos hasta encontrarlo en la posición correspondiente y devolvemos su ubicación. Si buscamos un valor como 74 que no está en el nodo, la búsqueda lineal nos indicará el punto donde deberíamos continuar, es decir, el hijo que contiene claves en el rango donde podría estar el 74. Así, la búsqueda se realiza recursivamente en ese hijo.
Un caso particular ocurre cuando buscamos un valor mayor que todas las claves del nodo. En ese caso, la búsqueda nos lleva al último hijo, que contiene todas las claves mayores que la última clave del nodo. Si llegamos a un nodo hoja y no encontramos el valor, concluimos que no está en el árbol.
Para implementar esta búsqueda, podemos usar un bucle while que recorra las claves hasta encontrar una clave mayor o igual al valor buscado, asegurándonos de no salirnos de los límites del array. Es importante controlar que el índice no supere el número de claves para evitar errores. Si encontramos el valor, devolvemos una tupla con el nodo y la posición. Si no, y el nodo tiene hijos, hacemos una llamada recursiva a la búsqueda en el hijo correspondiente. Si no hay hijos, devolvemos un valor que indique que no se encontró el elemento.
Este pseudocódigo refleja la lógica descrita:
función buscar(nodo, valor):
i = 0
mientras i < nodo.numClaves y nodo.claves[i] < valor:
i = i + 1
si i < nodo.numClaves y nodo.claves[i] == valor:
devolver (nodo, i) // Valor encontrado
si nodo.numHijos == 0:
devolver nulo // No encontrado en nodo hoja
devolver buscar(nodo.hijos[i], valor) // Búsqueda recursiva en hijo adecuado
Además, podemos derivar una función que solo indique la presencia o ausencia del valor, devolviendo true si se encuentra y false en caso contrario, simplificando los retornos.
Con esta base, tenemos una comprensión sólida de cómo se estructura un nodo en un Árbol B y cómo se realiza la búsqueda de manera recursiva, manejando cuidadosamente los casos base y los límites para evitar errores de índice. Esto nos prepara para abordar en próximas etapas operaciones como la inserción y el borrado en Árboles B.