Implementación de un Árbol de búsqueda binaria en C++
Enviado por tolero • 10 de Junio de 2018 • 1.395 Palabras (6 Páginas) • 213 Visitas
...
*/
if(AA -> hd != NULL)
return Minimo(AA -> hd);
TArbol y = AA -> p;
/*
Si no tiene hijo derecho voy intercambiando hijo con padre
y cuando el hijo no sea el hijo derecho del padre devuelvo el
padre y ese es el sucesor del nodo pedido.
*/
while(y != NULL && AA == y -> hd){
AA = y;
y = y -> p;
}
return y;
}/**OK**/
TArbol Predecessor(TArbol AA)
{
/*Si tiene hijo izquierdo busco en el subarbol derecho
el mínimo, ya que a la izquierda del nodo están los mayores
que el me quedo con el máximo de ellos
*/
if(AA -> hi != NULL)
return Maximo(AA -> hi);
TArbol y = AA -> p;
/*
Si no tiene hijo izquierdo voy intercambiando hijo con padre
y cuando el hijo no sea el hijo izquierdo del padre devuelvo
el padre y ese es el predecesor del nodo pedido.
*/
while(y != NULL && AA == y -> hi){
AA = y;
y = y -> p;
}
return y;
}/**OK**/
TArbol Transplant(TArbol& u, TArbol& v)
{
/**Función Auxiliar para el Delete**/
if(u -> p == NULL){
v -> hi = u -> hi;
v -> hd = u -> hd;
v -> p = NULL;
}
else if(u == u -> p -> hi)
u -> p -> hi = v;
else
u -> p -> hd = v;
if(v != NULL)
v -> p = u -> p;
}/**OK**/
TArbol Delete(TArbol AA, TArbol z)
{
/*
Si no tiene hijo izquierdo sobrescribo el nodo con su hijo
derecho
*/
if(z -> hi == NULL)
Transplant(z, z -> hd);
/*
Si no tiene hijo derecho sobrescribo el nodo con su hijo
izquierdo
*/
else if(z -> hd == NULL)
Transplant(z, z -> hi);
/*
Si tiene los dos hijos busco su sucesor que se encuentra
en su subarbol derecho y sobrescribo el nodo Y con su
subarbol derecho porque no tiene subarbol izquierdo, porque
si lo tuviera no fuera sucesor del nodo a borrar, luego
sobreescribo el nodo a borrar con el nodo Y y seteo los
respectivos hijos y padres
*/
else{
TArbol y = Minimo( z -> hd);
if(y -> p != z){
Transplant(y, y -> hd);
y -> hd = z -> hd;
y -> hd -> p = y;
}
Transplant(z, y);
y -> hi = z -> hi;
y -> hi -> p = y;
}
}/**OK**/
bool Sucesor(TArbol A, TDato x, TDato& suc){
/**Función obtimizada para buscar el Sucesor*/
/*
Devuelve falso si el arbol esta bacío o si el nodo al cual
se le busca el sucesor es el máximo nodo del arbol, y
devuelve verdadero si el nodo existe y con la llamada
por referencia se setea el valor de ese sucesor.
*/
TArbol Nod = Buscar(A, x);
if (A == NULL)
return false;
Nod = Sucesor(Nod);
if (Nod == NULL)
return false;
suc = Nod -> dato;//seteo de valor por referencia
return true;
}/**OK**/
TArbol ABB;
int main(){
assert(ABB == NULL);//interumpe el programa si no se setea el árbol a NULL
for(int i = 0;i <= 10;i++){
int x = rand() % 100;/*Se hacen inserciones aleatorias*/
...