Help me to Implement the AVLtree's remove algorithm

Question

meiyantao 0 Light Poster

17 Years Ago

Hello! I want to implement a avltree using C++,and I have do most of it,except the remove() algorithm. My question is when should I rotate the tree in remove(). I hope that any body can represent the situation for me using the Pelple's language,because the implemented code depend on the data structure which you had used.

here ,I give you some of my code for a reference. In this code,all the avltree class's method could be used,except the remove().

main.cpp

is used to debug,and you can run it independent.
myt_avltree.h

is the hole class's head files.

By the way,there's another important question:
how to compile the template separately?
Would you use my code myt_avltree.h to give a example for me?

Help me to implement it,or give me some advances please.

Thank you very much!:) [INDENT]
[/INDENT]

c++

main.cpp (7.36 KB)

#include <iostream>
using namespace std;

template <typename AnyType>
class avltree {
protected:
	class avlnode;
public:
	avltree():root(0),size(0){}
	avltree(const avltree &rhs){
		*this = rhs;
	}
	~avltree()  { 
		cout<<"DESTROY!"<<endl;
		makeEmpty();
		cout<<"OK" ;
		}
	
	const avltree &operator=(const avltree &rhs){
		makeEmpty();
		root = clone(rhs.root);
		return *this;
	}
	/////////////
	long int getSize() const{
		return size;
	}
	/////////////////
	AnyType getData(avlnode *t) const{
		if(t!=0)
			return t->data;
	}
	
	/////////////////////////////////
	int getHeight(avlnode *t) const{
		return (t==0 ? -1 : t->height);
	}

	
	//Insert a specific node into the tree.
  bool insert(const AnyType &x){
		//Insert the avlnode.
		if(root == 0){
			root = new avlnode(x,0,0);
			++size;
			return true;
		}
		int top = 0;
		//This array Used to save the path that had passed.
		avlnode (**upd[HEIGHT_LIMIT]);
		upd[top++] = &root;		
		bool dir;
		while(*upd[top-1] != 0){
			//If x had been in the tree,insert() method return false.
			if(x == (*upd[top-1])->data)
				return false;
			dir = (x > (*upd[top-1])->data);
			upd[top++] = &( (*upd[top-1])->link[dir] );
		}	
		*upd[top-1] = new avlnode(x,0,0);
		++size;
		
		//Rebalance after insert.
		for(int i=top-1; i>=0; --i){
			bool dic1 = x < (*upd[i])->data;					
			//The situations that need to be rotated.
			if( getHeight((*upd[i])->link[!dic1])
						- getHeight((*upd[i])->link[dic1]) ==2 ){
				bool dic2 = x < (*upd[i])->link[!dic1]->data;
				//The single rotation situations.
				if(dic1 == dic2)
					singleRotation(*upd[i],dic2);				
				//The double rotation situations.
				else
					doubleRotation(*upd[i],dic2);
			}
			(*upd[i])->height =max( getHeight((*upd[i])->link[0]),
												  getHeight((*upd[i])->link[1]) )+1;	
		}
		//The new node x had inserted in the tree,and the tree 
		//has been rebalanced,then return true.
		return true;
	}
			
		
	//Remove a specific node of the tree.
	bool remove(const AnyType &x){
		if(root == 0)
			return false;

		avlnode (**upd[HEIGHT_LIMIT]);
		int top = 0;
		upd[top++] = &root;
		
		//Find the position of x.
		while((*upd[top-1])->data != x){
			bool dir = (x > (*upd[top-1])->data);
			upd[top++] = &( (*upd[top-1])->link[dir] );
			//If the tree hasn't the node x,then return false.
			if(*upd[top-1] == 0)
				return false;
		}
		
		//The save indicate the position of x-node,
		//the upd[top-1] now becomes the save's left subtree.
		do{
			if((*upd[top-1])->link[0] == 0 && (*upd[top-1])->link[1] == 0){
				delete *upd[top-1];
				*upd[top-1] = 0;
				top--;
				break;
			}
			
			int save = top-1;
			upd[top] = &( (*upd[top-1])->link[0] );
			top++;
			//Find the largest one of the subtree 
			//whose root is upd[save] (or upd[top-1]).
			while((*upd[top-1])->link[1] != 0)
				upd[top++] = &( (*upd[top-1])->link[1] );
				
		//Delete the avlnode with value x.
			(*upd[save])->data = (*upd[top-1])->data;		
			avlnode *tmp = *upd[top-1];
			cout<<"top="<<top<<endl;
			if(tmp->link[0] == 0){
				*upd[top-1] = 0;
				delete tmp;
				top--;
			}
			else{
				*upd[top-1] = (tmp->link[0]);
				delete tmp;
			}
			cout<<"top="<<top<<endl;
			cout<<"*top["<<(top-1)<<"]="<<(*upd[top-1])->data<<endl;
			size--;
		}while(0);
		//Rebalance after remove.
		for(int i=top-1; i>=0; --i){
			(*upd[i])->height =max( getHeight((*upd[i])->link[0]),
												  getHeight((*upd[i])->link[1]) )+1;
			bool dic1 =( getHeight((*upd[i])->link[0]) 										
									< 
									 getHeight((*upd[i])->link[1]) ); 
			if( getHeight((*upd[i])->link[dic1])
						- getHeight((*upd[i])->link[!dic1]) ==2 ){
				bool dic2 =
				( getHeight( (*upd[i])->link[dic1]->link[0] )
										 		>
					getHeight( (*upd[i])->link[dic1]->link[1] ) );
				//The single rotation situations.
				if(dic1 == dic2)
					singleRotation(*upd[i],dic2);
					
				//The double rotation situations.
				else
					doubleRotation(*upd[i],dic2);
			}
		}
		
	}

	//Destroy the whole tree.
	void makeEmpty(){
		avlnode *it = root;
		avlnode *save;
	
		while(it != 0){
			if(it->link[0] != 0){
				/*Right rotation */
				save = it->link[0];
				it->link[0] = save->link[1];
				save->link[1] = it;
			}
			else{
				save = it->link[1];
				delete it;
			}
			it = save;
		}
	root = 0;
	size = 0;
	}
	
	//Two way single rotation:dir equal to 1 as root_left_left,
	//dir equal to 0 as root_right_right.
	void singleRotation(avlnode* &t, bool dir){
		avlnode *save = t->link[!dir];
		t->link[!dir] = save->link[dir];
		save->link[dir] = t;
		t->height = max( getHeight(t->link[0]),getHeight(t->link[1]) ) + 1;
		save->height = max( getHeight(save->link[0]),
														getHeight(save->link[1]) ) + 1;		
		t = save;
	}
	
	//Two way double rotation:dir equal to 1 as root_right_left,
	//dir equal to 0 as root_left_right.
	void doubleRotation(avlnode* &t, bool dir){
	  avlnode *s1 = t->link[dir];
	  avlnode *s2 = s1->link[!dir];
	  t->link[dir] = s2->link[!dir];
	  s1->link[!dir] = s2->link[dir];
	  s2->link[dir] = s1;
	  s2->link[!dir] = t;
  	
		s1->height = max( getHeight(s1->link[0]),getHeight(s1->link[1]) ) + 1;		
		t->height  = max( getHeight(t->link[0]),getHeight(t->link[1]) ) + 1;
		s2->height = max( getHeight(s2->link[0]),getHeight(s2->link[1]) ) + 1;
		
		t=s2;
	}
	
	//Inorder trave the tree with a callback op.
 	void printTree() const{
		if(root == 0)
			return;
		avlnode *t = root;
		avlnode *up[HEIGHT_LIMIT];
		int top = 0;
	
		while(1){
			while(t->link[0] != 0){
				up[top++] = t;
				t = t-> link[0];
			}
			cout<<t->data<<'('<<t->height<<')'<<"->";
			while(t->link[1] ==0){
				if(top > 0){
					t = up[--top];
					cout<<t->data<<'('<<t->height<<')'<<"->";
				}
				else
					return;
			}
		t = t->link[1];	
		}
	}
	
	//Return the Max value of int.
	int max(int a,int b){
		return ( a>b ? a : b );
	}
	///////////////////////////
	//
	avlnode *clone(avlnode *t) const{
		if(t==0)
			return t;	
		return new avlnode( t->element,clone(t->link[0]),clone(t->link[1]) );
	}

protected:
	avlnode 		 *root;		// Top of the tree
  long int      size;   // Number of items (user-defined)
  //The tallest of the tree.
  static const int 		HEIGHT_LIMIT = 64;

protected:
  class avlnode 
	{
		explicit avlnode(const AnyType &InitData,avlnode *lt = 0,
				avlnode *rt = 0)
			: height(0),data(InitData){
				link[0] = lt;
				link[1] = rt;
		}
		int          height; 	// height factor
		AnyType        data;  // User-defined content 
		avlnode 	 *link[2]; 	// Left (0) and right (1) links
		friend class avltree;
	};
	
};




int main()
{
	cout<<endl<<endl<<"/*******************/";
	avltree<int> myAVL;

	myAVL.insert(1);
	myAVL.insert(3);
	myAVL.insert(2);
	myAVL.insert(4);
	myAVL.insert(7);
	myAVL.insert(6);
	myAVL.insert(5);	
	myAVL.insert(60);
	myAVL.insert(15);
	myAVL.insert(21);
	myAVL.remove(4);
	myAVL.insert(16);       
	myAVL.insert(37);
	myAVL.insert(14);
	
	myAVL.insert(2);
	myAVL.insert(2);
	myAVL.insert(2);
	myAVL.remove(16);
	
	cout<<endl<<endl;
	myAVL.printTree();
	cout<<endl;
	cout<<endl<<"The size is "<<myAVL.getSize()<<"."<<endl;
	cout<<"After makeEmpty(),";
	myAVL.makeEmpty();
	cout<<"the size is "<<myAVL.getSize()<<"."<<endl;
	cout<<"ok!"<<endl;
	char a;
	cin>>a;

}

myt_avltree.h (4.31 KB)

#ifndef MYT_AVLTREE_H
#define MYT_AVLTREE_H
namespace myt{

template <typename AnyType>
class avltree {
protected:
	class avlnode;
public:
	avltree():root(0),size(0){}
	avltree(const avltree &rhs){
		*this = rhs;
	}
	~avltree()  { makeEmpty(); }
	
	const avltree &operator=(const avltree &rhs){
		makeEmpty();
		root = clone(rhs.root);
		return *this;
	}
	/////////////
	long int getSize() const{
		return size;
	}
	/////////////////
	AnyType getData(avlnode *t) const{
		if(t!=0)
			return t->data;
	}
	
	/////////////////////////////////
	int getHeight(avlnode *t) const{
		return (t==0 ? -1 : t->height);
	}

  //Internal method to insert into a subtree.
  bool insert(const AnyType &x){
		//Insert the avlnode.
		if(root == 0){
			root = new avlnode(x,0,0);
			++size;
			return true;
		}
		//avlnode **t = &root;
		int top = 0;
		avlnode (**upd[HEIGHT_LIMIT]);
		upd[top++] = &root;
		
		bool dir;
		while(*upd[top-1] != 0){
			if(x == (*upd[top-1])->data)
				return false;
			dir = (x > (*upd[top-1])->data);
			upd[top++] = &( (*upd[top-1])->link[dir] );
		}	
		*upd[top-1] = new avlnode(x,0,0);
		++size;
		
		//Rebalance after insert.
		for(int i=top-1; i>=0; --i){
			bool dic1 = x < (*upd[i])->data;					
			//The situations that need to be rotated.
			if( getHeight((*upd[i])->link[!dic1])
						- getHeight((*upd[i])->link[dic1]) ==2 ){
				bool dic2 = x < (*upd[i])->link[!dic1]->data;
				//The single rotation situations.
				if(dic1 == dic2)
					singleRotation(*upd[i],dic2);
					
				//The double rotation situations.
				else
					doubleRotation(*upd[i],dic2);
					
			}
			(*upd[i])->height =max( getHeight((*upd[i])->link[0]),
												  getHeight((*upd[i])->link[1]) )+1;	
		}
		return true;
	}

	//Remove a specific node of the tree.
	bool remove(const AnyType &x){
		
	}

	//Destroy the whole tree.
	void makeEmpty(){
		while(root != 0){
			avlnode *t = root;
			while(t->link[0] != 0){
				singleRotation(t,1);		
			}
			root = t->link[1];
			delete t;
		}
		size = 0;
	}
	
	//Two way single rotation:dir equal to 1 as root_left_left,
	//dir equal to 0 as root_right_right.
	void singleRotation(avlnode* &t, bool dir){
		avlnode *save = t->link[!dir];
		t->link[!dir] = save->link[dir];
		save->link[dir] = t;
		t->height = max( getHeight(t->link[0]),getHeight(t->link[1]) ) + 1;
		save->height = max( getHeight(save->link[0]),
														getHeight(save->link[1]) ) + 1;		
		t = save;
	}
	
	//Two way double rotation:dir equal to 1 as root_right_left,
	//dir equal to 0 as root_left_right.
	void doubleRotation(avlnode* &t, bool dir){
	  avlnode *s1 = t->link[dir];
	  avlnode *s2 = s1->link[!dir];
	  t->link[dir] = s2->link[!dir];
	  s1->link[!dir] = s2->link[dir];
	  s2->link[dir] = s1;
	  s2->link[!dir] = t;
  	
		s1->height = max( getHeight(s1->link[0]),getHeight(s1->link[1]) ) + 1;		
		t->height  = max( getHeight(t->link[0]),getHeight(t->link[1]) ) + 1;
		s2->height = max( getHeight(s2->link[0]),getHeight(s2->link[1]) ) + 1;
		
		t=s2;
	}
	
	//Inorder trave the tree with a callback op.
	template<typename Operate>
 	void printTree(Operate op) const{
		avlnode *t = root;
		avlnode *up[HEIGHT_LIMIT];
		int top = 0;
	
		while(1){
			while(t->link[0] != 0){
				up[top++] = t;
				t = t-> link[0];
			}
			op(*t);
			while(t->link[1] ==0){
				if(top > 0){
					t = up[--top];
					op(*t);
				}
				else
					return;
			}
		t = t->link[1];	
		}
	}
	
	//Return the Max value of int.
	int max(int a,int b){
		return ( a>b ? a : b );
	}
	///////////////////////////
	avlnode *clone(avlnode *t) const{
		if(t==0)
			return t;	
		return new avlnode( t->element,clone(t->link[0]),clone(t->link[1]) );
	}



protected:
	avlnode 		 *root;		// Top of the tree
  long int      size;   // Number of items (user-defined)
  //The tallest of the tree.
  static const int 		HEIGHT_LIMIT = 64;

  class avlnode 
	{
		explicit avlnode(const AnyType &InitData,avlnode *lt = 0,
				avlnode *rt = 0)
			: height(0),data(InitData){
				link[0] = lt;
				link[1] = rt;
		}
		int          height; 	// height factor
		AnyType        data;  // User-defined content 
		avlnode 	 *link[2]; 	// Left (0) and right (1) links
		friend class avltree;
	};
	
};




















}
#endif

2 Contributors
2 Replies
150 Views
1 Day Discussion Span
Latest Post 17 Years Ago Latest Post by meiyantao

Hamrick 150 Posting Whiz

17 Years Ago

I don't really know that much about AVL trees, but someone posted a link the other day to a site that has this. It looks pretty easy to follow, so I hope that helps you. :)

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

meiyantao 0 Light Poster · Answer 1 · 2007-08-22T18:02:02+00:00

I don't really know that much about AVL trees, but someone posted a link the other day to a site that has this. It looks pretty easy to follow, so I hope that helps you. :)

Thank you very much!
But this page I have too,and I had read it.
Some important idears of my code referenced it,for example the "link[]". But my avltree's balance flag is different from it,so I can't solve the probolem use it.

Thank you all the same!;)