数据结构【AVL树】

1.AVL树

1.AVL的概念

AVL树可以是一个空树。
它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在 log^N ，那么增删查改的效率也可以控制在O(log^N ) ，相比二叉搜索树有了本质的提升。

2.平衡因子

结点的平衡因子=右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像⼀个风向标一样。
为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？
因为例如二和四个结点无法达到0.

2.AVl树的实现

2.1AVL树的结构

template<class K, class V>
struct AVLTreeNode
{
	// 需要parent指针，后续更新平衡因⼦可以看到
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; // balance factor
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{
	}
};
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	//...
private:
	Node * _root = nullptr;
};

2.2AVL树的插入

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
		cur = new Node(kv);
	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	// 更新平衡因⼦
	while (parent)
	{
		// 更新平衡因⼦
		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 = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 不平衡了，旋转处理
			break;
		}
		else
		{
			assert(false);
		}
	}
	return true;
}

2.3 旋转

2.3.1 旋转的原则

保持搜索树的规则
让旋转的树从不满足变平衡，其次降低旋转树的高度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。