drzewo BST - usuwanie elementu

0

Witam,
Mam problem z usuwaniem elementu z drzewa BST, zdaje ze pewnie juz mnostwo takich watkow w internecie, niestety zaden nie byl mi pomocny. Chcialem stworzyc wlasny program (jestem zupelnie poczatkujacy w dziedzinie programowania), w celu przygotowania sie na zajecia, dlatego prosze o szybko odpowiedz.
Problem jest nastepujacy: nie mam pojecia czemu, ale przy usuwaniu elementu usuwa sie cale drzewo. Byc moze nie jest to stricte funkcja usuwajaca, niestety drugi dzien nie jestem w stanie zlokalizowac bledu.
Z gory dziekuje za szybka pomoc!

#include<iostream>
using namespace std;

class lisc{
	private:
		lisc *left, *right, *parent;
		int liczba;
	public:
		lisc():left(NULL), right(NULL), parent(NULL), liczba(0) {}
		lisc(int licz):left(NULL), right(NULL), parent(NULL), liczba(licz) {}
		~lisc() {}
	
	friend class drzewo;
};

class drzewo{
	private:
		lisc *korzen;
	public:
		drzewo():korzen(NULL) {}
		~drzewo() {
			if(korzen!=NULL){
				usun(korzen);
			}
		}
		
		void usun(lisc *pomoc){
			if(pomoc!=NULL){
				usun(pomoc->left);
				usun(pomoc->right);
				delete pomoc;
			}
		}
		
		void wstaw(int licz);
		void inorder(lisc *pomoc);
		void wyswietl_in();
		lisc *poprzednik(lisc *pomoc);
		lisc *szukaj(int licz);
		lisc *usuwanie(lisc *pomoc);
		void usun_element(int licz);
};

void drzewo::wstaw(int licz){
		lisc *w, *p;
	w= new lisc; //tworzymy dynamicznie nowy wezel
	w->left=w->right=NULL; //zerujemy wskazania synow
	w->liczba=licz; //wstawiamy dane
	p=korzen; //wyszukujemy miejsce dla w, rozpoczynajac od korzenia
	if(p==NULL){
		korzen=w; //jesli drzewo jest puste to w staje sie korzeniem
	}
	else {
		while(true){ //petla nieskonczona
			if(licz < p->liczba){ //zaleznie od klucza idziemy do prawego lub lewego syna
				if(p->left==NULL){ //jesli nie ma lewego syna to wezel nim sie staje
					p->left = w; 
					break;
				}
				else p=p->left;
			}
			else {
				if(p->right==NULL){
					p->right=w;
					break;
				}
				else p=p->right;
			}
			w->parent = p; //rodzicem wezla w jest zawsze wezel wskazany przez p
		}
	}
}

void drzewo::inorder(lisc *pomoc){
	if(pomoc!=NULL){
		inorder(pomoc->left);
		cout << pomoc->liczba << endl;
		inorder(pomoc->right);
	}
}

void drzewo::wyswietl_in(){
	if(korzen == NULL){
		cout << "Drzewo jest puste. " << endl;
	}
	else {
		cout << "Drzewo inorder: " << endl;
		inorder(korzen);
	}
}

lisc *drzewo::poprzednik(lisc* pomoc){
	if(pomoc->left!=NULL){
		pomoc=pomoc->left;
		while(pomoc->right!=NULL){
			pomoc=pomoc->right;
			return pomoc;
		}
	}
}

lisc *drzewo::szukaj(int licz){
	lisc *pomoc=korzen;
	while(pomoc!=NULL){
		if(pomoc->liczba==licz){
			return pomoc;
		}
		if(pomoc->liczba < licz) pomoc=pomoc->right;
		else pomoc=pomoc->left;
	}
	cout << "Brak elementu w drzewie. " << endl;
	return 0;
}

lisc *drzewo::usuwanie(lisc *pomoc){
	lisc *y=pomoc->parent; //rodzic usuwanego wezla
	lisc *z; 
	if(pomoc->left!=NULL and pomoc->right!=NULL){ //wezel ma dwojke dzieci
		z=usuwanie(poprzednik(pomoc)); //usuwamy poprzednik x i zapamietujemy go w z
		z->left=pomoc->left;
		z->right=pomoc->right; //wstawiamy pomoc w miejsce z
		if(z->left!=NULL){
			z->left->parent=z; //ustawiamy z jako rodzica
		}
		if(z->right!=NULL){
			z->right->parent=z;
		}
		z->parent=y; // ustawiamy y jako rodzica z
		if(y==NULL) korzen=z; //jesli z jest korzeniem
		else if(y->left==pomoc)	y->left=z;
		else y->right=z; //jesli z nie jest korzeniem to podpinamy pod odpowiednie dziecko
	}
	else if(pomoc->left!=NULL or pomoc->right!=NULL){ //jedno dziecko lub wcale
		if(pomoc->left!=NULL){ //z staje sie lewym lub prawym potomkiem usuwanego
			z=pomoc->left;
		}
		else {
			z=pomoc->right;
		}
		z->parent=y; //y staje sie rodzicem z
		if(y==NULL) korzen=z;
		else if(y->left==pomoc) y->left=z; 
		else y->right=z;
	}
	else{ //wezel nie ma dzieci
		if(y!=NULL){ //czy wezel ma rodzica
			if(y->liczba < pomoc->liczba) y->right=NULL; //szukamy wezla do usuniecia
			else y->left=NULL;
		}
		else korzen=NULL;
	}
	return pomoc;
}

void drzewo::usun_element(int licz){
	lisc *pomoc = new lisc(licz);
	lisc *x=szukaj(licz);
	if(x!=NULL) delete usuwanie(pomoc);
	else cout << "Zostala podana zla wartosc. " << endl;
}

int main() {
	
	drzewo sosna;
	sosna.wstaw(5);
	sosna.wstaw(10);
	sosna.wstaw(18);
	sosna.wstaw(2);
	sosna.wstaw(20);
	sosna.wyswietl_in();
	sosna.usun_element(18);
	sosna.wyswietl_in();
	
	return 0;
}
0

Mści się bezsensowne nazewnictwo zmiennych.

0

A konkretnie?

0

Jak konkretniej? Co wiersz to bezsensowna nazwa:

lisc *drzewo::usuwanie(lisc *pomoc){
    lisc *y=pomoc->parent; //rodzic usuwanego wezla
    lisc *z;
0
pastelowe napisał(a):

A konkretnie?

A konkretnie x, y, z. Nie wiadomo co jest czym.

0

Nie wgłębiłem się w ten program, bo tak jak poprzednicy mówią, czytanie go to udręka, ale na pierwszy rzut oka:

void drzewo::usun_element(int licz){
    lisc *pomoc = new lisc(licz);
    lisc *x=szukaj(licz);
    if(x!=NULL) delete usuwanie(pomoc);
    else cout << "Zostala podana zla wartosc. " << endl;
}
  1. Wyciek pamięci. Masz pomoc = new lisc, a gdzie masz delete pomoc, np. gdy x == NULL?
  2. pomoc to zdaje się jakiś liść totalnie niepowiązany z drzewem, więc jaki sens ma usuwanie(pomoc)?
0

Dzieki za wszystko odpowiedzi, ale srednio mi sie przydaly prawde mowiac. Ma ktos moze przejrzysty kod na implementacje tego algorytmu?

1

Wystarczy narysować na kartce i masz:

void drzewo::replace(lisc *parent,lisc *child,lisc *node)
  {
   if(node) node->parent=parent;
   if(!parent) korzen=node;
   else if(parent->left==child) parent->left=node;
   else /*if(parent->right==child)*/ parent->right=node;
  }

lisc *drzewo::usuwanie(lisc *node)
  {
   lisc *parent=node->parent,*lf=node->left,*rt=node->right;
   if(!lf) replace(parent,node,rt);
   else if(!rt) replace(parent,node,lf);
   else 
     {
      for(lisc *tmp=rt;tmp->left;) tmp=tmp->left;
      swap(node->liczba,tmp->liczba);
      replace(tmp->parent,tmp,tmp->rt);
      node=tmp;
     }
   delete tmp;
  }

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