C++実装の完全なツリープログラム

この2,3日伸張木を習って、先生のいくつかのソースコードを参考にして自分で完全な実現過程を書いてみました.しかし、プログラムに誤りがあることに気づいて、自分でデバッグを始め、細かくデバッグし、一歩一歩追跡することで、自分が発見した問題を解決しました.この過程で、ストレッチツリーのストレッチ過程は複雑ですが、自分もそこから自分のデバッグプログラムの能力を高め、ストレッチツリープログラムの実行過程に対する理解を深めました.もし皆さんが以下のプログラムの問題を発見したら、一緒に交流して勉強してください.

#include <iostream>
using namespace std;

struct Node
{
	Node* lc,*rc,*par;
	int val,weight; //weight         
}*root;


//     ( x   )
void rRotate(Node* x)
{
	//   x    
	Node* y=x->par;
	y->lc=x->rc;
	//x        
	if(x->rc) x->rc->par=y;
	
	//  x
	x->par=y->par;
	// y    
	if(y->par)
	{
		if(y==y->par->lc)
			y->par->lc=x;
		else
			y->par->rc=x;
	}
	//  y
	x->rc=y;
	y->par=x;
}


//     ( x   )
void lRotate(Node* x)
{
	//   x    
	Node* y=x->par;
	y->rc=x->lc;
	if(x->lc) x->lc->par=y;
	
	//  x
	x->par=y->par;
	// y    
	if(y->par)
	{
		if(y==y->par->lc)
			y->par->lc=x;
		else
			y->par->rc=x;
	}
	//  y
	x->lc=y;
	y->par=x;
}

//   x    y      
void Splay(Node* x,Node* y)
{
	while(x->par!=y)
	{
		//    
		if(x->par->par==y)
		{
			//  x            
			(x->par->lc==x)? rRotate(x):lRotate(x);
		}
		else
		{
			//  x           
			if(x->par->par->lc==x->par)
			{
				//    
				if(x->par->lc==x)
				{
					//    
					rRotate(x->par);
					rRotate(x);
				}
				//    
				else
				{
					//      
					lRotate(x);
					rRotate(x);
				}
			}
			else
			{
				//    
				if(x->par->rc==x)
				{
					//    
					lRotate(x->par);
					lRotate(x);
				}
				//    
				else
				{
					//      
					rRotate(x);
					lRotate(x);
				}
			}
		}
	}
	//  y  ，  x   
	if(0==y) root=x;
}


//       
bool find(Node* x,int key)
{
	if(!x) return false;

	//   
	if(x->val==key)
	{
		Splay(x,0); // x     
		return true;
	}
	else
	{
		//        
		if(x->val>key)
			return find(x->lc,key);
		else
			return find(x->rc,key);
	}
}

//    
void insert(int key)
{
	Node *ptr=root,*y=0;

	int lrChose=0; //         y         
	while(true)
	{
		//       
		if(!ptr)
		{
			ptr=new Node;
			ptr->lc=ptr->rc=0;
			ptr->val=key;
			ptr->weight=1;
			ptr->par=y;
			if(y!=0)
			{
				if(0==lrChose) y->lc=ptr;
				else y->rc=ptr;
			}

			Splay(ptr,0); //   
			break;
		}

		y=ptr;
		if(key==ptr->val)
		{
			++ptr->weight;
			Splay(ptr,0);
			break;
		}
		else
			if(key<ptr->val)
			{
				ptr=ptr->lc;
				lrChose=0;//       y        
			}
			else
			{
				ptr=ptr->rc;
				lrChose=1; //       y        
			}
	}
}

void preOrder(Node* r)
{
	if(r!=0)
	{
		for(int i=0;i<r->weight;++i)
			cout<<r->val<<" ";

		preOrder(r->lc);
		preOrder(r->rc);
	}
}


//        
Node* join(Node* n1,Node* n2)
{
	// n1 n2        
	if(n1) n1->par=0;
	if(n2) n2->par=0;

	//                
	if(!n1) return n2;
	if(!n2) return n1;

	n1->par=n2->par=0;

	Node* temp=n1;
	//  n1      (    )
	while(temp->rc) temp=temp->rc; 

	Splay(temp,0); // temp     (  temp      temp    )

	temp->rc=n2;
	n2->par=temp;

	return temp; //        
}

//       
void remove(Node* x)
{
	Splay(x,0); //  x     
	root=join(x->lc,x->rc); //      
	delete x; //    x   
}

//     
void delMin(int& min,int& cnt)
{
	Node* x=root;
	//       
	while(x->lc) x=x->lc;
	//                
	min=x->val;
	cnt=x->weight;

	remove(x);
}

//     
void delMax(int& max,int& cnt)
{
	Node* x=root;
	//       
	while(x->rc) x=x->rc;
	//                
	max=x->val;
	cnt=x->weight;

	remove(x);
}


int main()
{
	//test
	int val=0;

	while(cin>>val)
		insert(val);

	preOrder(root); //    
	cout<<endl;

	cin.clear(); //     


	int findNum=0;
	cout<<"Enter the integer you want find:";
	cin>>findNum;
	if(find(root,findNum))
		cout<<"Has found!"<<endl;
	else
		cout<<"Has not found!"<<endl;


	int max=0,min=0,cnt=0;
	delMin(min,cnt);
	cout<<"min:"<<min<<",num:"<<cnt<<endl;

	delMax(max,cnt);
	cout<<"max:"<<max<<",num:"<<cnt<<endl;
}

ツリーを伸ばすことで、入力したデータが特殊な場合、生成されたツリーはチェーンテーブルのようにプログラムの効率を低下させ、一般的なソートツリーが形成されると、構造が変更されにくいため、効率に影響を与え続ける.一方、ストレッチツリーは、構築されたばかりのときにも発生する可能性がありますが、操作が多ければ多いほど構造が最適化され、アルゴリズムの効率が高くなります.同じ操作を実行するたびにほとんどストレッチを行い、ツリー構造が合理的になるからです.これはまさに私たちがプロジェクトをしたり、システムをしたりするために考慮しなければならないことです.どのように自分のシステムをますます最適化するかは、ますます悪くなって、私たちがプロジェクトをしているすべての人が考えなければならない問題ではありません.