Usuwanie węzła drzewa BST

0

Witam.

Piszę program bazy danych oparty na drzewach BST i potrzebuję pomocy z usuwaniem węzła drzewa. Znalazłem gdzieś kawałek kodu, przerobiłem, ale nie działa. Program zawiesza się.
Mam gorącą prośbę żeby ktoś poszukał błędów lub ewentualnie jeżeli pisał coś opartego o drzewka BST żeby podrzucił kawałek swojego kodu usuwającego węzeł drzewa wskazywany przez wskaźnik. Najlepiej żeby był to kod strukturalny taki mniej-więcej dla początkujących. Pozdrawiam i z góry dziękuję za pomoc.

//funkcja usuwania wezla drzewa
//wsk jest adresem skladnika rodzica, ktory wskazuje na usuwany wezel
void Remove(Tree *wsk) {
    Tree *tymcz;
    if (wsk->Lewy == NULL)
    {
	tymcz = wsk;
	wsk = wsk->Prawy;
	free(tymcz);
    }
    else if (wsk->Prawy == NULL)
    {
	tymcz = wsk;
	wsk = wsk->Lewy;
	free(tymcz);
    }
    else    //jezeli usuwany wezel ma dwoje dziec
    {
	for (tymcz = wsk->Lewy; tymcz->Prawy != NULL;
		tymcz = tymcz->Prawy)
	    continue;
	tymcz->Prawy = wsk->Prawy;
	tymcz = wsk;
	wsk = wsk->Lewy;
	free(tymcz);
    }	
}
0

Wydaje mi sie ze za bardzo to sobie chciałeś "uprościć"
Tu masz moje usuwanie z BST, może ci się przyda ;)
Jest robione dla strukury:

struct node
  {
    int val;
    node* left;
    node* right;
    node* parent;
  };
void rem(node*& root, int k) //root to wskaznik do korzenia, k to klucz usuwanego elementu
{
  node* usuwacz = find(root,k); //szukamy elementu
  if (usuwacz) //jest w ogóle co usuwać
    {
      if ((usuwacz->left) && (usuwacz->right)) //ma oba poddrzewa
        {
          node* pre = pred(usuwacz); //poprzednik
          usuwacz->val=pre->val;
          if (pre->parent->left == pre) //jestesmy lewym poddrzewem
            pre->parent->left=pre->left; //przepinanie parenta poprzednika
          else
            pre->parent->right=pre->left;
          delete pre;
        }
      else //brak któregoś poddrzewa
        {
          node* poddrzewo = usuwacz->left ? usuwacz->left : usuwacz->right; //łapiemy wsk na poddrzewo

          if (usuwacz->parent) //nie-root
            {
              if (usuwacz->parent->left == usuwacz) //jesteśmy lewym poddrzwem
                usuwacz->parent->left = poddrzewo; //ustawianie parentow
              else
                usuwacz->parent->right = poddrzewo;

              if (poddrzewo) //jesli nie jest puste, czyli mozna ustawic mu parenta
                poddrzewo->parent = usuwacz->parent;
            }
          else //root
            {
              poddrzewo->parent=NULL;
              root=poddrzewo;
            }
          delete usuwacz;
        }
    }
}
0

Dzięki.

Sorry że tak przynudzam, mógłbyś z takim razie wrzucić jeszcze funkcję pred() i dodawanie węzła? Bo w moim drzewie nie miałem node->parent i nie bardzo wiem jak je dodawać.

Z góry dzięki

0

http://pastebin.4programmers.net/199
add, rem, find, pred, succ, rotate_right, rotate_left
ustawione na 72h więc spiesz się :P

0

Dzięki wielkie! Bardzo mi pomogłeś. [browar]

0

Również potrzebowałem takiego kody więc spróbowałem użyć tego zamieszczonego tu jednak gdy mój program dochodzi do miejsca

            else //root
            {
              poddrzewo->parent=NULL;
              root=poddrzewo;
            }

, a konkretnie linijki poddrzewo->parent=NULL; to wywala mi błędy segmenntacji

0

W takim razie masz gdzieś bląd, bo ten kod chyba działał i był poprawny.

0

Shalom, bardzo proszę o udostępnienie jeszcze raz kodów add, rem, find, pred, succ, rotate_right, rotate_left do drzew BST. Pozdrawiam.
Zaliczenie już jest, ogólnie mogę spodziewać się czegoś takiego na egzaminie a tematu tego jeszcze dobrze nie zgłębiłem a już nie zdążę pewnie napisać, no nic dzięki :)

0

Dziękuję bardzo Shalom, pozdrawiam :)

0

@Shalom - można prosić o ponowne wrzucenie kodów?
Z góry dzięki.

pozdr.
Mac.

0

W tym kodzie jest błąd: jeśli usuwamy element, który miał dwójkę dzieci, to u poprzednika nie uwzględniamy, że też może mieć potomstwo:

np.:
6(usuwany)
/
4 7

5
/
4,5

Oto mój kod:
TreeMap::iterator TreeMap::erase(TreeMap::iterator i){

TreeNode *del=i.node, *x, *y;

//najpierw sprawdzamy czy wezel ma pelne potomstwo
if(del->left == NULL || del->right == NULL)
	y=del;
else
	y=TreeMapDetail::next(del);

//sprawdzamy czy jest cos mniejszego w tym poddrzewie
if(y->left != NULL)
	x=y->left;
else
	x=y->right;

//przewiazanie wskaznikow w razie potrzeby
if(x!=NULL)
	x->parent=y->parent;

if(y->parent == root)
	root->left=x;
else{
	if(y == y->parent->left)
		y->parent->left=x;
	else
		y->parent->right=x;
}

//sprawdzenie czy wpinalismy na miejsce usuwanego wezla jakis inny bedacy
//nastepnikiem
if(y != del)
	del->data = y->data;

delete del;
return iterator(y);

}

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