平衡二叉搜索树

      AVL树又称高度平衡的二叉搜索树，是1962年俄罗斯的数学家提出来的。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

成都创新互联专注于章丘企业网站建设,自适应网站建设,商城网站开发。章丘网站建设公司,为章丘等地区提供建站服务。全流程按需网站制作，专业设计，全程项目跟踪，成都创新互联专业和态度为您提供的服务

    AVL的性质：

    （1）左子树和右子树的高度之差的绝对值不超过1。

    （2）树中的每个左子树和右子树都是AVL树。

    （3）每个节点都有一个平衡因子，任一节点的平衡因子是-1，0，1（每个节点的平衡因子等于右子树的高度减去左子树的高度）。

代码实现如下：

#include
using namespace std;

template
struct AVLTreeNode{
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;

	K _key;
	V _value;
	int  _bf;   //平衡因子

	AVLTreeNode(const K& key,const V& value)
		:_key(key)
		, _value(value)
		, _left(NULL)
		, _right(NULL)
		, _parent(NULL)
		, _bf(0)
	{}
};

template
class AVLTree{
	typedef AVLTreeNode Node;
public:
	AVLTree()
		:_root(NULL)
	{}
	bool Insert(const K& key, const V& value)
	{
		if (_root == NULL)
		{
			_root = new Node(key,value);
			return true;
		}
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key,value);
		if (parent->_key > key)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		//更新平衡因子
		//不平衡，则进行旋转
		while (parent)
		{
			if (parent->_right==cur)
				parent->_bf++;
			else
				parent->_bf--;
			//父节点平衡因子为0时，退出（说明父节点的两边高度一样，算路径长度的话都一样，没有影响）
			if (parent->_bf == 0)
				break;
			//父节点平衡因子为1或-1的时候（说明是从0+1或0-1得来的），父节点两边高度不同，故需要继续更新平衡因子
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//父节点平衡因子为2或-2时，旋转
			else  //(parent->_bf==2||parent->_bf==-2) 旋转
			{
				if (parent->_bf == -2)
				{
					if (cur->_bf == -1)//右单旋
					{
						_RotateR(parent);
					}
					else //(cur->_bf==1) 左右单旋
					{
						_RotateLR(parent);
					}
				}
				else //(parent->_bf==2)
				{
					if (cur->_bf == 1)  //左单旋
					{
						_RotateL(parent);
					}
					else  //(cur->_bf==-1)右左单旋
					{
						_RotateRL(parent);
					}
				}
				break;
			}
		}
	}
	Node* Find(const K& key)
	{
		if (_root == NULL)
			return false;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
				cur = cur->_left;
			else if (cur->_key < key)
				cur = cur->_right;
			else
				return cur;
		}
		return false;
	}
	bool Remove(const K& key)
	{
		if (_root == NULL)
			return false;

		Node* parent = NULL;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				Node* del;
				if (cur->_right == NULL)
				{
					del = cur;
					if (parent == NULL)
					{
						_root = cur->_left;
						//_root->_bf = 0;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
							parent->_bf++;
						}
						else
						{
							parent->_right = cur->_left;
							parent->_bf--;
						}
					}
					delete del;
				}
				else if (cur->_left == NULL)
				{
					del = cur;
					if (parent == NULL)
					{
						_root = cur->_right;
						_root->_bf = 0;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
							parent->_bf++;
						}
						else
						{
							parent->_right = cur->_right;
							parent->_bf--;
						}
					}
					delete del;
				}
				else
				{
					parent = cur;
					Node* left = cur->_right;
					while (left->_left)
					{
						parent = left;
						left = left->_left;
					}
					del = left;
					cur->_key = left->_key;
					cur->_value = left->_value;
					if (parent->_left == left)
					{
						parent->_left = left->_right;
						parent->_bf++;
					}
					else
					{
						parent->_right = left->_right;
						parent->_bf--;
					}

					delete del;
				}
				break;
			}
		}
		if (cur == NULL)
		{
			return false;
		}
		while (parent)
		{
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				break;
			}
			else //parent->_bf=2||parent->_bf=-2
			{
				if (parent->_bf == -2)
				{
					if (cur->_bf == -1)
						_RotateR(parent);
					else  //cur->_bf=1
						_RotateLR(parent);
				}
				else
				{
					if (cur->_bf == 1)
						_RotateL(parent);
					else
						_RotateRL(parent);
				}
				break;
			}
		}
		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	//判断这棵树是否是平衡搜索树
	bool IsBlance()
	{
		return _IsBlance(_root);
	}
protected:
	void _RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR=subL->_right;

		parent->_left = subLR;
		if (subLR != NULL)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		if (ppNode == NULL)
		{
			_root = subL;
			subL->_parent = NULL;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
				subL->_parent = ppNode;
			}
			else
			{
				ppNode->_right = subL;
				subL->_parent = ppNode;
			}
		}
		subL->_bf = parent->_bf = 0;
	}

	void _RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL= subR->_left;

		parent->_right = subRL;
		if (subRL != NULL)
		{
			subRL->_parent = parent;
		}

		subR->_left = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subR;
		if (ppNode == NULL)
		{
			_root = subR;
			subR->_parent = NULL;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
				subR->_parent = ppNode;
			}
			else
			{
				ppNode->_right = subR;
				subR->_parent = ppNode;
			}
		}
		subR->_bf = parent->_bf = 0;
	}

	void _RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL= subR->_left;
		int bf = subRL->_bf;

		_RotateR(parent->_right);
		_RotateL(parent);

		if (bf == 1) //从subRL的右边插入
		{
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == -1) //从subRL的左边插入
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else    //(bf=0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
		subRL->_bf = 0;
	}
	void _RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		_RotateL(parent->_left);
		_RotateR(parent);

		if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
		}
		else   //bf=0
		{
			parent->_bf = 0;
			subL->_bf = 0;
		}
		subLR->_bf = 0;
	}
	bool _IsBlance(Node* root)
	{
		if (root == NULL)
			return true;
		int right = _Height(root->_right);
		int left = _Height(root->_left);
		if (right - left != root->_bf || abs(right - left) >= 2)
		{
			cout << "平衡因子异常" << root->_key << endl;
		}
		return _IsBlance(root->_left) && _IsBlance(root->_right);
	}
	int _Height(Node* root)
	{
		if (root == NULL)
			return 0;
		int right = _Height(root->_right);
		int left = _Height(root->_left);
		if (right > left)
			return (right + 1);
		else
			return (left + 1);
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}
		else
		{
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
	}
protected:
	Node* _root;
};



#include "AVLTree.h"
void Test1()
{
	int a[9] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	AVLTree avl;
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		avl.Insert(a[i],i);
	}
	avl.InOrder();
	cout<* ret1 = avl.Find(18);
	if (ret1)
		cout << ret1->_key << ":" << ret1->_value << endl;
	else
		cout << "不存在ret1" << endl;

	AVLTreeNode* ret2 = avl.Find(1);
	if (ret2)
		cout << ret2->_key << ":" << ret2->_value << endl;
	else
		cout << "不存在ret2" << endl;

	avl.Remove(26);
	avl.Remove(18);
	avl.Remove(15);
	avl.InOrder();

	avl.Remove(3);
	cout << avl.Remove(7) << endl;
	avl.Remove(7);
	avl.Remove(9); 
	avl.Remove(11);
	avl.Remove(14);
	avl.Remove(15);
	cout << avl.Remove(100) << endl;
	avl.Remove(16);
	avl.Remove(18);
	avl.Remove(26);

	avl.InOrder();
}
void Test2()
{
	int a[10] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree avl;
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		avl.Insert(a[i], i);
	}
	avl.InOrder();
	cout << avl.IsBlance() << endl;

	AVLTreeNode* ret1 = avl.Find(5);
	if (ret1)
		cout << ret1->_key << ":" << ret1->_value << endl;
	else
		cout << "不存在ret1" << endl;

	AVLTreeNode* ret2 = avl.Find(88);
	if (ret2)
		cout << ret2->_key << ":" << ret2->_value << endl;
	else
		cout << "不存在ret2" << endl;

	avl.Remove(14);
	avl.Remove(16);
	avl.Remove(7);
	avl.InOrder();

	avl.Remove(15);
	avl.Remove(6);
	avl.Remove(5);
	cout << avl.Remove(4) << endl;
	avl.Remove(4);
	avl.Remove(3);
	avl.Remove(2);
	avl.Remove(1);
	cout << avl.Remove(100) << endl;
	avl.Remove(7);
	avl.Remove(16);

	avl.InOrder();
}
int main()
{
	Test1();
	cout << endl;
	cout << endl;
	Test2();
	return 0;
}

  实现结果：