Vamos a prestar especial atención a los árboles binarios de búsqueda, ya que son muy populares y ampliamente utilizados en BBDD. Como ya adelantaba en el post anterior, los arboles binarios son de orden 2, es decir, sus nodos pueden tener un máximo de dos hijos. Y si además es de búsqueda, tiene que cumplir las siguientes condiciones para todos los nodos:

  • Si el nodo tiene un hijo izquierdo, este tiene que ser menor que él.
  • Si el nodo tiene un hijo derecho, este tiene que ser mayor que él.

Esto obliga a que los datos que estemos guardando sean ordenables, podamos determinar claramente si uno es mayor o menor que otro. Dadas las condiciones de arriba que tienen que cumplir los arboles binarios de búsqueda, no se admiten duplicados, tienen que ser datos únicos.

Para entenderlo, veámoslo con un ejemplo sencillo en el que los datos serán números enteros. Un posible árbol binario de búsqueda sería:

Diagrama de árbol binario

Puede observarse que el nodo raíz guarda el valor 55 y tiene dos hijos: el izquierdo (53) , menor que el padre, y el derecho (59) mayor que el padre. Si recorremos el resto del árbol a través de sus nodos veremos que todos cumplen la condición establecida anteriormente, de que el hijo izquierdo sea menor y el derecho mayor.

Ejemplo de árbol binario de búsqueda

Veamos como funcionarían los árboles binarios de búsqueda en el caso del fichero de proveedores de nuestro amigo Antonio.

Paso 1: El fichero de partida.

El fichero de proveedores de Antonio y la estructura de índice que nos habíamos creado era la siguiente:

Fichero de partida

La clave que utilizamos para indexar era el nombre de proveedor, a partir de la cual obteníamos la dirección en memoria de todo el bloque de datos del proveedor correspondiente. Pues bien, ahora toca organizar esa tabla como un árbol binario de búsqueda.

Paso 2: Crear el árbol binario de búsqueda:

Nuestro fichero de proveedores tiene 1.000 registros, pero en este ejercicio, vamos a usar únicamente los 7 que he escrito, para mantener la complejidad controlada y poder presentar gráficamente el árbol binario. Seguro que no se os escapa que un árbol binario de 1.000 nodos resulta un poco complicado de pintar.

Cada par clave – dirección sería un nodo. La clave el nombre del proveedor y la dirección donde podemos encontrar todos los datos del proveedor identificado por la clave.

Lo primero que vamos a tener que hacer es añadir a los datos por nodos, proveedor y dirección, otros dos datos, dos punteros, uno que apunte al nodo hijo izquierdo y otro que apunte al nodo hijo derecho. Un puntero es una variable que apunta a una dirección de memoria. En realidad, la variable dirección que apunta al bloque de datos del proveedor es un puntero.

De esta forma, la estructura de un nodo de nuestro árbol binario de búsqueda queda con los siguientes parámetros:

  • clave: Nombre del proveedor.
  • Dirección: puntero al bloque de datos del proveedor.
  • Izqdo: puntero al hijo izquierdo del nodo
  • Dcha: puntero al hijo derecho del nodo.

La representación de nuestro árbol binario de búsqueda quedaría:

Representación de árbol binario de búsqueda

Podemos observar que el árbol cumple con las condiciones de árbol binario de búsqueda: para cualquier nodo, su hijo izquierdo es menor que él, y su hijo derecho es mayor, caso de tener uno u otro. Hemos podido construir el árbol porque los valores de los nodos (nombre de proveedores) son ordenables y  no admiten duplicados.

En el caso de que un nodo no tenga hijo izquierdo, el puntero Izqdo de ese nodo sería null. De idéntica forma, si no tiene hijo derecho, el puntero Dcha de ese nodo sería null.

La estructura de un nodo, podría expresarse de la siguiente manera:

Nodo{

Nombre proveedor (texto)

Dirección (puntero)

Izqdo (puntero)

Dcha (puntero)

}

Con este seudocódigo pretendo sencillamente mostrar la estructura, colocando entre paréntesis el tipo de dato.

Siguiendo esta estructura, podríamos definir el árbol de manera recursiva de la siguiente forma:

Árbol{

Nombre proveedor Nodo raíz (texto)

Dirección proveedor Nodo raíz (puntero)

Árbol hijo izquierdo (puntero a árbol)

Árbol hijo derecho (puntero a árbol)

}

En otras palabras, podemos considerar los dos nodos hijos como las raíces de dos nuevos arboles binarios de búsqueda.

Paso 3: Llevando todos los datos al árbol binario

El árbol binario que hemos visto en el paso anterior, no es más que una estructura de datos que almacena un valor o clave y tres punteros. La clave que habíamos escogido para ordenar el árbol y que será la que empleemos para buscar un proveedor, es el nombre de proveedor, una clave que puede ser ordenada y que no admite duplicados. Luego teníamos los punteros Izqdo y Dcha, que forman parte de la estructura del árbol, y el puntero dirección, que apunta a la zona de memoria donde están todos los datos del proveedor.

Los datos de esta estructura los vamos a tener en la memoria del Sistema, en la RAM, por lo que la búsqueda en el árbol binario será bastante rápida. Sin embargo, cuando encontremos el proveedor buscado, para acceder a sus datos tendremos que ir a la memoria secundario, seguramente en el disco duro, a la posición que apunta el puntero dirección. Este último acceso será más lento.

Pues bien, si los datos de proveedor no ocupan mucha memoria, y no tenemos muchos proveedores, es posible que nos entrara toda la información en la memoria del Sistema, y que de esta forma pudiéramos trabajar directamente con todos los datos en la RAM, sin tener que acceder al disco duro.

Nuestro nuevo árbol binario de búsqueda, para los datos de proveedores, quedaría:

Arbol binario de búsqueda con los datos de los proveedores

Y la estructura del árbol expresada en seudocódigo sería:

Árbol{

Nombre proveedor Nodo raíz (texto)

Contacto proveedor Nodo raíz (texto)

Teléfono proveedor Nodo raíz (texto)

Árbol hijo izquierdo (puntero a árbol)

Árbol hijo derecho (puntero a árbol)

}

Paso 4: Nivel del árbol binario:

Antonio tiene un fichero de proveedores con  1.000 proveedores registrados. Y quiere llevarlo todo a una estructura de árbol binario de búsqueda.

¿Qué nivel mínimo tendría que alcanzar el árbol binario?

Solución:

Se necesitaría hasta el nivel 9.

Tenemos que considerar que el árbol está equilibrado, puesto que pregunta por el nivel mínimo, es decir, la mínima profundidad.

Sabiendo que la raíz es considerada el nivel 0, y que en un nivel, si lo tenemos completo, tendríamos: 2^nivel nodos.

Nos construimos la tabla siguiente:

Tabla de niveles y nodos de un árbol binario equilibrado

Donde vemos que tenemos que llegar al menos al nivel 9 para poder tener 1.000 nodos en nuestro árbol.

NOTA:

Este post es parte de la colección “Arquitectura de Datos” que reproduce los apuntes de la clase que imparto sobre el tema en ESIC. Puedes ver el índice de esta colección aquí.