AVL樹又稱高度平衡的二叉搜索樹，是1962年俄羅斯的數(shù)學(xué)家提出來的。它能保持二叉樹的高度平衡，盡量降低二叉樹的高度，減少樹的平均搜索長度。

創(chuàng)新互聯(lián)長期為上千家客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為瑞安企業(yè)提供專業(yè)的成都做網(wǎng)站、成都網(wǎng)站建設(shè)，瑞安網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

AVL的性質(zhì)：

（1）左子樹和右子樹的高度之差的絕對值不超過1。

    （2）樹中的每個左子樹和右子樹都是AVL樹。

    （3）每個節(jié)點都有一個平衡因子，任一節(jié)點的平衡因子是-1，0，1（每個節(jié)點的平衡因子等于右子樹的高度減去左子樹的高度）。

代碼實現(xiàn)如下：

#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;
		}
		//更新平衡因子
		//不平衡，則進行旋轉(zhuǎn)
		while (parent)
		{
			if (parent->_right==cur)
				parent->_bf++;
			else
				parent->_bf--;
			//父節(jié)點平衡因子為0時，退出（說明父節(jié)點的兩邊高度一樣，算路徑長度的話都一樣，沒有影響）
			if (parent->_bf == 0)
				break;
			//父節(jié)點平衡因子為1或-1的時候（說明是從0+1或0-1得來的），父節(jié)點兩邊高度不同，故需要繼續(xù)更新平衡因子
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//父節(jié)點平衡因子為2或-2時，旋轉(zhuǎn)
			else  //(parent->_bf==2||parent->_bf==-2) 旋轉(zhuǎn)
			{
				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;
}

 實現(xiàn)結(jié)果：

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享題目：平衡二叉搜索樹-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://weahome.cn/article/cedide.html