平衡查找二叉樹

AVL樹是平衡二叉查找樹。在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O（log n）。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個(gè)樹。它能保持二叉樹的高度平衡，盡量降低二叉樹的高度，減少樹的平均搜索長(zhǎng)度。

• AVL樹的性質(zhì)

1. 左子樹和右子樹的高度之差的絕對(duì)值不超過1

2. 樹中的每個(gè)左子樹和右子樹都是AVL樹

3. 節(jié)點(diǎn)的平衡因子是它的左子樹的高度減去它的右子樹的高度。帶有平衡因子 1、0 或 -1 的節(jié)點(diǎn)被認(rèn)為是平衡的。帶有平衡因子 -2 或 2 的節(jié)點(diǎn)被認(rèn)為是不平衡的，并需要重新平衡這個(gè)樹。平衡因子可以直接存儲(chǔ)在每個(gè)節(jié)點(diǎn)中，或從可能存儲(chǔ)在節(jié)點(diǎn)中的子樹高度計(jì)算出來。  

                  

#include<iostream>
using namespace std;
//平衡搜索二叉樹
template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(K& key, V& val)
		:_key(key)
		, _val(val)
		, _left(NULL)
		, _right(NULL)
		, _parent(NULL)
		, _bf(0)
	{}
	K _key;
	V _val;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;// Balance Factor
};
template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree()
		:_root(NULL)
	{}
	bool Insert(K& key,V& val)
	{
		if (_root == NULL)
		{
			_root = new Node(key, val);
			return true;
		}
		else
		{
			Node* cur = _root;
			Node* parent = NULL;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key>key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
					return false;
			}
			cur = new Node(key, val);
			if (parent->_key > key)
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
			//更新平衡因子，不平衡進(jìn)行旋轉(zhuǎn)

			while (parent != NULL)
			{
				if (cur == parent->_left)
					++parent->_bf;
				else
					--parent->_bf;
				//跳出條件
				if (parent->_bf == 0)
					break;
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					cur = parent;
					parent = cur->_parent;
				}
				else//-2 2旋轉(zhuǎn)
				{
					if (parent->_bf == 2)
					{
						if (1== cur->_bf)//右旋
						{
							RotateR(parent);
						}
						else//左右旋
						{
							RotateLR(parent);
						}
					}
					else
					{
						if (1== cur->_bf)//左右旋
						{
							RotateRL(parent);
						}
						else//左旋
						{
							RotateL(parent);
						}
					}
					break;
				}
			}
			return true;
		}
	}
	Node* Find(K& key)
	{
		if (_root == NULL)
			return false;
		else
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
					cur = cur->_left;
				else if (cur->_key < key)
					cur = cur->_right;
				else
					return cur;
			}
			return NULL;
		}
	}
	bool Remove(K& key)
	{
		if (_root == NULL)
			return false;
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key>key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				Node* del = NULL;
				if (cur->_left == NULL)
				{
					del = cur;
					if (cur == _root)
					{
						_root = cur->_right;
						_root->_parent = NULL;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
							cur->_parent = parent;
						}
						else
						{
							parent->_right = cur->_right;
							cur->_parent = parent;
						}
					}
				}
				else if (cur->_right==NULL)
				{
					del = cur;
					if (cur == _root)
					{
						_root = cur->_left;
						_root->_parent = NULL;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
							cur->_parent = parent;
						}
						else
						{
							parent->_right = cur->_left;
							cur->_parent = parent;
						}
					}
				}
				else//左右都不為空
				{
					Node* rightMin = root->_right;
					Node* parent = root;
					while (rightMin->_left)
					{
						parent = rightMin;
						rightMin = rightMin->_left;
					}
					root->_key = rightMin->_key;
					root->_val = rightMin->_val;
					del = rightMin;
					if (parent->_left == rightMin)
						parent->_left = NULL;
					else
						parent->_right = NULL;
				}
				delete del;
			}
		}
		return false;
	}
	void InOrder()
	{
		_InOrder(_root);
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	int Height()
	{
		return _Height(_root);
	}
protected:
	int _Height(Node* root)
	{
		if (root == NULL)
			return 0;
		int left = _Height(root->_left);
		int right = _Height(root->_right);
		return left > right ? left + 1 : right + 1;
	}
	bool _IsBalance(Node* root)
	{
		if (root == NULL)
			return true;
		int left = _Height(root->_left);
		int right = _Height(root->_right);
		if (left-right != root->_bf)
		{
			cout << "平衡因子錯(cuò)誤，不平衡" << root->_key << endl;
			return false;
		}
		return abs(left - right)<2&&_IsBalance(root->_left) && _IsBalance(root->_right);
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		Node* ppNode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;
		if (ppNode == NULL)
		{
			_root = subR;
			subR->_parent = NULL;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}
		subR->_bf = parent->_bf = 0;
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (ppNode == NULL)
		{
			_root = subL;
			subL->_parent = NULL;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
			subL->_parent = ppNode;
		}
		subL->_bf = parent->_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 = -1;
			subL->_bf = 0;
		}
		else if (bf == -1)
		{
			subL->_bf = 1;
			parent->_bf = 0;
		}
		else
			subL->_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)
		{
			parent->_bf = 0;
			subR->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 0;
			parent->_bf = 1;
		}
		else
			subR->_bf = parent->_bf = 0;
	}
private:
	Node* _root;
};
void Test1()
{
	AVLTree<int, int> t;
	int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		t.Insert(a[i], i);
	}
	t.InOrder();
	t.IsBalance();
}
int main()
{
	Test1();
	system("pause");
	return 0;
}