【アルゴリズム学習】AVLバランス二叉探索木の原理及び各操作プログラミング実現(C++)

12250 ワード

データ構造とアルゴリズム

AVLTree(Adelson-Velskii-Landis Tree)は、追加条件を加えた二叉探索ツリーである.その平衡条件の確立は,木全体の深さがO(nLogn)であることを確保するためである.平衡条件は、任意のノードの左右のサブツリーの高さの差が1を超えないことである.
以下のコードでは,プログラミングによりAVLツリーの作成,検索,挿入,削除,遍歴などの操作が実現される.C++クラスパッケージを採用.
AVLツリーで複雑な操作の場合は挿入と削除操作を行います.ここでは挿入と削除の操作について説明します.
AVLツリーの挿入操作
AVLツリーに要素を挿入すると、ツリーのバランスが崩れる可能性があります.ただし,挿入点からルートノードへの経路が平衡状態を満たさない各ノードの中で最も深さが大きいものを調整するだけでよい.最も深いノードをXとします.Xのバランスを失うには4つのケースがあります.
(1)挿入点がXの左サブノードにある左サブツリー-左左.
(2)挿入点がXの左サブノードの右サブツリー−左右にある.
(3)挿入点がXの右サブノードにある左サブツリー-右左.
(4)挿入点がXの右サブノードにある左サブツリー-右.
ケース1と4は対称で,外側挿入となり,単回転で解決できる.ケース2と3も対称で、内側に挿入されます.二重回転で解決します.
ケース1について、一回転例を実施する.
ケース2について二重回転を実施する例:
AVLツリーの削除操作
削除操作もいくつかのケースに分けられます.
まず、ノードの要素値が削除する要素に等しいかどうかをツリーで検索します.検索されない場合は、直接戻ります.そうでない場合は、次の操作を行います.
(1)削除するノードは現在のルートノードTである.
左右のサブツリーが空でなければ.高さの大きいサブツリーで削除を実行します.
2つのケースに分けられます.
A、左サブツリーの高さが右サブツリーの高さより大きい場合、左サブツリーの最大の要素を現在のルートノードに割り当て、左サブツリーの要素値が最大のノードを削除します.
B、左サブツリーの高さが右サブツリーの高さより小さい場合、右サブツリーの最小要素を現在のルートノードに割り当て、右サブツリーの最小要素値のノードを削除します.
左右のサブツリーの1つが空の場合は、現在のルートノードをその非空のサブツリーまたはNULLで直接置き換えることができます.
(2)削除するノード要素の値は現在のルートノードTの値より小さく,左サブツリーで削除する.
再帰的に呼び出し、左サブツリーで削除を実行します.
これは、現在のルートノードが平衡条件を満たしているかどうかを判断する必要があり、
平衡条件が満たされると、現在のルートノードTの高さ情報を更新するだけでよい.
そうでない場合は、回転調整が必要です.
Tの左サブノードの左サブツリーの高さがTの左サブノードの右サブツリーの高さより大きい場合、対応する単一回転が行われる.そうでない場合は、2回転します.
(3)削除するノード要素の値が現在のルートノードTの値より大きく、右サブツリーで削除する.
プロセスは上記の手順と同様です.
具体的にはコードを見てください.
ここには私がプログラミングして実装したコードだけがリストされています.バグを発見したり、訂正したりします.
AVLTree.h:

#ifndef AVLTREE_H_INCLUDED
#define AVLTREE_H_INCLUDED

//AVL       
typedef int ElementType;//AVL         

//   
typedef struct AVLNode{
	ElementType element;//         
	AVLNode *left;//     
	AVLNode *right;//     
	int height;//       
}*AVLTree;

//AVL tree   
class CAVLTree{
private:
	//        
	int getHeight(AVLTree);//      

	void setHeight(AVLTree,int);//        

	//   ：    
	AVLTree SingleRightRotate(AVLTree);
	//   ：    
	AVLTree SingleLeftRotate(AVLTree);
	//   ：  
	AVLTree DoubleRightRotate(AVLTree);
	//   ：  
	AVLTree DoubleLeftRotate(AVLTree);

public:
	//      
	CAVLTree();
	//    
	~CAVLTree();
	//  AVL 
	void createAVLTree(ElementType *data,int n);
	//    
	AVLTree insertNode(AVLTree T,ElementType val);
	//              
	AVLTree deleteNode(AVLTree T,const ElementType val);
	//            
	AVLTree searchNode(AVLTree,ElementType);
	//       
	void preOrder(AVLTree T);
	//             
	AVLTree getMaxNode(AVLTree);
	//               
	AVLTree getMinNode(AVLTree);

	AVLTree T;
};

#endif // AVLTREE_H_INCLUDED

AVLTree.cpp:

#include "AVLTree.h"

#include 
#include 
#include 

using namespace std;

CAVLTree::CAVLTree()
{
	T = NULL;
}

CAVLTree::~CAVLTree()
{
	//if(T)
	//{
	//	if(NULL == T->left && NULL == T->right)
	//		delete T;
	//	else{
	//		delete T->left;
	//		delete T->right;
	//	}
	//}
	deleteTree(T);
}

//         ，  AVL 
void CAVLTree::createAVLTree(ElementType *data,int n)
{
	if (T)
	{
		cout << "The AVL Tree has been created" << endl;

		return;
	}

	if(!n)//      
	{
		T = NULL;
		return;
	}

	for(int i = 0;i < n;++i)
	{
		T = insertNode(T,*(data + i));
	}

	return;
}

AVLTree CAVLTree::insertNode(AVLTree T,ElementType val)
{
	AVLNode *pNewNode = new AVLNode;
	pNewNode->element = val;
	pNewNode->left = NULL;
	pNewNode->right = NULL;
	pNewNode->height = 1;//               

	if(NULL == T)
	{
		T = pNewNode;
		return T;
	}

	//          
	//            ，     
	if (val == T->element)
	{
		cout << "      ，  AVL   ！" << endl;
		return T;
	}
	//            ，        
	if(val < T->element)
	{
		//            
		T->left = insertNode(T->left,val);
		//            
		if(getHeight(T->left) - getHeight(T->right) > 1)
		{
			//           
			//     T         
			if(val < T->left->element)
				//     -   
				T = SingleRightRotate(T);
			else
				//     T         ，      
				T = DoubleRightRotate(T);
		}
	}
	//            ，        
	if(val > T->element)
	{
		T->right = insertNode(T->right,val);
		//            
		if(getHeight(T->right) - getHeight(T->left) > 1)
		{
			//     T          
			if(val > T->right->element)
				//     -   
				T = SingleLeftRotate(T);
			else
				//     T          
				//     -   
				T = DoubleLeftRotate(T);
		}
	}

	//     height 
	setHeight(T,max(getHeight(T->left),getHeight(T->right)) + 1);

	return T;
}

AVLTree CAVLTree::deleteNode(AVLTree T,const ElementType val)
{
	if (!T)
	{
		cout << "The tree is NULL, delete failed" << endl;
		return T;
	}

	AVLTree searchedNode = searchNode(T,val);
	//         ，    
	if (!searchedNode)
	{
		cout << "Cann't find the node to delete " << val << endl;
		return T;
	} 
	
	//          
	//                 
	if (val == T->element)
	{
		//       
		if (T->left && T->right)
		{
			//                 
			if (getHeight(T->left) > getHeight(T->right))
			{
				//      ，                ，           
				T->element = getMaxNode(T->left)->element;
				T->left = deleteNode(T->left,T->element);
			}
			else{
				//                ，           
				T->element = getMinNode(T->right)->element;
				T->right = deleteNode(T->right,T->element);
			}
		}
		else{
			//           ，                      
			AVLTree oldNode = T;
			T = (T->left ? T->left : T->right);
			delete oldNode;//         
			oldNode = NULL;
		}
	}
	else if (val < T->element)//           
	{
		//           
		T->left = deleteNode(T->left,val);
		//            
		if (getHeight(T->right) - getHeight(T->left) > 1)
		{
			if (T->right->left > T->right->right)
			{
				//    
				T = DoubleLeftRotate(T);
			}
			else//      
				T = SingleLeftRotate(T);
		}
		else
			//      ，        
			T->height = max(getHeight(T->left),getHeight(T->right)) + 1;
	}
	else//            
	{
		T->right = deleteNode(T->right,val);
		//          
		if (getHeight(T->left) - getHeight(T->right) > 1)
		{
			if(getHeight(T->left->right) > getHeight(T->left->left))
				//    
				T = DoubleRightRotate(T);
			else
				//    
				T = SingleRightRotate(T);
		}
		else
			//        
			T->height = max(getHeight(T->left),getHeight(T->right)) + 1;
	}

	return T;
}

AVLTree CAVLTree::searchNode(AVLTree T,ElementType val)
{
	if (!T)
	{
		return NULL;
	}

	//   
	if (val == T->element)
	{
		return T;
	}
	else if (val < T->element)
	{
		//       
		return searchNode(T->left,val);
	}
	else
	{
		//       
		return searchNode(T->right,val);
	}
}

void CAVLTree::preOrder(AVLTree T)
{
	if(!T)
		cout << "NULL ";
	else
	{
		cout << T->element << " ";
		preOrder(T->left);
		preOrder(T->right);
	}
}

AVLTree CAVLTree::getMaxNode(AVLTree T)
{
	if (!T)//   
	{
		return NULL;
	}

	AVLTree tempNode = T;
	//           NULL
	while(tempNode->right)
	{
		tempNode = tempNode->right;
	}

	return tempNode;
}

AVLTree CAVLTree::getMinNode(AVLTree T)
{
	if (!T)//   
	{
		return NULL;
	}

	AVLTree tempNode = T;
	//           NULL
	while(tempNode->left)
	{
		tempNode = tempNode->left;
	}

	return tempNode;
}

int CAVLTree::getHeight(AVLTree T)
{
	return (T == NULL) ? 0 : (T->height);
}

void CAVLTree::setHeight(AVLTree T,int height)
{
	T->height = height;
}

//            ，     -       
//    ：
//T：                   
AVLTree CAVLTree::SingleRightRotate(AVLTree T)
{
	AVLTree xPNode = T;
	AVLTree yPNode = T->left;
	xPNode->left = yPNode->right;//          
	yPNode->right = xPNode;//             

	//               
	xPNode->height = max(getHeight(xPNode->left),getHeight(xPNode->right)) + 1;
	yPNode->height = max(getHeight(yPNode->left),getHeight(yPNode->right)) + 1;

	//                 
	return yPNode;
}

//            ，     -       
//    ：
//T：                   
AVLTree CAVLTree::SingleLeftRotate(AVLTree T)
{
	AVLTree xPNode = T;
	AVLTree yPNode = T->right;

	xPNode->right = yPNode->left;//          
	yPNode->left = xPNode;//                  

	//                 
	xPNode->height = max(getHeight(xPNode->left),getHeight(xPNode->right)) + 1;
	yPNode->height = max(getHeight(yPNode->left),getHeight(yPNode->right)) + 1;

	//       
	return yPNode;
}

//     T         
AVLTree CAVLTree::DoubleRightRotate(AVLTree T)
{
	//              
	//      
	assert(T->left != NULL);
	//            -   
	T->left = SingleLeftRotate(T->left);
	//      
	//             -   
	return SingleRightRotate(T);
}

//     T         
AVLTree CAVLTree::DoubleLeftRotate(AVLTree T)
{
	//              
	//      
	assert(T->right != NULL);
	//            -   
	T->right = SingleRightRotate(T->right);
	//      
	//             -   
	return SingleLeftRotate(T);
}


void CAVLTree::deleteTree(AVLTree t)
{
	if(NULL == t)
		return;

	deleteTree(t->left);
	deleteTree(t->right);
	delete t;
	t = NULL;
}

main.cpp:

//        （AVL tree-Adelson-Velskii-Landis tree）    
//  ：    
//  ：2012-12-10

#include "AVLTree.h"
#include 

using namespace std;

int main()
{
	const int NumElements = 5;
	cout << "AVL         ：" << endl;
	int a[NumElements] ={18,14,20,12,16};
	CAVLTree *CAVLTreeObj1 = new CAVLTree();
	CAVLTreeObj1->createAVLTree(a,NumElements);
	cout << "AVL Tree      ：" << endl;
	CAVLTreeObj1->preOrder(CAVLTreeObj1->T);
	cout << endl;

	int insertedVal1 = 15;
	CAVLTreeObj1->T = CAVLTreeObj1->insertNode(CAVLTreeObj1->T,insertedVal1);
	cout << " AVL        " << insertedVal1 << "         ：" << endl;
	CAVLTreeObj1->preOrder(CAVLTreeObj1->T);
	cout << endl;

	int insertedVal2 = 16;
	CAVLTreeObj1->T = CAVLTreeObj1->insertNode(CAVLTreeObj1->T,insertedVal2);
	cout << " AVL        " << insertedVal2 << "         ：" << endl;
	CAVLTreeObj1->preOrder(CAVLTreeObj1->T);
	cout << endl;

	int minVal = CAVLTreeObj1->getMinNode(CAVLTreeObj1->T)->element;
	cout << "        ：" << minVal << endl;

	int maxVal = CAVLTreeObj1->getMaxNode(CAVLTreeObj1->T)->element;
	cout << "        ：" << maxVal << endl;

	const int deletedVal1 = 11;
	CAVLTreeObj1->T = CAVLTreeObj1->deleteNode(CAVLTreeObj1->T,deletedVal1);
	cout << "       " << deletedVal1 << "             ：" << endl;
	CAVLTreeObj1->preOrder(CAVLTreeObj1->T);
	cout << endl;

	const int deletedVal2 = 20;
	CAVLTreeObj1->T = CAVLTreeObj1->deleteNode(CAVLTreeObj1->T,deletedVal2);
	cout << "       " << deletedVal2 << "             ：" << endl;
	CAVLTreeObj1->preOrder(CAVLTreeObj1->T);
	cout << endl;

	const int deletedVal3 = 18;
	CAVLTreeObj1->T = CAVLTreeObj1->deleteNode(CAVLTreeObj1->T,deletedVal3);
	cout << "       " << deletedVal3 << "             ：" << endl;
	CAVLTreeObj1->preOrder(CAVLTreeObj1->T);
	cout << endl;

	const int searchedVal1 = 12;
	AVLTree searchedPNode = CAVLTreeObj1->searchNode(CAVLTreeObj1->T,searchedVal1);
	if(!searchedPNode)
		cout << "cannot find such node whose elemen equals " << searchedVal1 << endl;
	else
		cout << "search success element " << searchedVal1 << endl;

	const int searchedVal2 = 13;
	searchedPNode = CAVLTreeObj1->searchNode(CAVLTreeObj1->T,searchedVal2);
	if(!searchedPNode)
		cout << "cannot find such node whose elemen equals " << searchedVal2 << endl;
	else
		cout << "search success element " << searchedVal2 << endl;

	return 0;
}

実行結果(Win 7+VS 2008):
上記の木の操作についての絵の説明は以下の通りです(携帯電話で撮影したのですが、ちょっとわかりません):

【C++】Structの定義