AVL树介绍

一、介绍

高度平衡的搜索二叉树，保证每个节点的左右子树高度差不超过1，降低搜索树的高度以提高搜索效率。

通过平衡因子和旋转来保证左右子树高度差不超过1

二、插入节点

1、插入规则

（1）搜按索树规则插入节点

（2）更新父节点平衡因子

插入左边就 --，插入右边就 ++

（3）保证父节点平衡因子不超过1

平衡因子是0：表示插入节点之后以父节点为子树的树高度没变，所以插入合法直接跳出。

平衡因子是正负1：以父节点为子树的树高度增大或者减小了1，虽然当前的父节点依旧合法，但是由于高度变了还要向上更新平衡因子。

平衡因子是正负2：要旋转使以父节点为子树的树平衡因子合法。合法后直接挑出。

2、旋转逻辑实现

（1）左高右低右单旋

旋转前：

旋转后：

大逻辑：把 subLR 给 parent，把 parent 给 subL

右单旋代码实现逻辑和注意点：

a、标记三个节点：subL，subLR，ppNode（保存 parent 的父亲，为了最后更新 subL 的父节点）

b、先 subLR 作 parent 的左子树，注意更新subLR 父节点时 subLR == nullptr 情况

c、再 parent 作 subL 的右子树，注意更新 parent 的父节点

d、利用 ppNode 更新subL 的位置和父节点，注意一开始父节点是根的情况

e、更新 subL 和 parent 的平衡因子为0

右单旋代码：

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* ppNode = parent->_parent;

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

	subL->_right = parent;
	parent->_parent = subL;

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

（2）右高左低左单旋

旋转前：

旋转后：

分析过程和右单旋类似，代码如下：

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* ppNode = parent->_parent;

	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

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

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

（3）左高右高左右双旋

旋转图：

左右双旋的本质就是把 subLR 的左子树给 subL，右子树给 parent

通过本质就可以知道三种不同情况的平衡因子：

插入前 subLR 平衡因子	插入后平衡因子
插入前 subLR 平衡因子	subLR	subL	parent
-1（新节点插在 subLR 的左子树）	0	0	1
1（新节点插在 subLR 的右子树）	0	-1	0
0（新节点就是 subLR）	0	0	0

左右双旋代码：

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(subL);
	RotateR(parent);

	if (bf == -1)
	{
		subL->_bf = 0;
		parent->_bf = 1;
		subLR->_bf = 0;
	}
	else if (bf == 1)
	{
		subL->_bf = -1;
		parent->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 0)
	{
		subL->_bf = 0;
		parent->_bf = 0;
		subLR->_bf = 0;
	}
	else
		assert(false);
}

（4）右高左高右左双旋

旋转图：

右左双旋的本质就是把 subRL 的左子树给 parent，右子树给 subR

通过本质就可以知道三种不同情况的平衡因子：

插入前 subRL 平衡因子	插入后平衡因子
插入前 subRL 平衡因子	subRL	subR	parent
-1（新节点插在 subRL 的左子树）	0	1	0
1（新节点插在 subRL 的右子树）	0	0	-1
0（新节点就是 subRL）	0	0	0

右左双旋代码：

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	RotateR(subR);
	RotateL(parent);

	if (bf == 1)
	{
		subR->_bf = 0;
		parent->_bf = -1;
		subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		parent->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == 0)
	{
		subR->_bf = 0;
		parent->_bf = 0;
		subRL->_bf = 0;
	}
	else
		assert(false);
}

3、插入代码展示

bool insert(const pair<K, V> kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}

	Node* cur = _root;
	Node* parent = cur;
	// 1.像搜索二叉树一样插入节点cur
	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;
	}

	cur = new Node(kv);
	if (parent->_kv.first < kv.first)
		parent->_right = cur;
	else
		parent->_left = cur;
	cur->_parent = parent;

	// 2.更新平衡因子
	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
				RotateRL(parent); 
			break;
		}
		else
			assert(false);
	}
	return true;
}

三、验证AVL树

检查每个节点的左右子树高度差是否不超过1和平衡因子是否是左右子树的高度差

bool _IsBalance(Node* root)
{
	if (root == nullptr)
		return true;

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	// 不平衡
	if (abs(leftHeight - rightHeight) >= 2)
	{
		cout << root->_kv.first << endl;
		return false;
	}

	// 顺便检查一下平衡因子是否正确
	if (rightHeight - leftHeight != root->_bf)
	{
		cout << root->_kv.first << endl;
		return false;
	}

	return _IsBalance(root->_left)
		&& _IsBalance(root->_right);
}