【数据结构】二叉树、AVL树(2)

AVL树得名于其发明者G.M.Adelson-Velsky和E.M.Landis。AVL树是一个各结点具有平衡高度的扩展的二叉搜索树。在AVL树中，任一结点的两个子树的高度差最多为1，AVL树的高度不会超过1，AVL树既有二叉搜索树的搜索效率又可以避免二叉搜索树的最坏情况（退化树）出现。

AVL树的表示与二叉搜索树类似，其操作基本相同，但插入和删除方法除外，因为它们必须不断监控结点的左右子树的相对高度，这也正是AVL树的优势所在。

实现AVL树的相关运算

1、首先我们修改结构Binary_node，增加Balance_factor用以表示节点平衡情况

2、从二叉搜索树中派生出AVL树，编写其关键的插入和删除成员函数。

Error_code insert(const Record &new_data);
Error_code remove(const Record &old_data);

3、入和删除函数我们都用递归实现
编写递归函数：

Error_code avl_insert(Binary_node<Record>* &sub_root,const Record &new_data,bool &taller);
Error_code avl_remove(Binary_node<Record>* &sub_root,const Record &target,bool &shorter);

以及几个重要的调用函数：
左旋右旋函数：

void rotate_left(Binary_node<Record>* &sub_root);
void rotate_right(Binary_node<Record>* &sub_root);

两次旋转的左右平衡函数

void right_balance(Binary_node<Record>* &sub_root);
void left_balance(Binary_node<Record>* &sub_root);

删除函数还要分别编写删除左树和删除右树的递归函数

Error_code avl_remove_right(Binary_node<Record>&sub_root,bool &shorter);
Error_code avl_remove_left(Binary_node<Record>*&sub_root,bool &shorter);

?

4、个重要的成员函数代码如下：

template<class Record>
Error_code AVL_tree<Record>::insert(const Record &new_data)
//Post: If the key of new_data is already in the AVL_tree,a code of duplicate_error
//      is returned. Otherwise,a code of success is returned and the Record
//      new_data is inserted into the tree in such a way that the properties of an
//      AVL tree are preserved.
{
	bool taller;
	return avl_insert(root,new_data,taller);
}

template<class Record>
Error_code AVL_tree<Record>::avl_insert(Binary_node<Record>* &sub_root,bool &taller)
//Pre:  sub_root is either NULL or points to a subtree of the AVL tree
//Post: If the key of new_data is already in the subtree,a code of success is returned and the Record 
//      new_data is inserted into the subtree in such a way that the properties of 
//      an AVL tree have been preserved. If the subtree is increase in height,the
//      parameter taller is set to true; otherwise it is set to false
//Uses: Methods of struct AVL_node; functions avl_insert recursively,left_balance,and right_balance
{
	Error_code result=success;
	if(sub_root==NULL){
		sub_root=new Binary_node<Record>(new_data);
		taller=true;
	}
	else if(new_data==sub_root->data){
		result=duplicate_error;
		taller=false;
	}
	else if(new_data<sub_root->data){//Insert in left subtree
		result=avl_insert(sub_root->left,taller);
		if(taller==true)
			switch(sub_root->get_balance()){//Change balance factors
			case left_higher:
				left_balance(sub_root);
				taller=false;
				break;
			case equal_height:
				sub_root->set_balance(left_higher);
				break;
			case right_higher:
				sub_root->set_balance(equal_height);
				taller=false;
				break;
		}
	}
	else{        //Insert in right subtree
		result=avl_insert(sub_root->right,taller);
		if(taller==true)
			switch(sub_root->get_balance()){
			case left_higher:
				sub_root->set_balance(equal_height);
				taller=false;
				break;
			case equal_height:
				sub_root->set_balance(right_higher);
				break;
			case right_higher:
				right_balance(sub_root);
				taller=false; //Rebalancing always shortens the tree
				break;
		}
	}
	return result;
}

template<class Record>
void AVL_tree<Record>::right_balance(Binary_node<Record>* &sub_root)
//Pre:  sub_root points to a subtree of an AVL_tree that is doubly unbalanced
//      on the right
//Post: The AVL properties have been restored to the subtree
{
	Binary_node<Record>* &right_tree=sub_root->right;
	switch(right_tree->get_balance()){
	case right_higher:
		sub_root->set_balance(equal_height);
		right_tree->set_balance(equal_height);
		rotate_left(sub_root);
		break;
	case equal_height:
		cout<<"WARNING: program error detected in right_balance "<<endl;
	case left_higher:
		Binary_node<Record>*sub_tree=right_tree->left;
		switch(sub_tree->get_balance()){
		case equal_height:
			sub_root->set_balance(equal_height);
			right_tree->set_balance(equal_height);
			break;
		case left_higher:
			sub_root->set_balance(equal_height);
			right_tree->set_balance(right_higher);
		case right_higher:
			sub_root->set_balance(left_higher);
			right_tree->set_balance(equal_height);
			break;
		}
		sub_tree->set_balance(equal_height);
		rotate_right(right_tree);
		rotate_left(sub_root);
		break;
	}
}

template<class Record>
void AVL_tree<Record>::left_balance(Binary_node<Record>* &sub_root)
{
	Binary_node<Record>* &left_tree=sub_root->left;
	switch(left_tree->get_balance()){
	case left_higher:
		sub_root->set_balance(equal_height);
		left_tree->set_balance(equal_height);
		rotate_right(sub_root);
		break;
	case equal_height:
		cout<<"WARNING: program error detected in left_balance"<<endl;
	case right_higher:
		Binary_node<Record>*sub_tree=left_tree->right;
		switch(sub_tree->get_balance()){
		case equal_height:
			sub_root->set_balance(equal_height);
			left_tree->set_balance(equal_height);
			break;
		case right_higher:
			sub_root->set_balance(equal_height);
			left_tree->set_balance(left_higher);
			break;
		case left_higher:
			sub_root->set_balance(right_higher);
			left_tree->set_balance(equal_height);
			break;
		}
		sub_tree->set_balance(equal_height);
		rotate_left(left_tree);
		rotate_right(sub_root);
		break;
	}
}

template<class Record>
void AVL_tree<Record>::rotate_left(Binary_node<Record>* &sub_root)
//Pre:  sub_root points to a subtree of the AVL_tree. This subtree has 
//      a nonempty right subtree.
//Post: sub_root is reset to point to its former right child,and the 
//      former sub_root node is the left child of the new sub_root node
{
	if(sub_root==NULL||sub_root->right==NULL)//impossible cases
		cout<<"WARNING: program error detected in rotate_left"<<endl;
	else{
		Binary_node<Record>*right_tree=sub_root->right;
		sub_root->right=right_tree->left;
		right_tree->left=sub_root;
		sub_root=right_tree;
	}
}

template<class Record>
void AVL_tree<Record>::rotate_right(Binary_node<Record>*&sub_root)
{
	if(sub_root==NULL||sub_root->left==NULL)
		cout<<"WARNING:program error in detected in rotate_right"<<endl;
	else{
		Binary_node<Record>*left_tree=sub_root->left;
		sub_root->left=left_tree->right;
		left_tree->right=sub_root;
		sub_root=left_tree;
	}
}

template<class Record>
Error_code AVL_tree<Record>::remove(const Record &old_data)
{
	bool shorter;
	return avl_remove(root,old_data,shorter);
}

template<class Record>
Error_code AVL_tree<Record>::avl_remove(Binary_node<Record>* &sub_root,bool &shorter)
{
	Binary_node<Record>*temp;
	if(sub_root==NULL)return fail;
	else if(target<sub_root->data)
		return avl_remove_left(sub_root,target,shorter);
	else if(target>sub_root->data)
		return avl_remove_right(sub_root,shorter);
	else if(sub_root->left==NULL){//Found target: delete current node
		temp=sub_root;       //Move right subtree up to delete node
		sub_root=sub_root->right;
		delete temp;
		shorter=true;
	}
	else if(sub_root->right==NULL){
		temp=sub_root;   //Move left subtree up to delete node
		sub_root=sub_root->left;
		delete temp;
		shorter=true;
	}
	else if(sub_root->get_balance()==left_higher){
		//Neither subtree is empty; delete from the taller
		temp=sub_root->left;//Find predecessor of target and delete if from left tree
		while(temp->right!=NULL)temp=temp->right;
		sub_root->data=temp->data;
		avl_remove_left(sub_root,temp->data,shorter);
	}
	else{
		temp=sub_root->right;
		while(temp->left!=NULL)temp=temp->left;
		sub_root->data=temp->data;
		avl_remove_right(sub_root,shorter);
	}
	return success;
}

template<class Record>
Error_code AVL_tree<Record>::avl_remove_right(Binary_node<Record>
		   *&sub_root,bool &shorter)
{
	Error_code result=avl_remove(sub_root->right,shorter);
	if(shorter==true)switch(sub_root->get_balance()){
		case equal_height:
			sub_root->set_balance(left_higher);
			shorter=false;
			break;
		case right_higher:
			sub_root->set_balance(equal_height);
			break;
		case left_higher:
			Binary_node<Record>*temp=sub_root->left;
			switch(temp->get_balance()){
			case equal_height:
				temp->set_balance(right_higher);
				rotate_right(sub_root);
				shorter=false;
				break;
			case left_higher:
				sub_root->set_balance(equal_height);
				temp->set_balance(equal_height);
				rotate_right(sub_root);
				break;
			case right_higher:
				Binary_node<Record>*temp_right=temp->right;
				switch(temp_right->get_balance()){
				case equal_height:
					sub_root->set_balance(equal_height);
					temp->set_balance(equal_height);
					break;
				case left_higher:
					sub_root->set_balance(right_higher);
					temp->set_balance(equal_height);
					break;
				case right_higher:
					sub_root->set_balance(equal_height);
					temp->set_balance(left_higher);
					break;
				}
				temp_right->set_balance(equal_height);
				rotate_left(sub_root->left);
				rotate_right(sub_root);
				break;
			}
	}
	return result;
}

template<class Record>
Error_code AVL_tree<Record>::avl_remove_left(Binary_node<Record>
		   *&sub_root,bool &shorter)
{
	Error_code result=avl_remove(sub_root->left,shorter);
	if(shorter==true)
		switch(sub_root->get_balance()){
		case equal_height:
			sub_root->set_balance(right_higher);
			shorter=false;
			break;
		case left_higher:
			sub_root->set_balance(equal_height);
			break;
		case right_higher:
			Binary_node<Record>*temp=sub_root->right;
			switch(temp->get_balance()){
			case equal_height:
				temp->set_balance(left_higher);
				rotate_right(sub_root);
				shorter=false;
				break;
			case right_higher:
				sub_root->set_balance(equal_height);
				temp->set_balance(equal_height);
				rotate_left(sub_root);
				break;
			case left_higher:
				Binary_node<Record>*temp_left=temp->left;
				switch(temp_left->get_balance()){
				case equal_height:
					sub_root->set_balance(equal_height);
					temp->set_balance(equal_height);
					break;
				case right_higher:
					sub_root->set_balance(left_higher);
					temp->set_balance(equal_height);
					break;
				case left_higher:
					sub_root->set_balance(equal_height);
					temp->set_balance(right_higher);
					break;
				}
				temp_left->set_balance(equal_height);
				rotate_right(sub_root->right);
				rotate_left(sub_root);
				break;
			}
	}
	return result;
}

实验结果

（编辑：ASP站长网）