SDK Multiplataforma en C logo

SDK Multiplataforma en C

Árboles binarios de búsqueda

❮ Anterior
Siguiente ❯

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

SetSt(type)*setst_create (...)
voidsetst_destroy (...)
uint32_tsetst_size (...)
type*setst_get (...)
const type*setst_get_const (...)
type*setst_insert (...)
bool_tsetst_delete (...)
type*setst_first (...)
const type*setst_first_const (...)
type*setst_last (...)
const type*setst_last_const (...)
type*setst_next (...)
const type*setst_next_const (...)
type*setst_prev (...)
const type*setst_prev_const (...)
voidsetst_foreach (...)
voidsetst_foreach_const (...)
voidsetst_fornext (...)
voidsetst_fornext_const (...)
voidsetst_forback (...)
voidsetst_forback_const (...)
voidsetst_forprev (...)
voidsetst_forprev_const (...)

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).

Listado 1: Creación de arrays y sets.
 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);
Representación de un conjunto de elementos en array y en un árbol de búsqueda.
Figura 1: Representación de arrays y sets.

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:

Esquema que muestra de inserción o borrado de un elemento en un árbol binario de búsqueda.
Figura 2: En árboles de búsqueda la inserción o borrado no rompe el orden del conjunto.
  • 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).
  • Comparativa de un árbol de búsqueda degenerado (a una lista) y balanceado.
    Figura 3: Árbol de búsqueda degenerado y balanceado.

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.
  • Comparativa de conjuntos de registros y conjuntos de punteros.
    Figura 4: Conjuntos de registros y 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):

Muestra el comportamiento de un puntero iterador dentro de un árbol de búsqueda.
Figura 5: Los iteradores nos permiten movernos por la estructura.
  • 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.
  • Listado 2: Iterando sobre los elementos de un 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.
  • Tabla 1: Resultados de la comparativa (en segundos).
    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);
func_compare

Función para comparar dos elementos. Ordenar y buscar.

type

Tipo de objeto.

Retorna

El nuevo set.


setst_destroy ()

Destruye un set y todos sus elementos.

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

El set. Será puesto a NULL tras la destrucción.

func_remove

Función que debe liberar la memoria asociada a los campos del objeto, pero no el objeto en si mismo Destructores. Si es NULL se liberará solo el set y no el contenido interno de los elementos.

type

Tipo de objeto.


setst_size ()

Obtiene el número de elementos del set.

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

El set.

type

Tipo de objeto.

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);
set

El set.

key

Clave a buscar. Es un puntero a un objeto donde solo los campos relevantes de la búsqueda deben ser inicializados.

type

Tipo de objeto.

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);
set

El set.

key

Clave a buscar.

type

Tipo de objeto.

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");
set

El set.

key

Clave a insertar. Es un puntero a un objeto donde solo los campos relevantes de la búsqueda deben ser inicializados.

type

Tipo de objeto.

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");
set

El set.

key

Clave a eliminar. Es un puntero a un objeto donde solo los campos relevantes de la búsqueda deben ser inicializados.

func_remove

Función 'remove'. Ver setst_destroy.

type

Tipo de objeto.

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);
set

El set.

type

Tipo de objeto.

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);
set

El set.

type

Tipo de objeto.

Retorna

Elemento.


setst_last ()

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

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

El set.

type

Tipo de objeto.

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);
set

El set.

type

Tipo de objeto.

Retorna

Elemento.


setst_next ()

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

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

El set.

type

Tipo de objeto.

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);
set

El set.

type

Tipo de objeto.

Retorna

Elemento.


setst_prev ()

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

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

El set.

type

Tipo de objeto.

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);
set

El set.

type

Tipo de objeto.

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)
elem

Nombre de la variable 'elemento' dentro del bucle. Añadiendo el sufijo '_i' obtenemos el índice.

set

El set.

type

Tipo de objeto.


setst_foreach_const ()

Versión const de setst_foreach.

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

Elemento.

set

El set.

type

Tipo de objeto.


setst_fornext ()

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

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

Nombre de la variable 'elemento'. Debe ser el mismo que setst_foreach.

set

El set.

type

Tipo de objeto.


setst_fornext_const ()

Versión const de setst_fornext.

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

Elemento.

set

El set.

type

Tipo de objeto.


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)
elem

Nombre de la variable 'elemento' dentro del bucle. Añadiendo el sufijo '_i' obtenemos el índice.

set

El set.

type

Tipo de objeto.


setst_forback_const ()

Versión const de setst_forback.

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

Elemento.

set

El set.

type

Tipo de objeto.


setst_forprev ()

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

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

Nombre de la variable 'elemento'. Debe ser el mismo que setst_forback.

set

El set.

type

Tipo de objeto.


setst_forprev_const ()

Versión const de setst_forprev.

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

Elemento.

set

El set.

type

Tipo de objeto.

❮ Anterior
Siguiente ❯