Hola amigos!
tengo un problema intentando implementar una funcion remover, para un arbol binario de busqueda.
con un compañero planteamos este algoritmo:
arbol_t *removerDesbalanceado(arbol_t *arbol, int valor){
arbol_t *aux;
if(!arbol)
return NULL;
if(arbol->contenido > valor)
arbol->iz = removerDesbalanceado(arbol->iz,valor);
else if(arbol->contenido < valor)
arbol->der = removerDesbalanceado(arbol->der,valor);
else{ //Si es igual
if(arbol->der == NULL){
if(arbol->iz == NULL)
return NULL; //Si no tiene hijos retorna Null
return arbol->iz; //sino retorna todo el subarbol izquierdo
}
else{
aux = menor(arbol->der);
aux->iz = arbol->iz;
aux = arbol->der;
return aux;
}
}
}
arbol_t es la estructura de un nodo con un campo contenido y dos campos punteros de hijos:
typedef struct arbolStr{
int contenido;
struct arbolStr *iz, *der;
}arbol_t;
le pusimos removerDesbalanceado pq lo que hacemos es una vez q encontramos el nodo a remover ponemos en lugar de este, todo el arbol derecho, enlazando el nodo de mas abajo a la iz (el de menor valor) con el arbol izquierdo del nodo a remover.
se lo mostramos a otro compañero y nos dijo, que el arbol se iba a desbalancear demaciado, y que lo mejor seria: agarrar el menor del hijo derecho del arbol a remover y poner el valor de ese nodo como el valor del nodo a remover y luego hacer que el que apuntaba al nodo del cual "robamos" el valor apunte a NULL.
entonces el arbol quedaria mucho mas balanceado y la remocion seria mas efectiva.
nuestro problema es el de hacer que el nodo que apuntaba al nodo del "robamos" el valor apunte a null.
este es nuestro codigo, no terminado, en principio copiamos la funcion de removerDesbalanceado para modificarla, quiza hay cosas que son de la otra funcion y no estan modificadas:
arbol_t *removerBalanceado(arbol_t *arbol, int valor){
arbol_t *a, *b;
int cont;
if(!arbol)
return NULL;
if(arbol->contenido > valor)
arbol->iz = removerBalanceado(arbol->iz,valor);
else if(arbol->contenido < valor)
arbol->der->contenido = removerBalanceado(arbol->der,valor);
else{ //Si es igual, osea, si encontre el nodo a remover
if(arbol->der == NULL){
if(arbol->iz == NULL)
return NULL; //Si no hay hijo iz ni der devuelvo null
return arbol->iz; //si no hay hijo der pero si iz devuelvo subarbol iz
}
else{
a = menor(arbol->der);
cont = a->contenido;
b = rastreaAnterior(a); //busco el que apuntaba a aux para ponerlo en null
b->iz = NULL; //se que es el izquierdo pq cuando busco el menor siempre va a estar a la iz
free(a
); //Libero a, osea, remuevo el nodo a remover return b; //Devuelvo b que es el nodo que apuntaba
}
}
arbol->contenido = cont;
}
vamos por buen camino?
como podriamos hacer la parte del else{} de la funcion anterior.
ah!, me olvidaba, en el removerBlanaceado, llamo a una funcion auxiliar que me devuelve el que apunta a un nodo en particular, le paso el nodo minimo y cuando obtengo el nodo que lo apuntaba hago q apunte a NULL, parece razonable, el problema es que me parece medio enredado, y se que debe alguna otra forma para hacerlo mas eficiente.
si alguien nos puede ayudar se lo agradecemos
saludos!
