一.什么是AVL树

AVL树，也叫二叉平衡搜索树，就是在BST树的基础上加了平衡操作（平衡的定义是任意节点的左右子树的高度差不超过1）。

AVL树常用于查询操作多，写操作少的情况下，如果同样需要写操作，那么最好使用红黑树。

其基本框架与BST树相同，不过为了保证其平衡，添加了节点的旋转操作：

template<typename T>
class AVLTree
{
public:
	AVLTree()
		:root(nullptr)
	{ }
	~AVLTree(){}

private:
	struct Node
	{
		Node(T data=T())
			:m_data(data)
			,left(nullptr)
			,right(nullptr)
			,height(1)
		{ }
		


		T m_data;
		Node* left;
		Node* right;
		int height;//节点高度，用于旋转操作
	};
	Node* root;
};
//获取节点高度
int getHeight(Node* node)
{
	return node == nullptr ? 0 : node->height;
}

二.常见操作实现

1.平衡操作

（1）.右旋转操作

如果添加一个元素后，左孩子的左子树太高了，那么需要进行右旋转，如图：。

这里的节点node与节点child的孩子节点都发生了变化，它们的高度需要进行更新。

//右旋转操作
Node* rightRotate(Node* node)
{
	Node* child = node->left;
	node->left = child->right;
	child->right = node;

	node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
	child->height = max(getHeight(child->left), getHeight(child->right)) + 1;
	return child;

}

（2）.左旋转操作

如果添加一个元素后，右孩子的右子树太高了，那么需要进行左旋转，如图：

这里的节点node与节点child的孩子节点都发生了变化，它们的高度需要进行更新。

//左旋转操作
Node* leftRotate(Node* node)
{
	Node* child = node->right;
	node->right = child->left;
	child->left = node;

	node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
	child->height = max(getHeight(child->left), getHeight(child->right)) + 1;
	return child;

}

（3）左平衡操作

如果添加一个元素后，左孩子的右子树太高了，那么需要进行左平衡，如图：

//左平衡操作(左-右)
Node* leftBalance(Node* node)
{
	node->left= leftRotate(node->left);
	return rightRotate(node);


}

（4）右平衡操作

如果添加一个元素后，右孩子的左子树太高了，那么需要进行右平衡，如图：

//右平衡操作(右-左)
Node* rightBalance(Node* node)
{
	node->right= rightRotate(node->right);

	 return leftRotate(node);


}

2.插入操作

最多旋转2次，时间复杂度：logn

Node* insert(const T& val,Node* node)
{
	if (node == nullptr)
	{
		return new Node(val);

	}
	if (node->m_data == val)
	{
		return node;
	}
	else if (node->m_data > val)
	{
		node->left = insert(val, node->left);
		if ((getHeight(node->left) - getHeight(node->right))>1)
		{
			if (getHeight(node->left->left) >= getHeight(node->left->right))
			{
				node = rightRotate(node);
			}
			else 
			{
				node = rightBalance(node);
			}
		}
		

	}
	else
	{
		node->right = insert(val, node->right);
		if ((getHeight(node->right) - getHeight(node->left)) > 1)
		{
			if (getHeight(node->right->right) >= getHeight(node->right->left))
			{
				node = leftRotate(node);
			}
			else
			{
				node = leftBalance(node);
			}
		}
	}
	node->height = max(getHeight(node->left), getHeight(node->right)) + 1;


	return node;
}

3.删除操作

最多旋转logn次，时间复杂度：logn

Node* remove(const T& val, Node* node)
{
	if (node == nullptr)
	{
		return nullptr;
	}
	if (node->m_data > val)
	{
		node->left = remove(val, node->left);
		if ((getHeight(node->right) - getHeight(node->left)) > 1)
		{
			if (getHeight(node->right->right) >= getHeight(node->right->left))
			{
				node = leftRotate(node);
			}
			else
			{
				node = leftBalance(node);
			}
		}
		
	}
	else if(node->m_data < val)
	{
		node->right = remove(val, node->right);
		if ((getHeight(node->left) - getHeight(node->right)) > 1)
		{
			if (getHeight(node->left->left) >= getHeight(node->left->right))
			{
				node = rightRotate(node);
			}
			else
			{
				node = rightBalance(node);
			}
		}
	}
	else
	{
		if (node->left != nullptr && node->right != nullptr)
		{
			if (getHeight(node->left) >= getHeight(node->right))
			{
				Node* pre = node->left;
				while (pre->right != nullptr)
				{
					pre = pre->right;
				}
				node->m_data = pre->m_data;
				
				node->left = remove( pre->m_data, node->left);
			}
			else
			{
				Node* last = node->right;
				while (last->left != nullptr)
				{
					last = last->left;
				}
				node->m_data = last->m_data;
				node->right = remove( last->m_data, node->right);

			}
		}
		else
		{
			if (node->left != nullptr)
			{
				Node* left = node->left;
				delete node;
				return left;
			}
			else if (node->right != nullptr)
			{
				Node* right = node->right;
				delete node;
				return right;
			}
			else
			{
				delete node;
				return nullptr;
			}
		}
	}
	node->height = max(getHeight(node->left), getHeight(node->right)) + 1;

	return node;

}