前言

AVL树特点：在BST树的基础上，引入了节点“平衡”的概念，任意一个节点的左右子树高度差不超过1。

为什么要引入平衡这个概念？
在BST树中，由于插入后就是排序好的，那就会存在这样一种情况：如果插入的元素依次增大，就会导致理想中的二叉树，形成了一个链表，如下图，这种情况会导致增删查的时间复杂度并不是O(logn)，而是O(n)。为了解决这样情况，引入了平衡的概念。

AVL树节点的定义

template<typename T>
class AVLTree
{
private:
	// 定义AVL树节点类型
	struct Node
	{
		Node(T data = T())
			: val_(data)
			, left_(nullptr)
			, right(nullptr)
			, height_(1)
		{}

		T val_;
		Node* left_;
		Node* right_;
		int height_;	// 记录节点高度值
	};

	Node* root_;	// 指向根节点
};

AVL树维护节点平衡的四种旋转操作

1. 右旋转-左孩子的左子树太高

操作步骤：right rotate

1. child指针指向node节点的左孩子；
2. child如果有右子树，那就让node的左子树指向child的右子树；
3. child的右子树指向node；
4. 更新node和child节点的高度值。

代码：

// 返回节点的高度值
int height(Node* node)
{
	return node == nullptr ? 0 : node->height_;
}

// 右旋转操作,以参数node为轴做右旋转操作，并把新的根节点返回
Node* rightRotate(Node* node)
{
	Node* child = node->left_;
	node->left_ = child->right_;
	child->right_ = node;
	// 高度更新
	node->height_ = std::max(height(node->left_), height(node->right_)) + 1;
	child->height_ = std::max(height(child->left_), height(child->right_)) + 1;
	// 返回旋转后的子树新的根节点
	return child;
}

2. 左旋转-右孩子的右子树太高

操作步骤：left rotate

1. child指针指向node的右孩子；
2. 让node的右子树指向child的左子树；
3. child的左子树指向node；
4. 更新node和child节点的高度值。

代码：

// 左旋转操作
Node* leftRotate(Node* node)
{
	Node* child = node->right_;
	node->right_ = child->left_;
	child->left_ = node;
	// 高度更新
	node->height_ = std::max(height(node->left_), height(node->right_)) + 1;
	child->height_ = std::max(height(child->left_), height(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);
}

AVL树的增加-insert()

先来看看BST树的递归插入操作

如果node为nullptr，表示找到插入的位置了；
如果当前节点的值等于data，直接返回；
如果当前节点的值小于data，则递归往左子树走；
如果当前节点的值大于data，则递归往右子树走。

// 递归插入操作
Node* insert(Node* node, const T& data)
{
	if (node == nullptr)
	{
		// 递归结束，找到插入data的位置，生成新节点返回
		return new Node(data);
	}
	if (node->val_ == data)
	{
		return node;
	}
	else if (node->val_ < data))
	{
		node->right_ = insert(node->right_, data);
	}
	else
	{
		node->left_ = insert(node->left_, data);
	}
	return node;
}

AVL树的插入操作：相对于BST树增加了哪些内容？
如果node为nullptr，表示找到插入的位置了，递归结束，申请新节点返回；

1. 如果当前节点值大于data，则递归往左子树插入；在回溯时判断节点是否失衡，因为是在左子树插入，所以判断左子树失衡问题。若失衡，则有两种情况，一是左孩子的左子树太高，则对node进行右旋转；二是左孩子的右子树太高，则对node做左平衡（左-右旋转）。
2. 如果当前节点值小于data，则递归往右子树插入；在回溯时判断节点是否失衡，因为是在右子树插入，所有判断右子树失衡问题。若失衡，则又有两种情况，一是右孩子的右子树太高，则对node进行左旋转；二是右孩子的左子树太高，则对node做右平衡（右-左旋转）。
3. 如果当前节点值等于data，表示遇到相同的值，什么也不做；
4. 退出这三个判断后，在回溯过程中修正节点的高度，将其修正为左子树和右子树当中最高的高度再加1。
5. 最后返回当前节点。

// 插入操作实现
Node* insert(Node* node, const T& data)
{
	if (node == nullptr) // 递归结束
	{
		return new Node(data);
	}

	if (node->val_ > data)
	{
		node->left_ = insert(node->left_, data);
		// 添加1 在递归回溯时判断节点是否失衡
		// node的左子树太高，左子树失衡
		if (height(node->left_) - height(node->right_) > 1)
		{
			// 两种情况：左孩子左子树太高,节点失衡
			if (height(node->left_->left_) >= height(node->left_->right_))
			{
				node = rightRotate(node);
			}
			else // 左孩子的右子树太高，做左平衡
			{
				node = leftRotate(node);
			}
		}
	}
	else if (node->val_ < data)
	{
		node->right_ = insert(node->right_, data);
		// 添加2 在递归回溯时判断节点是否失衡
		// node的右子树太高，右子树失衡
		if (height(node->right_) - height(node->left_) > 1)
		{
			// 两种情况：右孩子右子树太高,节点失衡
			if (height(node->right_->right_) >= height(node->right_->left_))
			{
				node = leftRotate(node);
			}
			else // 右孩子的左子树太高，做右平衡
			{
				node = rightRotate(node);
			}
		}
	}
	else
	{
		; // 找到相同节点了，直接返回
	}

	// 添加3 添加节点后，回溯过程中检测更新节点高度
	node->height_ = max(height(node->left_), height(node->right_)) + 1;

	return node;
}

AVL树的删除（待补充）