AVL树节点失衡以及增加删除操作

AVL树节点失衡的原因： 

1. 左孩子的左子树太高了  （右旋操作）
2. 右孩子的左子树太高了  （左旋操作）
3. 左孩子的右子树太高了  （左平衡操作）
4. 右孩子的左子树太高了  （右平衡操作）

代码实现如下：

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;template<typename T>
class AVLTree
{
public:AVLTree() :root_(nullptr) {}
private://定义AVL树节点类型struct Node{Node(T data = T()):data_(data), left_(nullptr), right_(nullptr), height_(1){}T data_;Node *left_;Node *right_;int height_; //记录节点的高度值};//返回节点的高度值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_ = max(height(node->left_), height(node->right_)) + 1;child->height_ = max(height(child->left_), height(child->right_)) + 1;//返回旋转后的子树新的根节点return child;}//左旋转操作 以参数node为轴做左旋转操作，并把新的根节点返回Node* leftRotate(Node *node){//节点旋转Node *child = node->right_;node->right_ = child->left_;child->left_ = node;//高度更新node->height_ = max(height(node->left_), height(node->right_)) + 1;child->height_ = max(height(child->left_), height(child->right_)) + 1;return child;//返回旋转后的子树新的根节点}//左平衡操作  以参数node为轴做左-右旋转操作，并把新的节点返回Node* leftBalance(Node *node){node->left_ = leftRotate(node->left_); //参考笔记中左旋后返回的节点置为node的左孩子return rightRotate(node);}//右平衡操作  以参数node为轴做右-左旋转操作，并把新的节点返回Node* rightBalance(Node *node){node->right_ = rightRotate(node->right_); //参考笔记中右旋后返回的节点置为node的右孩子return leftRotate(node);}
}

 AVL树插入操作：

• 先找到要插入的位置，若插入的数字比根节点小在左子树进行查找，若大于根节点则在右子树进行查找
• 找到位置后插入节点进行递归回溯，判断节点是否失衡，如若失衡根据失衡原因进行相应的操作

 具体代码实现如下：

//AVL树的插入操作实现Node* insert(Node *node,const T &val){if (node == nullptr)//递归结束，找到插入的位置{return new Node(val);}if (node->data_ > val){node->left_ = insert(node->left_, val);//在递归回溯时判断节点是否失衡  node的左子树太高 node失衡if (height(node->left_) - height(node->right_) > 1){if (height(node->left_->left_) >= height(node->left_->right_)){//节点失衡，由于左孩子的左子树太高node = rightRotate(node);}else{//节点失衡，由于左孩子的右子树太高node = leftBalance(node);}}}else if (node->data_ < val){node->right_ = insert(node->right_, val);//在递归回溯时判断节点是否失衡  node的右子树太高 node失衡if (height(node->right_) - height(node->left_) > 1){if (height(node->right_->right_) >= height(node->right_->left_)){//节点失衡，由于右孩子的右子树太高node = leftRotate(node);}else{//节点失衡，由于右孩子的左子树太高node = rightBalance(node);}}}else{;//找到相同节点，不用往下递归了，直接向上回溯}//因为子树中增加了新的节点  在递归回溯时检测更新节点高度node->height_ = max(height(node->left_), height(node->right_)) + 1;return node;}

AVL树删除操作：

• 先找到要删除的位置，若删除的数字比根节点小在左子树进行查找，若大于根节点则在右子树进行查找。

1.  左子树删除节点可能造成右子树太高，有两种情况，分别是右孩子右子树太高和右孩子左子树太高，不同情况进行不同的失衡操作
2. 右子树删除节点可能造成左子树太高，有两种情况，分别是左孩子左子树太高和左孩子右子树太高，不同情况进行不同的失衡操作

• 需要删除的点也会出现三种不同情况

1. 被删除的点有两个孩子：为了避免删除前驱或者后继结点造成节点失衡，谁高删谁 （即删除后不用在判断失衡问题）
2. 被删除的点只有一个孩子：判断是左孩子还是右孩子，记录上它的孩子然后删除掉要删除的节点将记录的孩子返回
3. 被删除的点没有孩子：直接返回空

具体代码实现如下：

	//删除操作实现Node* remove(Node *node, const T &val){if (node == nullptr){return nullptr;}if (node->data_ > val){node->left_ = remove(node->left_, val);//左子树删除节点可能造成右子树太高if (height(node->right_) - height(node->left_) > 1){if (height(node->right_->right_) >= height(node->right_->left_)){//右孩子右子树太高node = leftRotate(node);}else{//右孩子左子树太高node = rightBalance(node);}}}else if (node->data_ < val){node->right_ = remove(node->right_, val);//右子树删除节点可能造成左子树太高if (height(node->left_) - height(node->right_) > 1){if (height(node->left_->left_) >= height(node->left_->right_)){//左孩子左子树太高node = rightRotate(node);}else{//左孩子右子树太高node = leftBalance(node);}}}else{//找到删除节点 先处理有两个孩子的删除情况if (node->left_ != nullptr && node->right_ != nullptr){//为了避免删除前驱或者后继结点造成节点失衡，谁高删谁 （即删除后不用在判断失衡问题）if (height(node->left_) > height(node->right_)){//删前驱Node *pre = node->left_;while (pre->right_ != nullptr){pre = pre->right_;}node->data_ = pre->data_;node->left_ = remove(node->left_, pre->data_);//删前驱节点}else{//删后继Node *post = node->right_;while (post->left_ != nullptr){post = post->left_;}node->data_ = post->data_;node->right_ = remove(node->right_, post->data_);//删后继节点}}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{return nullptr;}}}//更新节点高度node->height_ = max(height(node->left_), height(node->right_)) + 1;return node; //递归回说过程中，把当前节点给父节点返回}