平衡查找二叉树

AVL树是平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

• AVL树的性质

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

2. 树中的每个左子树和右子树都是AVL树

3. 节点的平衡因子是它的左子树的高度减去它的右子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。  

                  

#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;	}	//更新平衡因子，不平衡进行旋转	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旋转	{	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 << "平衡因子错误，不平衡" << 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; }