Usuwanie elementu z drzewa BST.

Tak wygląda implementacja drzewa:

  struct sleaf
{
 int     x;
 sleaf *pL;
 sleaf *pR;
};

sleaf *create(int x)
{
 sleaf *pleaf = new sleaf;
 pleaf->x  = x;
 pleaf->pL = NULL;
 pleaf->pR = NULL;
} 

Tak wygląda moja próba zbudowania funkcji usuwającej:

int remove2(sleaf *pleaf)
{
    if(pleaf->pL == NULL and pleaf->pR == NULL)
    {
        delete pleaf;
        return 0;
    }

    if(pleaf->pL != NULL and pleaf->pR == NULL)
    {
        sleaf * tmp = pleaf;
        pleaf = pleaf->pL;
        delete tmp->pL;
        delete tmp;
        return 0;
    }

    if(pleaf->pL == NULL and pleaf->pR != NULL)
    {
        sleaf * tmp = pleaf;
        pleaf = pleaf->pR;
        delete tmp->pR;
        delete tmp;
        return 0;
    }

    if(pleaf->pL != NULL and pleaf ->pR != NULL)
    {

        sleaf * tmp = pleaf;
        pleaf = pleaf->pL;
        pleaf->pR = tmp->pR;
        remove2(pleaf->pL);
        delete tmp;
    }
} 

Niestety nie działa, zatem jak zbudować prostą funkcję usuwającą dany węzeł z drzewa BST?

Witam,

Twoja implementacja jest nieprawidłowa. O ile struktury sleaf bym się jeszcze nie czepiał z uwagi na brak wskaźnika do rodzica, o tyle funkcje create jest całkowicie nieprawidłowa.

Jeżeli ma to być drzewo BST czyli binarne drzewo poszukiwań to wartość klucza lewego syna danego węzła musi być mniejsza niż wartość klucza tego węzła. Analogicznie z synem prawym tylko, ze wartość klucza syna prawego ma być większa.

Co do funkcji create to ja zaimplementowałbym coś takiego:

void dodaj(unsigned int id) {
	sleaf *wezel = new sleaf;	
	wezel->id = id;
	wezel->rodzic = 0;
	wezel->syn_lewy = 0;
	wezel->syn_prawy = 0;

	// Obiekt this->korzen jest gdzieś w klasie zawierającej funkcję dodaj.
	// Może też być przekazany jako argument funkcji wtedy będzie to tak:
	// void dodaj(sleaf *temp, unsigned int id)...
	//
	// ...i tej jednej linijki poniżej już nie będzie.
	sleaf *temp = this->korzen;

	if(this->korzen == 0){
		this->korzen = wezel;
	}
	else{
		while(temp){
			if(wezel->id < temp->id){
				if(temp->syn_lewy == 0){
					temp->syn_lewy = wezel;
					wezel->rodzic = temp;
					break;
				}
				else{
					temp = temp->syn_lewy;
				}
			}
			if(wezel->id > temp->id){
				if(temp->syn_prawy == 0){
					temp->syn_prawy = wezel;
					wezel->rodzic = temp;
					break;
				}
				else{
					temp = temp->syn_prawy;
				}
			}
		}
	}
}

Jeżeli chodzi o usuwanie węzła to fajnie się robi jeżeli węzeł nie posiada synów (jest liściem) lub posiada tylko jednego syna. Wtedy sprawa jest prosta.
Gorzej kiedy węzeł, który chce się usunąć posiada obu synów. Wtedy jego miejsce zajmuje jego następnik w porządku przechodzenia drzewa inorder i tutaj mogą być schody z podczepianiem takiego następnika do miejsca usuwanego węzła.

Osobiście z tematem poradziłem sobie w ten sposób:
Wykorzystałem część algorytmu DSW równowarzącego drzewo BST.
Faza pierwsza tego algorytmu tworzy z drzewa listę liniową i wtedy każdy węzeł posiada tylko rodzica i prawego syna co ułatwia usuwanie, bo robi się to tak jak w liście wskaźnikowej.

Tutaj jest ten algorytm również w C++ (ładnie wytłumaczone):
http://edu.i-lo.tarnow.pl/inf/alg/001_search/0116.php

Tak, wiem, że to jest trochę podejście typu workaround ale sam potrzebowałem zrównoważyć swoje drzewo dlatego skorzystałem z pomocy DSW przy usuwaniu węzła :)

Pozdrawiam.

hmmmmmm to zakładam, że moja funkcja dodawania nowych elementów, jest do śmieci?

void add(sleaf *pparent, sleaf *pchild, int which)
{
if (which == 1) pparent->pL = pchild;
if (which == 2) pparent->pR = pchild;
}

W funkcji dodawania elementu w ogóle nie podaje się wskaźnika na rodzica czy dzieci. Jeżeli nie korzystamy z klas do jedynym wskaźnikiem będzie wskaźnik do korzenia drzewa.
W funkcji tejże, jako argumenty, podaje się klucz oraz jakieś inne dane, które ten klucz ma opisywać (no bo po co nam drzewo BST z samymi kluczami liczbowymi?)

Reasumując jeżeli piszemy drzewo bez użycia klas to prototyp funkcji będzie następujący:
void dodaj(Drzewo *wsk, int klucz);

Gdzie Drzewo *wsk to wskaźnik to korzenia struktury 'Drzewo' opisującej drzewo.
Np.

 

struct Drzewo {
	int id;
	Drzewo *rodzic;
	Drzewo *syn_lewy;
	Drzewo *syn_prawy;
}

// Przy dodawaniu pierwszego węzła tworzony jest dopiero nowy obiekt.
Drzewo *korzen = 0;

// Tworzymy tempa żebyśmy nie przestawili wskaźnika do korzenia dodając węzeł.
Drzewo *temp = korzen;

/.../

// Dodawanie liczby 21 do drzewa.
dodaj(temp,21);

Jeżeli funkcja dodaj jest składową klasy, która posiada już jako składową także wskaźnik do struktury drzewa to piszemy:
void dodaj(int klucz);