性质

在BST树的基础上引入了平衡因子的概念，要求任意一个节点的左右子树高度差不超过1

需要旋转的四种情况

• 左孩子左子树太高：右旋
• 右孩子右子树太高：左旋
• 左孩子右子树太高：先对左孩子左旋，再对当前节点右旋（左平衡）
• 右孩子左子树太高：先对右孩子右旋，再对当前节点左旋（右平衡）

#include 
#include 
#include using namespace std;// 定义节点类型
template
struct Node {Node(T data = T()) : data_(data), left_(nullptr), right_(nullptr), height_(1) {}T data_;Node* left_;Node* right_;int height_; // 记录节点的高度
};// AVL树
template
class AVLTree {
public:AVLTree() : root_(nullptr) {}// 插入void insert(const T& val) {root_ = insert(root_,val);}// 删除void remove(const T& val) {root_ = remove(root_,val);}
private:Node* root_; // 根节点// 返回节点的高度int height(Node *node) {return node == nullptr ? 0 : node->height_;}// 右旋Node* rightRotate(Node* node);// 左旋Node* leftRotate(Node* node);// 左平衡Node* leftBalance(Node* node);// 右平衡Node* rightBalance(Node* node);// 插入Node* insert(Node* node, const T& val);// 删除Node* remove(Node* node, const T& val);
};// 右旋
template
Node* AVLTree::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;
}// 左旋
template
Node* AVLTree::leftRotate(Node* node) {// 节点旋转Node *child = node->left_;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右旋
template
Node* AVLTree::leftBalance(Node *node) {node->left_ = leftRotate(node->left_);return rightRotate(node);
}// 右平衡 先对node的右子树右旋，再对node左旋
template
Node* AVLTree::rightBalance(Node *node) {node->right_ = rightRotate(node->right_);return leftRotate(node);
}// 插入
template
Node* AVLTree::insert(Node *node, const T &val) {// 递归结束 找到插入的位置if (node == nullptr) return new Node(val);if (node->data_ > val) {node->left_ = insert(node->left_,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->data_ < val) {node->right_ = insert(node->right_,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 {// 找到相同节点 不需要向下递归 直接向上回溯}// 因为子树添加了新的节点 所以在递归的时候需要更新节点高度node->height_ = max(height(node->left_), height(node->right_)) + 1;return node;
}// 删除操作 从叶子节点中选出一个节点 进行替换
template
Node* AVLTree::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* pre = node->right_;while (pre->left_ != nullptr) {pre = pre->left_;}node->data_ = pre->data_;node->right_ = remove(node->right_,pre->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 {delete node;return nullptr;}}}// 更新节点高度node->height_ = max(height(node->left_), height(node->right_)) + 1;return node;
}

性能分析

• AVL树插入一个节点最多只需要两次旋转就可以恢复平衡

插入一个节点会导致节点所在的子树高度加1，但是旋转会让新节点所在子树减1，所以AVL树插入一个节点最多只需要两次旋转就可以了

• AVL树删除一个节点最多需要O(logN)次旋转才可以恢复平衡

删除一个节点会导致节点所在子树减1，旋转又会让节点所在的子树减1，所以最坏的时候需要O(logN)次旋转

删除节点 X 之后，R4的平衡因子变为 -2，R4 左旋；R3 的平衡因子变为 2，R3 右旋；R2 的平衡因子变为 -2， R2左旋；R1的平衡因子变为2，R1 右旋

当从根节点至待删除节点的父节点平衡因子交替为 -1 和 +1，删除该节点一旦触发旋转就需要logn次旋转