[C con Clase] Insertar en un árbol binario de búsqueda

[salvador en conclase.net]

El pasado 2012-06-06 21:57:45, User escribió:
 
U> Hola,
U> He visto el siguiente prototipo para la función en C de insertar en un
U> árbol binario de búsqueda:
U> int insertarDato(void * nuevoDato, ArbolBB** ParbolBB, int
U> (*fCompara)(void*, void*));
U> No entiendo bien la finalidad del último parámetro. Ni tampoco por qué usa
U> un doble puntero en ArbolBB.

Hola:
El último parámetro es un puntero a una función que, viendo el nombre y los argumentos que tiene, compara dos valores y retorna un entero. La regla general para este tipo de funciones es retornar un valor menor que cero si el primer parámetro es menor que el segundo, cero si son iguales y un valor mayor que cero si el primero es mayor que el segundo.

Supongo que esa función se usa para establecer el orden dentro del árbol ABB, de modo que el nuevo dato se inserte en la posición correcta.

El uso del doble puntero en el segundo parámetro es necesario. Hay que tener en cuenta que un ArbolBB se puede definir de dos modos. Una, que es la que yo prefiero es un puntero a un nodo. Es decir, cada puntero a un nodo es, o puede ser, la raíz de un árbol completo.

Según esto, la definición del tipo arbolBB debería ser:

typedef struct TNodo* ArbolBB;

y la de la función de inserción:

int insertarDato(void * nuevoDato, ArbolBB* ParbolBB, 
   int (*fCompara)(void*, void*));

La otra forma es la de tu ejemplo, en la que la definición de ArbolBB es igual que la del nodo, y por lo tanto, el puntero al ArbolBB se convierte en un puntero doble en la función de inserción. Lo malo de esta forma es que para manejar los árboles necesitarás punteros a ArbolBB, lo cual puede ser bastante equívoco.

En cualquier caso, se necesita un puntero doble. Si partimos de la primera definición para ArbolBB, pasaremos un puntero a nuestro árbol porque tenemos que tener en cuenta que el nuevo dato puede ocupar la posición de la raíz del árbol después de insertarlo. Esto ocurrirá cuando insertemos un dato en un árbol vacío. Si sólo pasamos como parámetro el ArbolBB, por copia, los cambios que hagamos en ese caso no se transfieren en el retorno, y la inserción no se ejecuta, además de producirse una fuga de memoria.

Si partimos de la segunda forma, el problema es análogo, aunque más difícil de explicar. :)

Ahora nuestro árbol estará declarado como:

ArbolBB *nuestroArbol;

Si queremos insertar un dato nuevo tendremos que pasar un puntero a nuestroArbol, que será un puntero doble a un ArbolBB.

U> He visto otros prototipos más sencillos como este:
U> int insertarDato(int nuevoDato, ArbolBB ParbolBB)

La diferencia entre esta versión de insertarDato y la otra es que en esta se asume que el dato es de tipo entero, y también se asume un orden concreto, por lo que no hay que proporcionar una función de comparación.

U> ¿Podríais poner un ejemplo de implementación para este prototipo?

Hay muchas posibles soluciones, pero básicamente es igual que para un tipo de dato concreto, aunque intentar lo mismo para datos genéricos complica un poco el código.

Lo siento, pero usaré la definición de ArbolBB siguiente:

----8<------
typedef struct TNodo {
   void* dato;
   struct TNodo* hijoIzdo;
   struct TNodo* hijoDcho;
} TNodo;

typedef struct TNodo* ArbolBB;

void insertarDato(void* dato, ArbolBB *ParbolBB, 
   int (*fCompara)(void*, void*)) {
   TNodo* padre = NULL;
   TNodo* actual = *ParbolBB;

   /* Buscamos la posición del dato dentro del árbol: */
   while(!Vacio(actual) && 0 != fCompara(dato, actual->dato)) {
      padre = actual;
      if(fCompara(dato, actual->dato)<0) actual = actual->hijoIzdo;
      else if(fCompara(dato, actual->dato)>0) actual = actual->hijoDcho;
   }

   /* Si el dato está en el árbol, regresamos sin hacer nada */
   if(!Vacio(actual)) return;
   /* Si el árbol está vacío, creamos un árbol nuevo: */
   if(Vacio(padre)) {
      *a = (ArbolBB)malloc(sizeof(TNodo));
      (*a)->dato = dato;
      (*a)->hijoIzdo= (*a)->derecho = NULL;
   } /* Si no, creamos un nodo y lo añadimos al árbol: */
   else if(fCompara(dato, padre->dato) < 0) {
      actual = (ArbolBB)malloc(sizeof(TNodo));
      padre->hijoIzdo= actual;
      actual->dato = dat;
      actual->hijoIzdo= actual->hijoDcho= NULL;
   }
   else if(fCompara(dato, padre->dato) > 0) {
      actual = (ArbolBB)malloc(sizeof(TNodo));
      padre->hijoDcho= actual;
      actual->dato = dat;
      actual->hijoIzdo= actual->hijoDcho= NULL;
  }
}
----8<------

Puede que haya algún error, ya que no lo he compilado...

Hasta pronto.