AVL树

概念

• AVL树是一棵平衡二叉查找树，AVL树是空树，保证左右子树都是AVL树，AVL树要求高度差的绝对值不超过1，因为最好情况是1，比如4个节点高度差最好是1,2个也是1,3个节点最好是0
• 任何子树-左右子树高度差的绝对值都是1
• 这样AVL树就接近完全二叉树了，高度为logN，增删查改的效率就为logN
• 任何节点的平衡因子：右子树-左子树的高度，0/-1/1，有了平衡因子就更容易控制AVL树是否平衡，但AVL树并不是必须要平衡因子

AVL树的插入

1. 按二叉搜索树的规则进行插入
2. 新增节点后会影响祖先节点的高度，也就是祖先节点的平衡因子，所以更新从新增节点到根节点路径上的平衡因子，实际最坏情况要跟新到根，也可能根新到中间就停止了
3. 更新平衡因子中没有出现问题，插入结束
4. 不平衡子树要进行旋转，旋转的本质是调平衡，进而降低子树的高度，不会再影响上一层，则插入结束

平衡因子的更新

更新规则：

• 平衡因子 = 右子树的高度 - 左子树的高度
• 只有子树的高度变化才会影响当前节点的平衡因子
• 插入新节点，插入在左子树，parent节点平衡因子减减，插入在右子树，parent节点平衡因子加加
• parent所在子树的高度的变化决定了是否继续向上更新
• 高的那边才会影响平衡因子

更新的停止条件：

1. 更新后平衡因子是1或者-1，那么更新前更新中平衡因子是0->-1,0->1,说明更新前parent子树两边一样高，更新后一边高一边低，符合平衡的要求，但是高度增加了1，高度的增加会影响parent节点的平衡因子，所以要继续向上更新
2. 更新后parent平衡因子是0，更新中parent的平衡因子变化为-1->0,1->0,更新前parent的子树一边高一边低，更新后parent子树一样高，不会影响parent的平衡因子，所以停止更新。
3. 更新后parent平衡因子是2或-2，-1->-2,1->2,更新前parent的子树一边高一边低，更新后，增加节点到了高的那边，高的那边更高了，所以高的那边破坏了平衡，需要旋转处理
4. 旋转的目标：把parent的子树旋转平衡；降低parent子树的高度，恢复到插入之前的高度。插入之前是平衡的。
5. 结束的3个情况：旋转后，插入结束；平衡因子是0；平衡因子是-1/1，但是更新到根节点都是-1/1也就结束了
   

旋转的规则

1. 保证旋转前和旋转后都是搜索树
2. 让旋转的树从不满足平衡到满足平衡，其次还会降低旋转树的高度来满足平衡因子
   旋转分为四种：左单旋/右单旋/左右双旋/右左双旋

左单旋

左单旋：右边的树比左边的树高
左单旋和右单旋类似就不多做说明了

右单旋

右单旋：左边的树比右边的树高
a,b,c的高度都是h
h >= 0,a,b,c都是搜索二叉树，只是把它抽象出来了

抽象的情况

1. 往右旋，5变为根，10变为5的右节点，b变为10的左节点
   

h==0

h==1

h== 2

h == 3

#pragma once
#include<iostream>

using namespace std;

// 节点的结构
// 加了一个parent,为了找到父节点的父节点，从而往上走
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;
	// 平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_bf(0)// 刚插入的节点平衡因子都是0
	{}
};

// 树的结构
template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	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 (parent->_left == cur)
				parent->_bf--;
			else if (parent->_right == cur)
				parent->_bf++;

			if (parent->_bf == 0)
			{
				break;
			}
			eles if (parent->_bf == -1 || parent->_bf == 1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 旋转

				break;
			}
			else
			{
				// 逻辑错误,之前就不是AVL树
				assert(false);
			}
		}
		return true;
	}
private:
	Node* _root = nullptr;
};