[数据结构与算法]数据结构---AVL树

介绍

AVL树是二叉搜索树的优化，他能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

---

注意：

1. 他的左右子树都是AVL树
2. 每个结点的左右子树高度之差的绝对值(一般用平衡因子记录)不超过1
3. 如果一棵二叉搜索树是高度平衡的，它就是AVL树
   如果它有n个结点，其高度可保持在O(log₂N) ，搜索时间复杂度O(log₂N)

1）定义一个AVL树

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;//这里采用三叉链结构，是为了方便之后的 “旋转” 找到父节点
	pair<K, V> _kv;//作为map，set的底层，需要一个键值对
	int _bf; //balance factor = 右子树高度-左子树的高度
	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

注意：

1. 采用三叉链结构，是为了方便之后的 “旋转” 找到父节点
2. 作为map，set的底层，需要一个键值对
3. 需要一个变量记录平衡因子

2）AVL树的插入

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree()
		:_root(nullptr)
	{}
	bool Insert(const pair<K, V>& kv){};
	void RotateL(Node* parent){};
	void RotateR(Node* parent){};
	void RotateLR(Node* parent){};
	void RotateRL(Node* parent){};
private:
	Node* _root;

①插入的第一部分逻辑

前面部分的插入逻辑和搜索二叉树的插入一模一样，解释略(比当前节点值大就右，反之左)

if (_root == nullptr)
{
	_root = new Node(kv);
	return true;
}
Node* parent = _root;
Node* cur = _root;
while (cur)
{
	if (cur->_kv.first > kv.first)
	{
		parent = cur;
		cur = cur->_left;
	}
	else if (cur->_kv.first < kv.first)
	{
		parent = cur;
		cur = cur->_right;
	}
	else
		return false;//不允许重复(二叉搜索树)
}
if (parent->_kv.first > kv.first)
{
	cur = new Node(kv);
	parent->_left = cur;
	cur->_parent = parent;
}
else
{
	cur = new Node(kv);
	parent->_right = cur;
	cur->_parent = parent;
}

②插入的第二部分逻辑+AVL树的旋转

逻辑部分

注意，增加一个节点，只会改变当前路径的平衡因子，同时共有6种情况
分别为：

1. 插入更新的节点在父亲的左边，父亲平衡因子–
2. 插入更新的节点在父亲的右边，父亲平衡因子++
3. 父亲的平衡因子更新以后是0，说明父亲所在子树的高度没变,不需要继续往上更新
4. 父亲的平衡因子更新以后是1或-1,说明父亲所在子树高度变了,需要继续往上更新
5. 更新以后父亲的平衡因子是2或-2,说明父亲所在的子树已经不平衡了，需要旋转处理，达到平衡
6. 更新到了根节点就不需要在更新

代码如下：

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)//说明父亲所在的子树已经不平衡了，需要旋转处理，达到平衡
	{
		if (parent->_bf == -2 && cur->_bf == -1)//左单旋（直线->单旋）
			RotateR(parent);
		else if (parent->_bf == 2 && cur->_bf == 1)//右单旋（直线->单旋）
			RotateL(parent);
		else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋（折线->双旋）
			RotateLR(parent);
		else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋（折线->双旋）
			RotateRL(parent);
		else
			assert(false);
		break;
	}
	else
		assert(false);
}

右单旋

即隶属于parent->_bf == 2 || parent->_bf == -2的子情况：parent->_bf == 2 && cur->_bf == 1

插入在左子树的左边

注意：

1. 因为我们要求子树都必须是AVL树，所有图中的null部分都可以用一棵高度不为0的AVL树代替，图中展示了详细旋转过程
2. 因为我们是三叉链，所以旋转后不要忘了讲子节点的_parent正确指向
3. 图中第二步5的右孩子为空，这里这种情况是特殊情况，nullptr不能指向任何节点(所以不需要将空指针的父节点正确指向)
4. 7这个节点可能是根节点(_root)，也可能之上还有节点，分情况讨论
5. 注意：插入在左子树的右边我们归属在双旋的情况里

void RotateR(Node* parent)
	{
		Node* sub = parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* sub_parent = sub->_parent;
		sub->_left = subLR;
		if (subLR)//将subLR给给sub的左，如果subLR为nullptr，subLR->_parent = sub空指针指向报错
			subLR->_parent = sub;
		subL->_right = sub;
		sub->_parent = subL;
		if (sub_parent == nullptr)//也相当于_root==parent(root==sub)
		{
			subL->_parent = nullptr;
			_root = subL;
		}
		else//sub上面还有节点
		{
			subL->_parent = sub_parent;
			if (sub_parent->_left == sub)//值永远写左边！！！！！
				sub_parent->_left = subL;
			else
				sub_parent->_right = subL;
			
		}
		sub->_bf = subL->_bf = 0;
	}

左单旋

即隶属于parent->_bf == 2 || parent->_bf == -2的子情况：parent->_bf == -2 && cur->_bf == -1

插入在左子树的左边 ，情况完全和左单旋相反（略）
代码如下：

void RotateL(Node* parent)
	{
		Node* sub = parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* sub_parent = sub->_parent;
		sub->_right = subRL;
		if (subRL)//将subRL给给sub的有，如果subRL为nullptr，subRL->_parent = sub空指针指向报错
			subRL->_parent = sub;
		subR->_left = sub;
		sub->_parent = subR;
		if (sub_parent == nullptr)//也相当于_root==parent(root==sub)
		{
			subR->_parent = nullptr;
			_root = subR;
		}
		else//sub上面还有节点
		{
			subR->_parent = sub_parent;
			if (sub_parent->_left == sub)
				sub_parent->_left = subR;
			else
				sub_parent->_right = subR;
		}
		sub->_bf = subR->_bf = 0;//更新平衡因子
	}

左右双旋

即隶属于parent->_bf == 2 || parent->_bf == -2的子情况：parent->_bf == -2 && cur->_bf == 1

下面有一个AVL树
分三种情况：

1. B后插入一个节点
   
   
2. 或者在C后插入一个节点
   
   
3. 插入的这个节点刚好构成双旋(也就是上面单旋提到的左子树的右边插入情况)
   

注意：

1. 三种情况结束后5，6，7三个节点的平衡因子都不一样，需要根据更改前subRL的平衡因子来分类更改旋转后的各平衡因子
2. 在调用单旋函数之前一定要记录一下subRL的平衡因子，因为双旋调用两个单旋很有可能会改变subRL的平衡因子

代码如下：

void RotateLR(Node* parent)
{
	Node* sub = parent;
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;//必须要在这里先记录一下subLR的平衡因子，因为双旋调用两个单旋很有可能会改变subLR的平衡因子
	RotateL(subL);
	RotateR(sub);
	if (bf == 1)
	{
		subL->_bf = -1;
		subLR->_bf = 0;
		sub->_bf = 0;
	}
	else if (bf == -1)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		sub->_bf = 1;
	}
	else if (bf == 0)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		sub->_bf = 0;
	}
	else
		assert(false);
}

右左双旋

即隶属于parent->_bf == 2 || parent->_bf == -2的子情况：parent->_bf == 2 && cur->_bf == -1

下面有一个AVL树
分三种情况：

1. b处插入一个节点
2. 或者在c处插入一个节点
3. 插入的这个节点刚好构成双旋(也就是上面单旋提到的右子树的左边插入情况)

略，代码如下：

void RotateRL(Node* parent)
{
	Node* sub = parent;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;//必须要在这里先记录一下subRL的平衡因子，因为双旋调用两个单旋很有可能会改变subRL的平衡因子
	RotateR(subR);
	RotateL(sub);
	if (bf == 1)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		sub->_bf = -1;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		subRL->_bf = 0;
		sub->_bf = 0;
	}
	else if (bf == 0)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		sub->_bf = 0;
	}
	else
		assert(false);
}

3）AVL树的删除（mark一下，以后看）

删除在搜索树里是难点，AVL的删除大致和搜索树相同，但同时加上了旋转，两个难点加在一起
大致思路：

1. 按二叉搜索树的思路进行删除。
2. 更新平衡因子
3. 如果出现不平衡树，进行旋转

（这里注意当平衡因子为0的时候不能停止）