-
Notifications
You must be signed in to change notification settings - Fork 1
/
abb_borrar.c
75 lines (61 loc) · 2.19 KB
/
abb_borrar.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//Busca el padre de 'nodo'
nodo_abb_t* buscar_padre(abb_t* arbol,nodo_abb_t* raiz, nodo_abb_t* nodo){
nodo_abb_t *nodo_anterior;
nodo_abb_t *nodo_actual = raiz;
int comparacion = arbol->comparar_clave(nodo_actual->clave, nodo->clave);
while(comparacion != 0){
nodo_anterior = nodo_actual;
if(comparacion < 0){
nodo_actual = nodo_actual->h_izquierdo;
}else{
nodo_actual = nodo_actual->h_derecho;
}
comparacion = arbol->comparar_clave(nodo_actual->clave, nodo->clave);
}
return nodo_anterior;
}
//dado un nodo busca donde termina por su lado mayor(derecha) y devuelve el ultimo nodo.
nodo_abb_t *buscar_ult_mayor(nodo_abb_t* nodo){
nodo_abb_t *nodo_actual = nodo;
while(nodo_actual->h_derecho != NULL){
nodo_actual = nodo_actual->h_derecho;
}
return nodo_actual;
}
//FALTA en caso de que el nodo sea la raiz, se podria redireccionar a una funcion borrar_raiz().
void *abb_borrar(abb_t *arbol, const char *clave){
nodo_abb_t* nodo_a_borrar = abb_buscar(arbol,arbol->raiz,clave);
if (!nodo_a_borrar){
return NULL;
}
void *dato = nodo_a_borrar->dato;
nodo_abb_t* padre_nodo_a_borrar = buscar_padre(arbol,arbol->raiz,nodo_a_borrar);
bool hijo_izquierdo_de_padre = arbol->comparar_clave(nodo_a_borrar->clave, padre_nodo_a_borrar->clave) < 0;
if((nodo_a_borrar->h_izquierdo == NULL) && (nodo_a_borrar->h_derecho == NULL)){
free(nodo_a_borrar);
}else if((nodo_a_borrar->h_izquierdo != NULL) && (nodo_a_borrar->h_derecho != NULL)){
if(hijo_izquierdo_de_padre){
padre_nodo_a_borrar->h_izquierdo = nodo_a_borrar->h_izquierdo;
}else{
padre_nodo_a_borrar->h_derecho = nodo_a_borrar->h_izquierdo;
}
nodo_abb_t *utltimo_mayor = buscar_ult_mayor(nodo_a_borrar->izquierdo);
ultimo_mayor->h_derecho = nodo_a_borrar->h_derecho;
}else{
if(nodo_a_borrar->h_izquierdo != NULL){
if(hijo_izquierdo_de_padre){
padre_nodo_a_borrar->h_izquierdo = nodo_a_borrar->izquierdo;
}else{
padre_nodo_a_borrar->h_derecho = nodo_a_borrar->izquierdo;
}
}else{
if(hijo_izquierdo_de_padre){
padre_nodo_a_borrar->h_izquierdo = nodo_a_borrar->derecho;
}else{
padre_nodo_a_borrar->h_derecho = nodo_a_borrar->derecho;
}
}
}
free(nodo_a_borrar);
return dato;
}