SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: Rombus en Martes 7 de Octubre de 2008, 17:52

Título: Remover Nodo de Arbol Binario de Busqueda
Publicado por: Rombus en Martes 7 de Octubre de 2008, 17:52

Hola amigos!

tengo un problema intentando implementar una funcion remover, para un arbol binario de busqueda.

con un compañero planteamos este algoritmo:

Código: C

1.  
2. arbol_t *removerDesbalanceado(arbol_t *arbol, int valor){ 
3.     arbol_t *aux;   
4.  
5.     if(!arbol) 
6.         return NULL;
7.  
8.     if(arbol->contenido > valor) 
9.         arbol->iz = removerDesbalanceado(arbol->iz,valor); 
10.     else if(arbol->contenido < valor) 
11.         arbol->der = removerDesbalanceado(arbol->der,valor); 
12.     else{   //Si es igual 
13.         if(arbol->der == NULL){ 
14.             if(arbol->iz == NULL) 
15.                 return NULL;    //Si no tiene hijos retorna Null 
16.             return arbol->iz;   //sino retorna todo el subarbol izquierdo 
17.         } 
18.         else{ 
19.             aux = menor(arbol->der); 
20.             aux->iz = arbol->iz; 
21.             aux = arbol->der; 
22.             free(arbol); 
23.             return aux; 
24.         } 
25.     } 
26. }
27.  
28.  

arbol_t es la estructura de un nodo con un campo contenido y dos campos punteros de hijos:

Código: C

1. typedef struct arbolStr{ 
2.     int contenido; 
3.     struct arbolStr *iz, *der; 
4. }arbol_t;
5.  

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:

Código: C

1. arbol_t *removerBalanceado(arbol_t *arbol, int valor){ 
2.     arbol_t *a, *b; 
3.     int cont;   
4.  
5.     if(!arbol) 
6.         return NULL;   
7.  
8.     if(arbol->contenido > valor) 
9.         arbol->iz = removerBalanceado(arbol->iz,valor);  
10.     else if(arbol->contenido < valor)        
11.         arbol->der->contenido = removerBalanceado(arbol->der,valor); 
12.     else{       //Si es igual, osea, si encontre el nodo a remover 
13.         if(arbol->der == NULL){ 
14.             if(arbol->iz == NULL) 
15.                 return NULL;        //Si no hay hijo iz ni der devuelvo null 
16.             return arbol->iz;       //si no hay hijo der pero si iz devuelvo subarbol iz 
17.         } 
18.         else{ 
19.             a = menor(arbol->der); 
20.             cont = a->contenido; 
21.             b = rastreaAnterior(a); //busco el que apuntaba a aux para ponerlo en null 
22.             b->iz = NULL; //se que es el izquierdo pq cuando busco el menor siempre va a estar a la iz 
23.             free(a);    //Libero a, osea, remuevo el nodo a remover 
24.             return b;   //Devuelvo b que es el nodo que apuntaba  
25.         }
26.     } 
27.     arbol->contenido = cont; 
28. }
29.  

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!