平衡二叉搜索樹

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

    AVL的性質(zhì)：

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

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

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

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

#include<iostream>
using namespace std;

template<class K,class V>
struct AVLTreeNode{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _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 K,class V>
class AVLTree{
	typedef AVLTreeNode<K, V> 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<int, int> avl;
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		avl.Insert(a[i],i);
	}
	avl.InOrder();
	cout<<avl.IsBlance()<<endl;

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

	AVLTreeNode<int, int>* 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<int, int> avl;
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		avl.Insert(a[i], i);
	}
	avl.InOrder();
	cout << avl.IsBlance() << endl;

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

	AVLTreeNode<int, int>* 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é)果：