【数据结构】AVL树详解

AVL树又称平衡二叉搜索树，它能保证二叉树高度相对平衡，尽量降低二叉树的高度，提高搜索效率。单纯的二叉搜索树在最坏的情况下插入查找删除等操作时间复杂度会是O(N),

例如：

所以，AVL树就能避免这种情况，使得增删查改的时间复杂度为O(lgN). （ps:这里的lgN指的是log以2为底的N。）那么AVL树是怎么做到的呢，看看它的特点你就大概知道了：

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

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

3.>每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,1。(每个节点的平衡因子等于右子树的高度减去左子 树的高度 ) .

思考这样一个问题，既然保证了二叉树的高度之差不超过1就能降低时间复杂度，那直接保证左右子树高度相同岂不是更好？当然是不行的，假如这棵树只有两个节点，那要怎么办呢？所以，我们只能保证高度差不能超过1 。

按照普通的插入，如果给一个数组是：1,2,3,4,5,6,7 ，一定会导致上面图的那种情况，所以，我们要进行调整。那么什么情况下需要调整，怎么调呢？

需要调整的情况大概分为以下几种：

1>需要右单旋：

图片是一种直观的表现，过程是这个样子的：

先将p节点的右树（如果存在的话）当做g的左树，断开了p,g的原始关系，再让p的右指向g，建立新的联系。这里注意，因为我的AVL树时三叉链结构（左，右，父）在让g的父亲节点指向p之前需要先保存g的父亲节点。因为，如果g的父亲存在的话，最后要让它指向p（如上图）。旋转没什么难的，但是要注意平衡因子的调整。然后就是要细心，一定要注意三叉链在改变指针指向的时候也要改变父亲指针的指向！博主就这里不知道自己当时哪里抽了好几处没有改变父亲节点的指向，虽然这个错误很容易找到，但是还是要花费我宝贵的时间！

2>需要左单旋：

右单旋与左单旋类似，就是节点的名称我改变了一下，方便大家理解代码。

3>需要左右双旋

可以看到，左右双旋其实是先以p为轴左旋一次，再以g为轴右旋一次。但实际上如果左右旋只调用两个单旋是会出现问题的。没错，问题就出在平衡因子上。按照上面说单旋时的结点位置变化情况，我们可以画一张图来表示右左单旋最终结点的变化情况。

4>需要右左双旋：

与左右双旋类似，右左双旋也是先右旋后左旋，对平衡因子的处理也跟左右双旋很类似，根据它结点最终的位置确定平衡因子。

1>如果根节点为空，直接插入赋给根节点

2>通过关键码先找到插入的位置，如果找到了与给定关键码相同的码，则插入失败（key结构和key+value结构都不允许树中出现重复关键码，会导致查找出错）

3>插入，插到左边平衡因子减一，插到右边加一

4>检查是否平衡，不平衡则调节至平衡（具体代码里有注释做了相关解释）

思想：递归算出每个结点的左右树高度，用右树减左树的数值和结点的平衡因子比较，如果相等，则该节点平衡，就这样递归去判断。

上述问题的代码实现：

#include<iostream>

using namespace std;

template<class K,class V>
struct AVLtreeNode    //结点结构体
{
	typedef AVLtreeNode<K,V> Node;
	Node* _left;
	Node* _right;
	Node* _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 (NULL == _root)
		{
			_root = new Node(key,value);
			return true;
		}
		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;
			}

		}
		if (parent->_key < key)
		{
			Node* tmp = new Node(key,value);
			parent->_right = tmp;
			tmp->_parent = parent;
			parent->_bf++;
		}
		if (parent->_key>key)
		{
			Node* tmp = new Node(key,value);
			parent->_left = tmp;
			tmp->_parent = parent;
			parent->_bf--;
		}
		while (parent)
		{
			if (parent->_bf == 0)  //原来是1或者-1，那插入以后不会对树的高度有影响;
			{
				return true;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) //原来是0，对树的高度有影响
			{
				Node* pparent = parent->_parent;
				if (pparent != NULL)
				{
					if (pparent->_left == parent)// 左树上高度增加
						pparent->_bf--;
					else //右树上高度增加
						pparent->_bf++;
				}

				parent = pparent;
			}
			else //平衡因子是2/-2，从1或者-1变过来，不满足平衡树，需要旋转
			{
				if (parent->_bf == 2)  //右树过高
				{
					if (parent->_right->_bf == 1) //需要左旋结构
					{
						_RotateL(parent);
						return true;
					}
					else if (parent->_right->_bf = -1)  //需要右左旋结构
					{
						_RotateRL(parent);
						return true;
					}
				}
				else //平衡因子为-2
				{
					if (parent->_left->_bf == -1)  //需要右单旋的结构
					{
						_RotateR(parent);
						return true;
					}
					else if (parent->_left->_bf == 1) //需要左右旋的结构
					{
						_RotateLR(parent);
						return true;
					}
				}
			}
		}
	}
	

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

protected:
	bool _IsBalance(Node* root)
	{
		if (NULL == root)
			return true;
		int bf = _Depth(root->_right) - _Depth(root->_left);
		if (bf == root->_bf)
			return true;
		else
		{
			cout << root->_key << "平衡因子异常" << endl;
			return false;
		}
			
		return _IsBalance(root->_left);
		return _IsBalance(root->_right);
	}

	int _Depth(Node* root)
	{
		if (NULL == root)
			return 0;
		int left = _Depth(root->_left)+1;
		int right = _Depth(root->_right) + 1;
		return left > right ? left : right;
	}


	void _InOrder(Node* root)
	{
		if (NULL == root)
			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* pparent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

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

	void _RotateR(Node* parent)    //右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* pparent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (pparent == NULL)
		{
			_root = subL;
			subL->_parent = NULL;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
				subL->_parent = pparent;
			}
			else
			{
				pparent->_right = subL;
				subL->_parent = pparent;
			}			
		}
		parent->_bf = subL->_bf = 0;
	}

	void _RotateRL(Node* parent)    //右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;  //必须记录下来，旋转后发生改变
		_RotateR(subR);
		_RotateL(parent);

		if (bf == 0)    //插入后子树根节点为0，高度没有受到影响，则调整后父节点和祖父结点的平衡因子为0
		{
			parent->_bf = subRL->_bf=subR->_bf = 0;
		}
		else if (bf == 1)  //插入后右树高，右树给了subR的左边，所以subR的平衡因子为0，左树高度低于右树，给了parent的右树所以parent的平衡因子为1
		{
			parent->_bf = -1;
			subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)//插入后左树高，右树给了subR的左边，所以subR的平衡因子为1，左树高度低于右树，给了parent的右树所以parent的平衡因子为0
		{
			parent->_bf = subRL->_bf = 0;
			subR->_bf = 1;
		}
	}

	void _RotateLR(Node* parent)   //左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		_RotateL(subL);
		_RotateR(parent);

		if (bf == 0)
			parent->_bf =subLR->_bf= subL->_bf = 0;
		else if (bf == 1)
		{
			parent->_bf = subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = subLR->_bf = 0;
		}
	}
private:
	Node* _root;
};

void TestAVLtree()
{
	AVLtree<int,int> tree;
	int a[] = { 16,7,11,9,26,18,14,15 };
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		tree.Insert(a[i],i);
		cout << "isbalance?"<<tree.IsBalance() <<"插入"<< a[i] << endl;
	}
	tree.InOrder();
	tree.IsBalance();
	AVLtree<int,int> tree1;
	int a1[] = { 4,1,15,16,14 };
	for (size_t i = 0; i < sizeof(a1) / sizeof(a1[0]); i++)
	{
		tree1.Insert(a1[i],i);
		cout << "isbalance?" << tree1.IsBalance() << "插入" << a1[i] << endl;
	}
	tree1.InOrder();
}

如果有没写清楚或者写错了的地方请多指教