Árboles binarios de búsqueda

Contenedor de datos donde los elementos se almacenan en forma de árbol binario, optimizando las búsquedas, inserciones o borrados. Para conjuntos de punteros consultar Árboles binarios de búsqueda (punteros).

Funciones

Al igual que los array los binary search trees (BST), también conocidos como conjuntos (set) o mapas (map), son contenedores que nos permiten trabajar con una colección de objetos. La principal diferencia con respecto a los primeros es que los elementos no se almacenan de forma lineal en posiciones contiguas de memoria, sino que utilizan una estructura en forma de árbol donde cada nodo tiene dos descendientes (Listado 1) (Figura 1).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

typedef struct _product_t Product;
struct _product_t
{
    type_t type;
    String *code;
    String *description;
    Image *image64;
    real32_t price;
};

static int i_compare(const Product *p1, const Product *p2)
{
    return str_scmp(p1->code, p2->code);
}

ArrSt(Product) *arrst = arrst_create(Product);
ArrPt(Product) *arrpt = arrpt_create(Product);
SetSt(Product) *setst = setst_create(i_compare, Product);
SetPt(Product) *setpt = setpt_create(i_compare, Product);

Los BST son estructuras optimizadas para casos donde sean muy frecuentes las inserciones, borrados y búsquedas. Están permanentemente ordenados, de ahí que sea posible insertar, eliminar o localizar cualquier elemento en tiempo logarítmico O(logn), sin necesidad de utilizar funciones de ordenación como arrst_sort (Figura 2). Para que el mantenimiento se pueda llevar a cabo de forma eficiente, el árbol que soporta la estructura debe cumplir una serie de características:

• Binario: Cada nodo solo puede tener 0, 1 ó 2 hijos.
• Ordenado: Todos los descendientes a la izquierda de un nodo son de menor valor y los situados a la derecha de mayor valor. El criterio de orden y búsqueda se establece en el constructor mediante una función de comparación (i_compare en el ejemplo anterior) y no se puede cambiar durante el tiempo de vida del contenedor. Los nuevos elementos se insertarán en su posición correcta conforme a este orden. No soporta elementos duplicados ni en posiciones arbitrarias.
• Balanceado: Un árbol puede cumplir las dos propiedades anteriores, pero haber degenerado a una lista donde las búsquedas ya no pueden resolverse en tiempo logarítmico (Figura 3). Internamente, los contenedores Set de NAppGUI están implementados con los llamados árboles rojo-negro, donde se garantiza una altura máxima de 2log(n+1). Esto se consigue reestructurando el árbol después de cada inserción o borrado, por lo que añadir un nuevo elemento (o eliminarlo) se resuelve en un máximo de O(logn). Esto es muchísimo más rápido que en arrays, donde hay que desplazar todos los elementos para insertar un registro en una posición concreta, con un coste asociado de O(n).

Como ya vimos en Registros o punteros, tenemos dos modalidades a la hora de crear conjuntos (Figura 4). La versión basada en registros es más eficiente que la basada en punteros, aunque menos flexible.

• Utiliza setst_create para crear un conjunto de registros.
• Utiliza setpt_create para crear un conjunto de punteros.

1. Iteradores

No podemos acceder a los elementos de un set mediante un índice aleatorio, como ocurría con los arrays. Los nodos están dispersos en diferentes zonas de memoria, lo que impide calcular la posición de un elemento concreto a partir de una dirección base. Un iterador no es más que un puntero dentro del set que actúa como marcador del elemento seleccionado actualmente (Figura 5). A partir de una posición concreta, podemos desplazarnos al elemento anterior o posterior, pero nunca dar saltos arbitrarios. Podemos controlar la posición del iterador con diferentes funciones (Listado 2):

• Utiliza setst_get para buscar un elemento. El iterador quedará fijado en él.
• Utiliza setst_next para desplazar el iterador al siguiente elemento.
• Utiliza setst_prev para desplazar el iterador al elemento anterior.
• Utiliza setst_first para desplazar el iterador al primer elemento del set.
• Utiliza setst_last para desplazar el iterador al último elemento del set.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

const Product *product = setst_first(setst, Product); while (product != NULL) { // Do something ... product = setst_next(setst, Product); } setst_foreach(product, setst, Product) // Do something ... setst_fornext(product, setst, Product) // In reverse order setst_forback(product, setst, Product) // Do something ... setst_forprev(product, setst, Product)

2. Comparativa Arrays vs Sets

Hemos realizado un test para ver el comportamiento de estos dos tipos de estructuras en situaciones reales, al margen de la mera teoría (Tabla 1). Se ha utilizado la estructura Product descrita en (Listado 1). Compararemos seis tipos de contenedores ArrSt(Product) y ArrPt(Product) (desordenados), ArrSt(Product) y ArrPt(Product) (ordenados), SetSt(Product) y SetPt(Product).

• Los elementos se ordenarán por el campo code utilizando el método i_compare descrito en (Listado 1).
• Los elementos han sido creados previamente y residen en memoria. Los tiempos solo reflejan la gestión realizada por los contenedores.
• El campo code toma valores desde "0" hasta "n-1", donde n=100.000 es el número de elementos. Los elementos han sido previamente desordenados utilizando la función bmem_shuffle_n.
• Las pruebas se han realizado en una Raspberry Pi 3 Model B con NAppGUI compilado en versión Release (Configuraciones). Hemos elegido esta plataforma por su clara inferioridad técnica con respecto a otras. De esta forma la diferencia asintótica resulta más evidente.

Operation	ArrSt	ArrPt	ArrSt-Sort	ArrPt-Sort	SetSt	SetPt
Add(100k)	0.006	0.004	27.600	2.896	0.159	0.274
Loop(100k)	0.000	0.000	0.000	0.000	0.022	0.025
Search(100k)	84.139	588.080	0.101	0.218	0.121	0.232
Sort(100k)	0.085	0.205	-	-	-	-
Delete(100k)	0.004	0.003	31.198	3.064	0.171	0.253

A la vista de estos datos, podemos llegar a las siguientes conclusiones:

• Las búsquedas lineales O(n) son tremendamente lentas.
• Mantener un array ordenado tras cada inserción o borrado es costoso. Es más eficiente añadir todos los elementos y luego ordenar, aunque esto no siempre será posible. Si los elementos entran o salen de forma arbitraria pero el conjunto debe siempre estar ordenado, es mejor utilizar Sets.
• Las estructuras basadas en registros son más eficientes en consultas, pero menos al insertar o borrar. No obstante, este test no incluye el tiempo de crear o liberar memoria dinámica, algo inherente a los contenedores de punteros.
• Iterar en arrays sale prácticamente gratis, pero iterar en sets tiene un pequeño coste debido a la lógica de salto entre nodos.
• No podemos decir que un contenedor sea mejor que otro en general. Dependerá de cada caso concreto.
• Para grupos pequeños (menos de 1000 elementos) las diferencias son prácticamente imperceptibles.
• Para grupos extremadamente pequeños (hasta 100 elementos) utilizar siempre arrays. La mejora asintótica de los Sets se ve empañada por la implementación mucho más eficiente de los Arrays.

setst_create ()

Crea un set de registros vacío.

SetSt(type)*
setst_create(FPtr_compare func_compare,
             type);

Retorna

El nuevo set.

setst_destroy ()

Destruye un set y todos sus elementos.

void
setst_destroy(SetSt(type) **set,
              FPtr_remove func_remove,
              type);

setst_size ()

Obtiene el número de elementos del set.

uint32_t
setst_size(const SetSt(type) *set,
           type);

Retorna

Número de elementos.

setst_get ()

Busca un elemento en O(logn). Es equivalente a arrst_bsearch. Si existe, el iterador interno de la estructura quedará fijado en él.

type*
setst_get(SetSt(type) *set,
          const type *key,
          type);

1
2
3
4

Product key;
Product *pr;
key.id = 453;
pr = setst_get(setst, &key, Product);

Retorna

Puntero al elemento si existe, o NULL si no.

Observaciones

Iteradores.

setst_get_const ()

Versión const de setst_get.

const type*
setst_get_const(const SetSt(type) *set,
                const type *key,
                type);

Retorna

Elemento.

setst_insert ()

Inserta un nuevo elemento en el set.

type*
setst_insert(SetSt(type) *set,
             type *key,
             type);

1
2
3
4
5
6
7
8

Product *pr;
Product key;
key.id = 345;
pr = setst_insert(setst, &key, Product);
if (pr != NULL)
    i_init(pr, 345, 100.45f);
else
    error("Already exists");

Retorna

Puntero al elemento insertado, que debe utilizarse para inicializar el objeto. Si ya existe un elemento con la misma clave, retorna NULL.

Observaciones

Insertar o eliminar elementos invalida el iterador interno del set Iteradores. Debes volver a inicializarlo con setst_first.

setst_delete ()

Elimina un elemento del set.

bool_t
setst_delete(SetSt(type) *set,
             type *key,
             FPtr_remove func_remove,
             type);

1
2
3
4

Product key;
key.id = 345;
if (setst_delete(setst, &key, product_remove, Product) == FALSE)
    error("Doesn't exists");

Retorna

TRUE si el elemento ha sido eliminado, o FALSE si no existe un elemento con dicha clave.

Observaciones

Insertar o eliminar elementos invalida el iterador interno del set Iteradores. Debes inicializarlo con setst_first.

setst_first ()

Obtiene el primer elemento del set e inicializa el iterador interno.

type*
setst_first(SetSt(type) *set,
            type);

Retorna

Puntero al primer elemento o NULL si el set está vacío.

Observaciones

Iteradores.

setst_first_const ()

Versión const de setst_first.

const type*
setst_first_const(const SetSt(type) *set,
                  type);

Retorna

Elemento.

setst_last ()

Obtiene el último elemento del set e inicializa el iterador interno.

type*
setst_last(SetSt(type) *set,
           type);

Retorna

Puntero al último elemento o NULL si el set está vacío.

Observaciones

Iteradores.

setst_last_const ()

Versión const de setst_last.

const type*
setst_last_const(const SetSt(type) *set,
                 type);

Retorna

Elemento.

setst_next ()

Obtiene el siguiente elemento del set, tras incrementar el iterador interno.

type*
setst_next(SetSt(type) *set,
           type);

Retorna

Puntero al siguiente elemento o NULL si el iterador ha alcanzado el último.

Observaciones

Utiliza setst_first para inicializar el iterador interno Iteradores.

setst_next_const ()

Versión const de setst_next.

const type*
setst_next_const(const SetSt(type) *set,
                 type);

Retorna

Elemento.

setst_prev ()

Obtiene el elemento anterior del set, tras decrementar el iterador interno.

type*
setst_prev(SetSt(type) *set,
           type);

Retorna

Puntero al elemento anterior o NULL si el iterador ha alcanzado el primero.

Observaciones

Utiliza setst_last para inicializar el iterador interno en bucles revertidos Iteradores.

setst_prev_const ()

Versión const de setst_prev.

const type*
setst_prev_const(const SetSt(type) *set,
                 type);

Retorna

Elemento.

setst_foreach ()

Recorre todos los elementos del set. Utiliza setst_fornext para cerrar el bucle.

void
setst_foreach(type *elem,
              SetSt(type) *set,
              type);

1
2
3

setst_foreach(product, set, Product)
    bstd_printf("Position:%d, Id:%d\n", product_i, product->id);
setst_fornext(product, set, Product)

setst_foreach_const ()

Versión const de setst_foreach.

void
setst_foreach_const(const type *elem,
                    const SetSt(type) *set,
                    type);

setst_fornext ()

Cierra el bucle abierto por setst_foreach, incrementando el iterador interno.

void
setst_fornext(type *elem,
              SetSt(type) *set,
              type);

setst_fornext_const ()

Versión const de setst_fornext.

void
setst_fornext_const(const type *elem,
                    const SetSt(type) *set,
                    type);

setst_forback ()

Recorre todos los elementos del set en orden inverso. Utiliza setst_forprev para cerrar el bucle.

void
setst_forback(type *elem,
              SetSt(type) *set,
              type);

1
2
3
4

// Now in reverse order
setst_forback(product, set, Product)
    bstd_printf("Position:%d, Id:%d\n", product_i, product->id);
setst_forprev(product, set, Product)

setst_forback_const ()

Versión const de setst_forback.

void
setst_forback_const(const type *elem,
                    const SetSt(type) *set,
                    type);

setst_forprev ()

Cierra el bucle abierto por setst_forback, decrementando el iterador interno.

void
setst_forprev(type *elem,
              SetSt(type) *set,
              type);

setst_forprev_const ()

Versión const de setst_forprev.

void
setst_forprev_const(const type *elem,
                    const SetSt(type) *set,
                    type);