详解二叉搜索树（AVL树）

template<class T>
struct TreeNode
{
	TreeNode(const T& data)
		:_data(data)
		,_left(nullptr)
		,_right(nullptr)
	{}

	TreeNode* _left;
	TreeNode* _right;
	T _data;
};

template<class T>
class Tree
{
	using Node = TreeNode<T>;

private:
	Node* _root = nullptr;
};

2.节点的插入与删除

插入节点就定义一个cur节点从根开始遍历，cur节点存储的值的大小与要插入值比较，大的往左走小的往右走（反过来也行，看个人需求），当然要定义一个parent节点存储它的父节点来进行链接操作；删除节点就找一个存储数据大小相近的节点来进行替换后进行链接就行了，当然里面有很多细节（空节点的判定等）要注意特殊处理，这些二叉搜索树基础操作不过多详解，在此简单点一下，代码奉上：

bool Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_data > data)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_data < data)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
        {
			return false;
        }
	}

	cur = new Node(data);
	if (parent->_data > data)
    {
		parent->_left = cur;
    }
	else
    {
		parent->_right = cur;
    }

	return true;
}

bool Erase(const T& data)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_data > data)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_data < data)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			if (cur->_left == nullptr)
			{
				if (parent == nullptr)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_left == cur)
                    {
						parent->_left = cur->_right;
                    }
					else
                    {
						parent->_right = cur->_right;
                    }
				}
				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				if (parent == nullptr)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}
				delete cur;
				return true;
			}
			else // 两边节点都不为空，找可代替节点(左子树的最左节点或右子树的最最右节点)
			{
				Node* right_min_parent = cur;
				Node* right_min = cur->_right;
				while (right_min->_left)
				{
					right_min_parent = right_min;
					right_min = right_min->_left;
				}
				cur->_data = right_min->_data;

				if (right_min_parent->_left == right_min) // 节点数据替换后别忘了链接被代替节点的兄弟节点！！！
                {
					right_min_parent->_left = right_min->_right;
                }
				else
                {
					right_min_parent->_right = right_min->_right;
                }
				delete right_min;
				return true;
			}
			return true;
		}
	}
	return false;
}

2.平衡搜索二叉树

平衡二叉搜索树是一种特殊的二叉搜索树，它除了满足二叉搜索树的基本特点之外，本身还存在特定规则，这些规则可以保证二叉树的搜索性能保持在O(log n)量级，不会出现极端的单支树等类似树状结构将搜索性能降低。

比较常见的平衡二叉搜索树有AVL树、红黑树等

我们这篇博客就来深度解析一下AVL树的运行逻辑

3.AVL树

AVL树除了满足二叉搜索树的基本特点之外，它还有它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1的规律。

为了满足这个规则，我们在每个节点处增加一个平衡因子，这个平衡因子用于储存它左右子树的高度差（_bf = 右子树的高度 - 左子树的高度），即我们只需要让每个节点的平衡因子的值维持在1/-1/0之中即可，为了方便链接我们再加一个parent节点储存父节点。

1.AVL树的节点插入

当我们新增了平衡因子后，在每次插入节点后都需要进行检查、维护，所以AVL树插入过程就很明了了：

1.按二叉搜索树的规则插入节点

2.更新平衡因子

那么现在就来分析一下平衡因子的更新规律

1.平衡因子的更新

我们这里就定义右子树的高度 - 左子树的高度为平衡因子的值，那么我们只需要判断插入节点是父节点的左子树还是右子树来对parent节点的平衡因子进行-- 或 ++，接着再对parent节点更新后的平衡因子的值来进行分析来判断是否继续向上更新

1.更新后节点的平衡因子变为0：

我们要更新平衡因子，就要先知道平衡因子更新到什么时候就可以停下来了——当我们更新到的节点的平衡因子变为0时就能停了

节点的平衡因子变为0，那么之前的值为-1或1，在插入节点之前的以这个节点为根的这棵树，它子树一边高一边低，那么在插入结点之后，这棵树变平衡了，它的高度是不变的，因此他的父节点的平衡因子也是不用变的

2.更新后节点的平衡因子变为-1/1和-2/2：

为什么没有其他情况，就只有这两种情况？

如果有其他情况的话，比如3/-3,那么就说明在更新前他的平衡因子为-2/2或-4/4，那么在更新前就已经不是AVL树了，那这棵树就出问题了，其余情况同理

a.更新后节点的平衡因子变为-1/1：

根据上面的推理，我们不难知道更新前平衡因子必定为0，那么以这个节点为根的树就由平衡变得不平衡，它的高度就增加了，那么就要继续往上更新

b.更新后节点的平衡因子为-2/2：

这时树就变得不是AVL树了，那么这时候就要进行旋转，让它重新变为AVL树

2.旋转

我们把旋转分为4种情况：左单旋/右单旋/左右双旋/右左双旋

1.右单旋

以上图为例：当在a里插入了一个节点后，parent节点的平衡因子变为了-2，cur节点为-1，也就是该树变为了纯粹的左边高。这时候就要让parent节点以cur节点为轴心向右旋转

旋转的核心步骤就是让parent变为cur的右子树，而cur原来的右子树变为parent的左子树parent，再对祖先节点与cur节点进行链接即可，在最后将parent和cur的平衡因子置为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)
	{
		if (pParent->_left == parent)
			pParent->_left = subL;
		else
			pParent->_right = subL;
		subL->_parent = pParent;
	}
	else
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	parent->_bf = subL->_bf = 0;
}

2.左右双旋

如果该树不是纯粹的左边高（或右边高），那么进行右单旋还会平衡吗？

可以看到旋转后仍不平衡，那么我们可以想办法让这棵树变为纯粹的单边高，再来进行旋转，那么该怎么做呢？

那么这时候我们可以先让cur节点左旋一次，让这棵树变为纯粹的左边高，再让parent右旋一次，实现平衡，那么其他情形呢？

如图，这个适用于所有的类型，但是有些眼睛好的亦菲彦祖们就发现了：再上上张图中进行左右双旋的话，它的parent，subL及subLR节点的平衡因子在旋转后都变为了0；而在上图中subL的平衡因子居然变成了-1！！

那么这就是双旋后对平衡因子的更改的重点：

1.当新增节点再subLR的左子树时（subLR->_bf == 1），e树高度就为h，f树就为h-1，旋转链接后不难发现，subL变平衡树了，而parent变得不平衡了

2.当新增节点再subLR的左子树时（subLR->_bf == -1），如上图

3.而新增节点就为subLR时（subLR->_bf == 0），它在旋转后该树变为了满二叉树

对此可以以subLR的平衡因子的值为根据来进行判断，右左双旋同理

左右双旋代码奉上：

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

	RotateL(parent->_left);
	RotateR(parent);

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

2.AVL树平衡检测

当我们理解了上述要点就能自己尝试实现AVL树了，那我们该如何验证自己写的是正确的呢？

要验证我们实现的树是正确的无非是检查他是否遵循AVL树的规则：

1.左右子树高度差不超过1

2.每个节点的平衡因子的值是准确的

也就是我们只要验证上述两点即可！

我们可以写一个获取二叉树高度的代码，让它左右子树的高度相减，判断结果是否大于1，再递归去遍历每个节点，同时判断平衡因子的正确性（H左 - H右 < 2）

代码奉上：

int _Height(Node* root)
{
	if (root == nullptr)
    {
		return 0;
    }
	
	return max(1 + _Height(root->_left), 1 + _Height(root->_right));
}

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

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;
	if (abs(diff) >= 2)
	{
		cout << root->_data << "高度差异常" << endl;
		return false;
	}
	if (root->_bf != diff)
	{
		cout << root->_data << "平衡因子异常" << endl;
		return false;
	}
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}