Usuwanie ostatniego elementu w drzewie BST

0

Witajcie. Mam taki problem: znajduje daną wartość w drzewie funkcją szukaj, która przyjmuje 2 arg: var korzen oraz co_szukac.
W funkcji usun_element(var k : wsk; element : integer) szukam wartości, której chce usunąć tak:

szukaj(k, element)

Po wyświetleniu w funkcji usun_element: k.^dana wyświetla odpowiednią wartość (to co w element). Następnie sprawdzam czy k^.lewy = nil and k^.prawy = nil. Jeśli tak to daje dispose(k);

No i podczas wyświetlenia drzewa metodą inorder:
Wynik wyszukania inorder: 1 2 4 5 6 7 -32488 <- tutaj było 9, teraz wyświetla jakieś bzdety zamiast nie wyświetlać nic..
Procedura inorder:

procedure inorder(k : wsk);
BEGIN
     if k <> nil then
     BEGIN
        inorder(k^.lewy);
        write(k^.dana, ' ');
        inorder(k^.prawy);
     END;
END

Jak widać, sprawdzam za każdym razem, czy k<> nil -> więc dlaczego jakby odczytywało tą "9" tylko już zniszczoną i zapewne odczytuje bzdety z pamięci ?

0

Następnie sprawdzam czy k^.lewy = nil and k^.prawy = nil. Jeśli tak to daje dispose(k);

A co, jeśli k^.lewy = nil i k^.prawy <> nil lub k^.lewy <> nil i k^.prawy = nil? Czyli w przypadku, gdy dany węzeł posiada jednego syna lub jeden liść?

Nie podałeś jakiegoś sensownego kodu, więc nic więcej nie można napisać.

0

Samo zwolnienie pamięci to jeszcze nie wszystko element, który był rodzicem tego liścia musi go oznaczyć jako nil. W przeciwnym wypadku wskaźnik będzie dalej wskazywał na zwolnione miejsce w pamięci.

0

przekazuj k jako var po dispose(k); dodaj k:=nil;

0

@_13th_Dragon
Mam taki kod usuwania ostatniego elementu:

procedure usun_element(var root : wsk; wartosc : integer); {przekazuje przez vara}
var
	tmp : wsk;

BEGIN
	tmp := nil;
	szukaj(root, wartosc); {ustawienie wskaznika na element, ktory chce usunac...}
	if (root^.lewy = nil) and (root^.prawy = nil) then {sprawdzam czy lewy i prawy = nil => ostatni element}
	BEGIN
		writeln('Usuwam wartosc: ', root^.dana, ' bez naruszenia struktury drzewa.');
		dispose(root); {usuwanie aktualnego elementu}
		root := nil;
		exit;
	END;
	{if root^.lewy <> nil ... dalsze przypadki jeszcze nie zrobione }
	
END;

Nadal wyświetla: 1 2 4 5 6 7 -28392 <- tutaj była 9

@furious programming wiem że są też inne przypadki, ale chce załatwić ten jeden konkretny żeby działał i dopiero dopiszę następne. Jednak nie widzę sensu aktualnie pisać innych przypadków jak nie mogę sobie poradzić z najłatwiejszym :/

@szopenfx
jak zwolnię pamięć i przypisze do tego miejsca nil to znaczy, że górny element (rodzic) pokazuje na nil (nie zrywam więzi) więc i tak powinno działać (?)

0

Masz zmienić szukaj tak aby też działała na var
Przy czym root nie możesz zmieniać w szukaj, więc:

tmp:=root;
szukaj(tmp,wartosc);
0

nadal to samo. Procedura szukająca elementu w drzewie:

procedure szukaj(var k : wsk; co_szukac : integer);
BEGIN
     while TRUE do
     BEGIN
          if k^.dana = co_szukac then
          BEGIN
             writeln('ZNALEZIONO!');
             exit;
          END;
          if (k^.lewy = nil) and (k^.prawy = nil) then
          BEGIN
              writeln('NIE ZNALEZIONO!');
              exit;
          END;
          if co_szukac < k^.dana then
          BEGIN
             if k^.lewy <> nil then k := k^.lewy
             else BEGIN writeln('Nie znaleziono'); break;  END;
          end
          else
             if k^.prawy <> nil then k := k^.prawy
              else BEGIN writeln('Nie znaleziono'); break; END;
     END;
END;

Usuwanie elementu:

procedure usun_element(var root : wsk; wartosc : integer);
var
	tmp : wsk;

BEGIN
	tmp := root;
	szukaj(tmp, wartosc);
	if (tmp^.lewy = nil) and (tmp^.prawy = nil) then
	BEGIN
		writeln('Usuwam wartosc: ', tmp^.dana, ' bez naruszenia struktury drzewa.');
		dispose(tmp);
		tmp := nil;
		exit;
	END;
	{if root^.lewy <> nil }
	
END;

Główny blok programu:

BEGIN
  wstaw_item(korzen, 5); {to bedzie korzen}
  wstaw_item(korzen, 4);
  wstaw_item(korzen, 2);
  wstaw_item(korzen, 6);
  wstaw_item(korzen, 7);
  wstaw_item(korzen, 1);
  wstaw_item(korzen, 9);
  
  usun_element(korzen, 9);

  write('Wynik wyszukania inorder: ');
  
  inorder(korzen);
  usun_drzewo(korzen);  
  readln;
END.

Wynik dla usuwania 9 :

Usuwam wartosc: 9 bez naruszenia struktury drzewa.
Wynik wyszukania inorder: 1 2 4 5 6 7 -24296 
0

Bo po twoim usunieciu rodzic usunietego elementu wciaz na cos wskazuje, powinienes przekierowac na NIL

0

Myślałem, że jak mam element jakiś i go skasuje a potem na to miejsce przypisze nil, to jego rodzic nadal pokazuje w to miejsce, jednak to miejsce to nil (więc nie powinno się wyświetlać). Jednak błędnie zakładałem. Napisałem funkcje "wyszukajRodzica", potem usuwam element, który chce usunąć, i w elemencie rodzic daje nil na wiązanie z tym właśnie usuniętym elementem. Póki co działa. Dzięki

0

Niepotrzebnie tworzysz zmienną lokalną tmp będzie ona miała kopię wskaźnika root, zmieniając ją później na tmp := nil; skótek będzie tylko wewnątrz tej funkcji a root dalej nie będzie "nil".
Prawdopodobnie to zadziała:

procedure usun_element(var root : wsk; wartosc : integer);
BEGIN
    szukaj(root, wartosc);
    if (root^.lewy = nil) and (root^.prawy = nil) then
    BEGIN
        writeln('Usuwam wartosc: ', root^.dana, ' bez naruszenia struktury drzewa.');
        dispose(root);
        root := nil;
        exit;
    END; 
END;

//Edycja: poprawiłem całość bez zmiennej lokalnej (wcześniej by to nie zadziałało)

0
qqqs napisał(a)

Myślałem, że jak mam element jakiś i go skasuje a potem na to miejsce przypisze nil, to jego rodzic nadal pokazuje w to miejsce, jednak to miejsce to nil (więc nie powinno się wyświetlać).

To nie tak działa - jeśli syn danego węzła jest pusty, to jego wskaźnik musi być **Nil**em, a nie wskazywać na miejsce, w którym być może (bo niekoniecznie) znajduje się wartość odpowiadająca **Nil**owi;

Dlatego jeśli chcesz zmodyfikować jakikolwiek węzeł drzewa, musisz jego wskaźnik przekazać przez referencję (czyli ze słówkiem Var), a nie przez wartość (bez żadnego słowa kluczowego); Inaczej będziesz operować na jego kopii, a wszelkie znami będą miały zasięg lokalny.

0
procedure usun_element(var root:wsk;wartosc:integer);
begin
  if root=nil then Exit;
  if root^.dana>wartosc then usun_element(root^.lewy,wartosc)
  else if root^.dana<wartosc then usun_element(root^.prawy,wartosc)
  else
  begin
    dispose(root);
    root:=nil;
  end; 
end;
0

@_13th_Dragon , pokaz ten inny sposob :)

0

Podwojny wskaznik.

Btw. jako niezarejestrowany moge dodawac komentarze?

1
procedure usun_element(var root:wsk;wartosc:integer);
var tmp:^wsk;
var node:wsk;
begin
  node:=root;
  tmp:=@root;
  while node<>nil do
  begin
    if node^.dana>wartosc then tmp:=@(node^.lewy)
    else if node^.dana<wartosc then tmp:=@(node^.prawy)
    else
    begin
      dispose(node);
      tmp^:=nil;
    end; 
    node:=tmp^;
  end;
end;

1 użytkowników online, w tym zalogowanych: 0, gości: 1