avltree.cpp

一个简单的华容道的算法；很适合初学者学习参考。

// AVLTree.cpp: implementation of the AVLTree class.
//
//////////////////////////////////////////////////////////////////////

#include "AVLTree.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

AVLTree::AVLTree():root(NULL)
{
}

AVLTree::~AVLTree()
{

}


bool AVLTree::Insert(AVLNode* &tree, ListNode vld, int &taller)
{
	bool success=false;
	if(tree == NULL)
	{
		tree = new AVLNode(vld,NULL,NULL);
		success = tree != NULL?true:false;
		if(success)
			taller = 1;
	}
	else if(vld<tree->ld)
	{
		success=Insert(tree->left,vld,taller);
		if(taller)
		{
			switch(tree->balance)
			{
			case -1:
				LeftBalance(tree,taller);break;
			case 0:
				tree->balance = -1;break;
			case 1:
				tree->balance = 0;
				taller = 0;
				break;
			}
		}
	}
	else if(vld>tree->ld)
	{
		success = Insert(tree->right,vld,taller);
		if(taller)
		{
			switch(tree->balance)
			{
			case -1:
				tree->balance = 0;
				taller = 0;
				break;
			case 0:
				tree->balance = 1;break;
			case 1:
				RightBalance(tree,taller);
				break;
			}
		}
	}
	else if(vld.equal(tree->ld))
	{
		success = 0;
		taller = 0;
	}
	return success;
}

void AVLTree::RotateLeft(AVLNode *tree, AVLNode* &newtree)
{
	newtree = tree->right;
	tree->right = newtree->left;
	newtree->left = tree;
}

void AVLTree::RotateRight(AVLNode *tree, AVLNode* &newtree)
{
	newtree = tree->left;
	tree->left = newtree->right;
	newtree->right = tree;
}

void AVLTree::LeftBalance(AVLNode* &tree, int &taller)
{
	AVLNode *leftsub = tree->left, *rightsub=NULL;
	switch(leftsub->balance)
	{
	case -1:
		tree->balance = leftsub->balance = 0;
		RotateRight(tree,tree);
		taller=0;
		break;
	case 0:
		break;
	case 1:
		rightsub = leftsub->right;
		switch(rightsub->balance)
		{
		case -1:
			tree->balance = 1; leftsub->balance = 0;break;
		case 0:
			tree->balance = leftsub->balance = 0;break;
		case 1:
			tree->balance = 0; leftsub->balance = -1;break;
		}
		rightsub->balance = 0;
		RotateLeft(leftsub,tree->left);
		RotateRight(tree,tree);
		taller = 0;
	}
}

void AVLTree::RightBalance(AVLNode* &tree, int &taller)
{
	AVLNode *rightsub = tree->right, *leftsub=NULL;
	switch(rightsub->balance)
	{
	case 1:
		tree->balance = rightsub->balance = 0;
		RotateLeft(tree,tree);
		taller = 0;
		break;
	case 0:
		break;
	case -1:
		leftsub = rightsub->left;
		switch(leftsub->balance)
		{
		case 1:
			tree->balance = -1;
			rightsub->balance = 0;
			break;
		case 0:
			tree->balance = rightsub->balance = 0;break;
		case -1:
			tree->balance = 0;
			rightsub->balance = 1;
			break;
		}
		leftsub->balance = 0;
		RotateRight(rightsub,tree->right);
		RotateLeft(tree,tree);
		taller = 0;
	}
}

int AVLTree::Hight(AVLNode *t)
{
	return 0;
}

bool AVLTree::Insert(ListNode vld)
{
	int taller;
	return Insert(this->root,vld,taller);
}