удаление из АВЛ-дерева

[Maikl Korleone]

Имеется задание: написать программу которая бы удаляла заданный элемент из АВЛ-дерева.

Я написал такой код:

#include<iostream.h>#define TRUE 1#define FALSE 0struct node{ int Key;  int Count;  int bal;  node *Left;  node *Right;};class TREE { public: //private:int h;node *Tree; //public:TREE () { Tree=NULL; h=FALSE;}void Search (int, node **);void Vyvod (node **, int);node** GetTree() {return &Tree;}void del_tree(int, node **);void del_el(node **);void bal_left(node **);void bal_right(node **);};void main (){ TREE A; int el,i; int n;FILE  *infile;bool flag=0;//,g=0,l=0;//int nN;char c;//node *t1,*t2;infile=fopen("input.txt","rb");  //открытие файлаif (!infile) //проверка наличия файла{cout << "Error: open 'input.txt'.";	flag=1;   	//return -1;}if ((flag==0)&&(c=getc(infile)==EOF)) //проверка файла на пустоту			flag=1;fclose(infile);if (flag==0){infile=fopen("input.txt","rb"); while(!feof(infile)){	 fscanf(infile,"%d",&el);	 A.Search (el,A.GetTree());	} fclose(infile);}else{ printf("File clear!"); //return -1;} //cout<<"Количество вершин в дереве: "; //cin>>n; //cout<<"Информационные поля вершин дерева: \n"; //for (i=1; i<=n; i++)//{ cin>>el; A.Search (el,A.GetTree());}  cout<<"AVL-tree:\n"; A.Vyvod (A.GetTree(),0);  cout<<"\nInput deleted node: ";  cin>>el;  A.del_tree(el,&A.Tree);  cout<<"\nAVL-tree:\n";  A.Vyvod (A.GetTree(),0);  cin>>el;}void TREE::Search (int x, node **p)// x - ключ вершины, помещаемой в АВЛ-дерево.// *p - указатель на корень АВЛ-дерева.// h - флаг, сигнализирующий об увеличении высоты поддерева:// TRUE - высота поддерева увеличилась, // FALSE - высота поддерева не увеличилась.// При первом обращении к функции Search() h=FALSE.{ node *p1, *p2; h = FALSE; if (*p==NULL)  {  *p = new(node);  h = TRUE; (**p).Key = x;   (**p).Count = 1; (**p).Left = (**p).Right = NULL;  (**p).bal = 0; } else   if (x<=(**p).Key)   {	Search (x,&((**p).Left)); 	if (h==TRUE)	  switch ((**p).bal)	  {		case 1 :  (**p).bal = 0; h = FALSE; break;		case 0 : (**p).bal = -1; break;		case -1:				 p1 = (**p).Left;				 if ((*p1).bal==-1)				 {	(**p).Left = (*p1).Right;					  (*p1).Right = *p;					  (**p).bal = 0; *p = p1; }				 else {				   p2 = (*p1).Right;				   (*p1).Right = (*p2).Left;				   (*p2).Left = p1;				   (**p).Left = (*p2).Right;				   (*p2).Right = *p;				   if ((*p2).bal==-1) (**p).bal = 1;				   else (**p).bal = 0;				   if ((*p2).bal==1) (*p1).bal = -1;				   else (*p1).bal = 0;				   *p = p2;				 }				 (**p).bal = 0; h = FALSE;				 break;	  }  }  elseif (x>(**p).Key) {	Search (x,&((**p).Right)); 	 if (h==TRUE)	   switch ((**p).bal)	   {		  case -1:  (**p).bal = 0; h = FALSE; break;		  case  0: (**p).bal = 1; break;		  case  1:				p1 = (**p).Right;				if ((*p1).bal==1)				{	(**p).Right = (*p1).Left;					 (*p1).Left = *p; (**p).bal = 0; *p = p1;				}				else				{	 p2 = (*p1).Left; (*p1).Left = (*p2).Right;					  (*p2).Right = p1; (**p).Right = (*p2).Left;					  (*p2).Left = *p;					  if ((*p2).bal==1) (**p).bal = -1;					  else (**p).bal = 0;					  if ((*p2).bal==-1) (*p1).bal = 1;					  else (*p1).bal = 0;					  *p = p2;				} 				(**p).bal = 0; h = FALSE; break;	   }}}void TREE::Vyvod (node **w,int l)//Изображение дерева w на экране дисплея//		 (рекурсивный алгоритм).//*w - указатель на корень дерева.{ int i; if  (*w!=NULL) {Vyvod (&((**w).Right),l+1);for  (i=1; i<=l; i++) cout<<"   ";cout<<(**w).Key<<endl;Vyvod (&((**w).Left),l+1); }}void TREE::del_tree(int x,node **tr){node *v=new node;v->Left=NULL;v->Right=NULL;if (tr==NULL) cout<<"Tree is nothing!\n";else{ if (x<(*tr)->Key) {  del_tree(x,&(*tr)->Left);  //левый поворот  bal_right(tr); } elseif (x>(*tr)->Key){ del_tree(x,&(*tr)->Right); //правый поворот bal_left(tr);}else{ v=*tr; if (v->Right==NULL) {  tr=&v->Left;  h=TRUE; } else   if (v->Left==NULL)   {	tr=&v->Right;	h=TRUE;   }   else   {	del_el(&v->Left);	//левый паворот	bal_right(tr);   }}}}void TREE::del_el(node **tr){if ((*tr)->Right!=NULL){ del_el(&(*tr)->Right); //bal_left}else{ node *v=new node; v->Key=(*tr)->Key; v=*tr; tr=&(*tr)->Left; h=TRUE;}}void TREE::bal_right(node **p){node *p1, *p2;if (h==TRUE)	   switch ((**p).bal)	   {		  case -1:  (**p).bal = 0; h = FALSE; break;		  case  0: (**p).bal = 1; h = FALSE; break;		  case  1:				p1 = (**p).Right;				if (((*p1).bal==1)||(*p1).bal==0)				{	(**p).Right = (*p1).Left;					 (*p1).Left = *p;					 //(*p).bal = 0;					 if ((*p1).bal==0)					 {					  (*p)->bal=1;					  p1->bal=-1;					  h=FALSE;					 }					 else					 {					  (*p)->bal=0;					  p1->bal=0;					 }					 *p = p1;				}				else				{	 p2 = (*p1).Left; (*p1).Left = (*p2).Right;					  (*p2).Right = p1; (**p).Right = (*p2).Left;					  (*p2).Left = *p;					  if ((*p2).bal==1) (**p).bal = -1;					  else (**p).bal = 0;					  if ((*p2).bal==-1) (*p1).bal = 1;					  else (*p1).bal = 0;					  *p = p2;				}				//(*p).bal = 0; //h = FALSE;				break;	   } //Vyvod (&Tree,0);}void TREE::bal_left(node **p){node *p1, *p2;if (h==TRUE)	  switch ((**p).bal)	  {		case 1 :  (**p).bal = 0; h = FALSE; break;		case 0 : (**p).bal = -1; h = FALSE; break;		case -1:				 p1 = (**p).Left;				 if (((*p1).bal==-1)||(*p1).bal==0)				 {	(**p).Left = (*p1).Right;					  (*p1).Right = *p;					  //(*p).bal = 0;					  if ((*p1).bal==0)					 {					  (*p)->bal=-1;					  p1->bal=1;					  h=FALSE;					 }					 else					 {					  (*p)->bal=0;					  p1->bal=0;					 }					  *p = p1;				 }				 else {				   p2 = (*p1).Right;				   (*p1).Right = (*p2).Left;				   (*p2).Left = p1;				   (**p).Left = (*p2).Right;				   (*p2).Right = *p;				   if ((*p2).bal==-1) (**p).bal = 1;				   else (**p).bal = 0;				   if ((*p2).bal==1) (*p1).bal = -1;				   else (*p1).bal = 0;				   *p = p2;				 }				 //(*p).bal = 0; //h = FALSE;				 break;	  } //Vyvod (&Tree,0);}

Построение дерева работает правильно, а вот с удалением возникли проблемы. Повороты вроде выполняются верно, но когда выводишь измененное дерево то оно выводится или вообще без изменений, либо правильно повернутое но удаляемый элемент при этом остается.

[Maikl Korleone]

За не имением советов пришлось разбираться самому, оказалось напутал с передачей параметров в методы.

Выкладываю полностью рабочий код реализующий удаление из АВЛ-дерева элементов с ключами из заданного диапазона, может кому пригодится:

#include<iostream.h>#define TRUE 1#define FALSE 0struct node{ int Key;  int Count;  int bal;  node *Left;  node *Right;};class TREE { public: //private:int h;node *Tree; //public:TREE () { Tree=NULL; h=FALSE;}void Search (int, node **);void Vyvod (node **, int);node** GetTree() {return &Tree;}void del_tree(int, node **);void del_el(node **, node **);void bal_left(node **);void bal_right(node **);};void main (){ TREE A; int el,el1,i; int n;FILE  *infile;bool flag=0;char c;infile=fopen("input.txt","rb");  //открытие файлаif (!infile) //проверка наличия файла{cout << "Error: open 'input.txt'.";	flag=1;}if ((flag==0)&&(c=getc(infile)==EOF)) //проверка файла на пустоту			flag=1;fclose(infile);if (flag==0){infile=fopen("input.txt","rb"); while(!feof(infile)){	 fscanf(infile,"%d",&el);	 A.Search (el,A.GetTree());	} fclose(infile);}else{ printf("File clear!");} //Вывод дерева cout<<"AVL-tree:\n"; A.Vyvod (A.GetTree(),0); cout<<"\nInput breach of deleted node: "; //ввод интервала удаляемых элементов cin>>el; cin>>el1; while (el<=el1) {  A.del_tree(el,&A.Tree);  el++; }  cout<<"\nAVL-tree:\n";  A.Vyvod (A.GetTree(),0);  cin>>el;}void TREE::Search (int x, node **p)//вставка элемента{ node *p1, *p2; h = FALSE; if (*p==NULL)  {  *p = new(node);  h = TRUE; (**p).Key = x;  (**p).Count = 1; (**p).Left = (**p).Right = NULL;  (**p).bal = 0; } else  if (x<=(**p).Key)  {	Search (x,&((**p).Left));	if (h==TRUE)	  switch ((**p).bal)	  {		case 1 :  (**p).bal = 0; h = FALSE; break;		case 0 : (**p).bal = -1; break;		case -1:			 // LL-поворот				 p1 = (**p).Left;				 if ((*p1).bal==-1)				 {	(**p).Left = (*p1).Right;					  (*p1).Right = *p;					  (**p).bal = 0; *p = p1; }				 else {	 // LR-поворот				   p2 = (*p1).Right;				   (*p1).Right = (*p2).Left;				   (*p2).Left = p1;				   (**p).Left = (*p2).Right;				   (*p2).Right = *p;				   if ((*p2).bal==-1) (**p).bal = 1;				   else (**p).bal = 0;				   if ((*p2).bal==1) (*p1).bal = -1;				   else (*p1).bal = 0;				   *p = p2;				 }				 (**p).bal = 0; h = FALSE;				 break;	  }  }  elseif (x>(**p).Key){	Search (x,&((**p).Right));	 if (h==TRUE)	   switch ((**p).bal)	   {		  case -1:  (**p).bal = 0; h = FALSE; break;		  case  0: (**p).bal = 1; break;		  case  1:			// RR-поворот				p1 = (**p).Right;				if ((*p1).bal==1)				{	(**p).Right = (*p1).Left;					 (*p1).Left = *p; (**p).bal = 0; *p = p1;				}				else		// RL-поворот				{	 p2 = (*p1).Left; (*p1).Left = (*p2).Right;					  (*p2).Right = p1; (**p).Right = (*p2).Left;					  (*p2).Left = *p;					  if ((*p2).bal==1) (**p).bal = -1;					  else (**p).bal = 0;					  if ((*p2).bal==-1) (*p1).bal = 1;					  else (*p1).bal = 0;					  *p = p2;				} 				(**p).bal = 0; h = FALSE; break;	   }}}void TREE::Vyvod (node **w,int l)//Вывод дерева на экран{ int i; if  (*w!=NULL) {Vyvod (&((**w).Right),l+1);for  (i=1; i<=l; i++) cout<<"   ";cout<<(**w).Key<<endl;Vyvod (&((**w).Left),l+1); }}void TREE::del_tree(int x,node **tr)//удаление элемента{node *v=new node;v->Left=NULL;v->Right=NULL;if (tr==NULL) cout<<"Tree is nothing!\n";else{ if (x<(*tr)->Key) {  del_tree(x,&(*tr)->Left);  //левый поворот  bal_right(tr); } elseif (x>(*tr)->Key){ del_tree(x,&(*tr)->Right); //правый поворот bal_left(tr);}else{ v=*tr; if (v->Right==NULL) {  *tr=v->Left;  h=TRUE; } else   if (v->Left==NULL)   {	*tr=v->Right;	h=TRUE;   }   else   {	del_el(&v->Left,&v);	//левый паворот	bal_right(tr);   }}}}void TREE::del_el(node **tr,node **v)//обработка случая когда удаляемый элемент имеет двух потомков{if ((*tr)->Right!=NULL){ del_el(&(*tr)->Right,v); bal_left(tr);}else{ (*v)->Key=(*tr)->Key; v=tr; *tr=(*tr)->Left; h=TRUE;}}void TREE::bal_right(node **p)//восстановление баланса при удалении из левого поддерева{node *p1, *p2;if (h==TRUE)	   switch ((**p).bal)	   {		  case -1:  (**p).bal = 0; h = FALSE; break;		  case  0: (**p).bal = 1; h = FALSE; break;		  case  1:				p1 = (**p).Right;				if (((*p1).bal==1)||(*p1).bal==0)				{	(**p).Right = (*p1).Left;					 (*p1).Left = *p;					 //(*p).bal = 0;					 if ((*p1).bal==0)					 {					  (*p)->bal=1;					  p1->bal=-1;					  h=FALSE;					 }					 else					 {					  (*p)->bal=0;					  p1->bal=0;					 }					 *p = p1;				}				else				{	 p2 = (*p1).Left; (*p1).Left = (*p2).Right;					  (*p2).Right = p1; (**p).Right = (*p2).Left;					  (*p2).Left = *p;					  if ((*p2).bal==1) (**p).bal = -1;					  else (**p).bal = 0;					  if ((*p2).bal==-1) (*p1).bal = 1;					  else (*p1).bal = 0;					  *p = p2;				}				break;	   }}void TREE::bal_left(node **p)//восстановление баланса при удалении из правого поддерева{node *p1, *p2;if (h==TRUE)	  switch ((**p).bal)	  {		case 1 :  (**p).bal = 0; h = FALSE; break;		case 0 : (**p).bal = -1; h = FALSE; break;		case -1:				 p1 = (**p).Left;				 if (((*p1).bal==-1)||(*p1).bal==0)				 {	(**p).Left = (*p1).Right;					  (*p1).Right = *p;					  //(*p).bal = 0;					  if ((*p1).bal==0)					 {					  (*p)->bal=-1;					  p1->bal=1;					  h=FALSE;					 }					 else					 {					  (*p)->bal=0;					  p1->bal=0;					 }					  *p = p1;				 }				 else {				   p2 = (*p1).Right;				   (*p1).Right = (*p2).Left;				   (*p2).Left = p1;				   (**p).Left = (*p2).Right;				   (*p2).Right = *p;				   if ((*p2).bal==-1) (**p).bal = 1;				   else (**p).bal = 0;				   if ((*p2).bal==1) (*p1).bal = -1;				   else (*p1).bal = 0;				   *p = p2;				 }				 break;	  } }