Cześć,
Chciałbym poprosić o pomoc, chodzi o usuwanie elementu z drzewa BST podejrzewam, że rozwiązanie które mam jest nieoptymalne w kontekście wykorzystania pamięci. Wzorowałem się na tym: http://geeksquiz.com/binary-search-tree-set-2-delete/ Zastanawiam się czy rekurencji nie dałoby się jakoś zamienić na coś takiego:
void UsunHaslo(Haslo **korzen, string etykieta) {
Haslo *v = (*korzen);
while (v && !(v->etykieta == etykieta))
v = (v->etykieta < etykieta) ? v->prawy : v->lewy;
if (v != NULL) {
if (v->strony == NULL) {
if (v->lewy == NULL)
{
//delete(v);
v = v->prawy;
return;
}
else if (v->prawy == NULL)
{
//delete(v);
v = v->lewy;
return;
}
Haslo* pom = NajmniejszeHaslo(v->prawy);
v->etykieta = pom->etykieta;
v->strony = pom->strony;
UsunHaslo(&v->prawy, pom->etykieta);
}
}
}
Z tym, że nie wiem dlaczego stosując to rozwiązanie, po wyjściu z funkcji nie widzę zmian w drzewie, które miała ona dokonać... Nie wiem co jest źle, analogicznie usuwam budując algorytm oparty o listę i tam zmiany zapisują się po wyjściu z funkcji
void UsunHaslo(Haslo **korzen, string etykieta, short int numer) {
Haslo *kopia = (*korzen), *tmp = NULL;
while (kopia != NULL && kopia->etykieta < etykieta) {
tmp = kopia;
kopia = kopia->nastepny;
}
if (kopia != NULL && kopia->etykieta == etykieta) {
if (kopia->strony == NULL) {
if (kopia == (*korzen)) {
(*korzen) = NULL;
}
else {
tmp->nastepny = kopia->nastepny;
}
}
}
}
Każda podpowiedź mile widziana ;)