Borrar un nodo sin hijos ó nodo hoja: Simplemente se borra y se establece a nulo el apuntador
de su padre.
Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.
Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el
de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en
inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de
su subárbol derecho (menor nodo del subarbol derecho).Aunque en realidad aún no he podido implementarlo =(.. pues el codigo no hace lo que debería.
Toda esta información la encontré en wikipedia. http://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "bool.h"
#define DEBUG 1
// NOTA: faltan implementar las rotaciones
// dobles; por ahora no balancea bien
// un nodo de ruteo no cuenta duplicados
#define NO_VALIDO -1
int next = 0;
struct nodo_de_arbol {
char dato;
int altura;
int contador;
int id;
struct nodo_de_arbol* padre;
struct nodo_de_arbol* izq; // hijo
struct nodo_de_arbol* der; // otro hijo
};
typedef struct nodo_de_arbol nodo;
void borra(nodo* n) {
if (n == NULL) {
return;
} else {
borra(n->izq);
borra(n->der);
free(n);
}
return;
}
void muestra(nodo* n) {
if (n == NULL) {
return; // caso base de recursion
} else {
muestra(n->izq);
if (n->izq != NULL && n->der != NULL) {
printf("[%c, %d <%d / %d, %d>] ",
n->dato, n->altura, n->id,
n->izq->id, n->der->id);
} else {
printf("(%c, %d <%d> #%d) ",
n->dato, n->altura, n->id,
n->contador);
}
if (n->izq == NULL && n->der == NULL) {
printf("%c[%d] ", n->dato, n->contador);
}
muestra(n->der);
}
return;
}
void elimina(nodo* n,nodo** raiz){nodo-> NULL;
}
void balancea(nodo* n, nodo** raiz) {
int ai, ad, max, min, aalt, balt;
nodo* t = NULL;
nodo* u = NULL;
nodo* v = NULL;
nodo* a = NULL;
nodo* b = NULL;
nodo* p = NULL;
nodo* x1 = NULL;
nodo* x2 = NULL;
if (n == NULL) {
printf("Ya topamos con la raiz.\n");
return;
}
if (n->izq == NULL ||
n->der == NULL) {
printf("No se puede sin hijos.\n");
return;
}
t = n; // nodo actual
assert(t != NULL);
printf("Checando balance en %c (alt. %d).\n",
t->dato, t->altura);
u = n->izq; // hijo izquierdo
assert(u != NULL);
v = n->der; // hijo derecho
assert(v != NULL);
ai = u->altura;
ad = v->altura;
printf("Hijos %c (alt. %d) y %c (alt. %d).\n",
u->dato, ai, v->dato, ad);
max = (ai > ad) ? ai : ad;
min = (ai > ad) ? ad : ai;
if (max + 1 != t->altura) {
t->altura = max + 1; // actualizar altura
}
if (max - min > 1) { // balancear
p = t->padre; // padre del actual
printf("%c a altura %d requiere balanceo.\n",
t->dato, t->altura);
printf("Entrando tenemos:\n");
if (p != NULL) {
printf("p = %d, ", p->id);
} else {
printf("p = NULL, ");
}
printf("t = %d, \n", t->id);
printf("u = %d, v = %d, \n",
u->id, v->id);
if (ai <= ad - 2) {
// si hay demasiada altura a la der
// => voltear "peso" hacia la izq.
a = v->izq;
b = v->der;
assert(a != NULL);
assert(b != NULL);
aalt = a->altura;
balt = b->altura;
printf("a = %d, b = %d, \n",
a->id, b->id);
if (aalt <= balt) { // rotacion simple izq
printf("Simple izquierda.\n");
if (p != NULL) {
// v debe reemplazar a t como hijo
if (p->izq == t) {
p->izq = v;
} else { // era derecho
p->der = v;
}
} else {
// v es ahora raiz
*raiz = v;
}
// el padre de t sera padre de v
v->padre = p;
// printf("Arreglado hacia arriba.\n");
// v ahora es hijo izq de t
// t es padre de v
v->izq = t;
t->padre = v;
// el hijo der de t no cambia
// printf("Arreglado entre t y v.\n");
// a va a ser hijo derecho de t
// t va a ser padre de a
t->der = a;
a->padre = t;
// printf("Arreglado entre a y t.\n");
if (p != NULL) {
printf("v = %d es hijo de p = %d,\n",
v->id, p->id);
}
printf("t = %d = %d es hijo de v = %d,\n",
t->id, v->izq->id, v->id);
printf("a = %d = %d es hijo de t = %d\n",
a->id, t->der->id, t->id);
printf("b = %d = %d es hijo de v = %d,\n",
b->id, v->der->id, v->id);
printf("u = %d = %d es hijo de t = %d.\n",
u->id, t->izq->id, t->id);
// para ni u ni b nada cambia
} else {
printf("Simple derecha-izquierda.\n");
x1 = a->izq;
assert(x1 != NULL);
x2 = a->der;
assert(x2 != NULL);
if (p != NULL) {
if (p->izq == t) {
p->izq = a; // w
} else { // era der.
p->der = a;
}
} else { // t era raiz
*raiz = a; // avisar main
}
v->padre = a;
a->der = v;
t->padre = a;
a->izq = t;
v->izq = x2;
x2->padre = v;
t->der = x1;
x1->padre = t;
}
} else if (ai >= ad + 2) {
// voltear hacia la derecha
a = u->izq;
b = u->der;
assert(a != NULL);
assert(b != NULL);
aalt = a->altura;
balt = b->altura;
if (aalt >= balt) {
printf("Simple derecha.\n");
if (p != NULL) {
if (p->izq == t) {
p->izq = u;
} else { // era derecho
p->der = u;
}
} else {
// cambiando la raiz para ser u
*raiz = u;
}
u->padre = p;
// printf("Arreglado hacia arriba.\n");
u->der = t;
t->padre = u;
// printf("Arreglado entre t y u.\n");
t->izq = b;
b->padre = t;
// printf("Arreglado entre b y t.\n");
} else { // (aalt < balt)
printf("Doble izquierda derecha.\n");
x1 = b->izq;
assert(x1 != NULL);
x2 = b->der;
assert(x2 != NULL);
if (p != NULL) {
if (p->izq == t) {
p->izq = b; // w
} else { // era der.
p->der = b;
}
} else { // t era raiz
*raiz = b; // avisar main
}
u->padre = b;
b->izq = u;
t->padre = b;
b->der = t;
u->der = x1;
x1->padre = u;
t->izq = x2;
x2->padre = t;
}
}
if (p != NULL) {
balancea(p, raiz);
}
} else {
printf("%c esta bien (%d vs. %d).\n",
n->dato, ai, ad);
// siempre checa hasta la raiz
balancea(n->padre, raiz);
}
return;
}
bool agrega(char dato, nodo* arbol, nodo** n) {
nodo* nuevo;
nodo* reemplazo;
char ruteo;
if (arbol == NULL) {
// caso especial de no tener nada aun
nuevo = (nodo*)malloc(sizeof(nodo));
nuevo->contador = 1;
nuevo->id = next++;
nuevo->altura = 1; // como hoja
nuevo->dato = dato;
nuevo->padre = NULL;
nuevo->izq = NULL;
nuevo->der = NULL;
*n = nuevo; // nueva raiz
return TRUE;
} else {
if (arbol->izq == NULL &&
arbol->der == NULL) { // si es hoja
if (arbol->dato == dato) {
// iguales; agregar duplicidad
arbol->contador++;
return FALSE;
}
printf("Agregando %c en %c.\n",
dato, arbol->dato);
ruteo = (arbol->dato < dato ?
arbol->dato : dato);
nuevo = (nodo*)malloc(sizeof(nodo));
nuevo->contador = 1;
nuevo->id = next++;
nuevo->altura = 1; // como hoja
nuevo->dato = dato;
nuevo->padre = arbol;
nuevo->izq = NULL;
nuevo->der = NULL;
reemplazo = (nodo*)malloc(sizeof(nodo));
reemplazo->contador = arbol->contador;
arbol->contador = NO_VALIDO;
reemplazo->id = next++;
reemplazo->altura = 1; // como hoja
reemplazo->dato = arbol->dato;
reemplazo->padre = arbol;
reemplazo->izq = NULL;
reemplazo->der = NULL;
if (dato < arbol->dato) {
arbol->izq = nuevo;
arbol->der = reemplazo;
} else if (dato > arbol->dato) {
arbol->der = nuevo;
arbol->izq = reemplazo;
}
arbol->dato = ruteo;
arbol->altura = 2;
balancea(arbol->padre, n);
} else {
if (dato <= arbol->dato) {
agrega(dato, arbol->izq, n);
} else { // mayor
agrega(dato, arbol->der, n);
}
}
}
return TRUE;
}
int main(int argc, char** args) {
nodo* raiz = NULL;
char dato;
int contador = 0;
do {
dato = getchar(); // lee un caracter
if (!isspace(dato)) {
if (agrega(dato, raiz, &raiz)) {
contador++;
}
if (raiz != NULL) {
printf("\nCon %d nodos, altura %d: \n",
contador, raiz->altura);
muestra(raiz);
printf("\n");
} else {
printf("No hay nada.\n");
}
}
} while (dato != '!'); // parar despues de !
borra(raiz);
return 1;
}
1 comentario:
O sea, echaste mucho rollo sobre cómo eliminar y luego a fin de cuentas nada más le pusiste null :D
LOL, +2.
Publicar un comentario