阅读本文前，请确保您已经了解了二叉搜索树的相关内容（如定义、增删查改的方法以及效率等）。否则，建议您先学习二叉搜索树。本文假定您对二叉搜索树有了足够的了解。
效率？
众所周知，在平衡条件下，对二叉搜索树中的元素进行增删查改，时间效率为(O(log(n)))。
然而，理想很丰满，现实很骨感，实际上，二叉搜索树并不总是能够保持平衡状态。
最极端的情况就是，除了叶节点之外，每个节点只有一个子节点，如图所示：
这种情况下二叉搜索树已经退化成一个链表，时间复杂度达到了(O(n))，二叉搜索树在时间效率上的优势并没有发挥出来。
要想解决这个问题，我们就要在每次动态操作（插入、删除）之后，采取某种措施，使二叉搜索树重新回到平衡状态（重平衡）。
平衡？
最理想的状态就是完全二叉树，其时间复杂度为(O(log(n)))，但是如果每次动态操作之后都要让二叉搜索树处于这样一种理想状态的话，实现起来比较复杂，大量的时间消耗在重平衡上，最后反而得不偿失。
鱼和熊掌不可兼得，我们需要在“平衡状态”和“花在重平衡上的时间成本”之间做出一个取舍，将平衡条件适当放宽。
一种可能的折中方案
这次，我们不再要求二叉搜索树必须是完全二叉树，而是放宽到每一个节点的左右子树高度差不超过1（规定空树的高度为0）。这就是所谓的AVL树。
引入一个新的定义：平衡因子（Balance Factor），是指一个节点的左子树高度减去右子树高度。所以，AVL树的性质等价于每个节点的平衡因子的绝对值不超过1。（之所以不在平衡因子的定义里加上绝对值，是因为后面要判断是左子树比右子树高还是右子树比左子树高）
下图就是一棵AVL树的例子。
可以看出，每个节点的左右子树高度差不超过1。这棵树确实不是一棵完全二叉树，但是其时间效率依然近似为(O(log(n)))，是可以接受的。
动态操作之后的重平衡
不难发现，对AVL树进行动态操作，有可能破坏AVL树的性质。因此，在每一次动态操作之后，我们都要对其进行某种措施，使其重新恢复AVL树性质。
等价变换
我们知道，一棵二叉搜索树的中序遍历序列是单调递增的，但是中序遍历序列相同的二叉搜索树的结构不一定相同，这里我们可以将中序遍历序列相同的二叉搜索树看做是等价的。比如以下这4棵二叉搜索树的中序遍历序列均为1 2 3，因此这4棵二叉搜索树都可以看做是等价的。
对于发生失衡的节点，常用“旋转”的方法使之恢复平衡。所谓“旋转”操作，就是以下两种结构的相互变换。
以左旋操作为例，令待旋转节点为x，x的父节点为p，x的右子节点为y，y的左右子节点分别为b和c，则左旋的操作步骤为：
- 将b设为x的右子节点。
- 将x设为y的左子节点。
- 将y设为p的左子节点/右子节点（这取决于原先x是p的左子节点还是右子节点）。
右旋操作与此对称，不再赘述。
几种失衡的情况
以下是一些失衡的情况，需要做不同的处理来使之恢复平衡。
LL与RR
所谓LL，就是失衡节点的左子树比右子树高，且左孩子的左子树又比右子树高或等高，这时候我们只需要对失衡节点做一次右旋操作就可以恢复平衡。如图：
RR就是失衡节点的右子树比左子树高，且右孩子的右子树又比左子树高或等高。恢复措施完全是对称的，这里不再赘述了。
LR与RL
所谓LR，就是失衡节点的左子树比右子树高，但左孩子的右子树却比左子树高。这时候我们需要进行两步旋转操作：首先对失衡节点的左孩子进行一次左旋，使得整个结构变成LL，然后对失衡节点进行一次右旋，这样才能平衡，如图：
RL与此是完全对称的，操作步骤也是对称的。
插入节点后的重平衡
在插入节点后，有可能出现失衡的情况，如图：
这时候就要进行相应的恢复平衡的措施。步骤如下：
- 上溯到最低的失衡节点。（如果上溯到根节点也没有发现失衡节点就可以不用重平衡了）
- 根据失衡类型（LL、LR、RL、RR）进行相应的调整。
调整后的子树的高度会与插入前保持一致，因此不需要进行后续的重平衡操作了。
重平衡的时间复杂度：(O(log(n)))。其中上溯的时间复杂度为(O(log(n)))，旋转的时间复杂度为(O(1))。
删除节点后的重平衡
对节点进行删除，也有可能导致出现失衡，如图：
这时候的操作和插入操作一样，先上溯到最深的失衡节点然后进行调整。
但是！调整后的子树的高度有可能会变化，这就意味着这棵子树虽然恢复了平衡，但是有可能反而会导致父节点的失衡，如图：
因此，我们需要进一步上溯到父节点，然后进行重平衡处理。
同样的，这样做可能会继续导致父节点的父节点的失衡，因此我们需要不断地上溯、重平衡，直到上溯到的节点不再失衡为止。如果上溯到根节点依然没有发现失衡节点，那么自然就不需要再进行重平衡了。
重平衡的时间复杂度：(O(log(n)))。其中上溯的时间复杂度为(O(log(n)))，旋转的时间复杂度为(O(1))。
代码实现
类定义
AVL树类框架
为了能够让AVL树能够适应不同的数据类型（int、float、long）等，我们以模板类的方式来实现。
整个AVL树类应该对外提供以下接口：查找节点是否存在、插入节点、删除节点。
为了隐藏实现细节，只暴露接口，我们将AVL树节点类以private嵌套类的形式封装在AVL树内部。
另外，为了方便，我们引入一个哑结点，其左孩子为整棵树的根节点，父节点和右孩子为nullptr。
由于插入、删除操作为动态操作，除了哑结点之外的所有节点全都是通过new运算符动态分配在堆内存中的，因此我们需要一种方式在AVL树对象销毁时将动态分配出来的节点所占用的内存空间释放掉。因为我们释放节点时只能在左右孩子均释放之后才能释放当前节点（否则会因为访问未分配的内存而引发程序异常退出），因此我们需要单独定义一个函数来递归的释放节点。
因此，整个AVL树类的大体框架如下：
template<typename T> class AVLTree { class AVLTreeNode { // ... }; AVLTreeNode dummyHead; public: AVLTree() : /* ... */ {} virtual ~AVLTree() { // ... } protected: // 上述3个接口（存在、插入、删除）均依赖于这个内部接口。 // 返回给定数据所在的节点。如果不存在的话，就返回插入操作中所插入的节点的父节点。 AVLTreeNode *find(T data) { // ... } public: // 判断AVL树中是否存在指定数据所在的节点。 bool exists(T data) { // ... } // 如果给定数据所在的节点不存在，则插入节点。 void insert(T data) { // ... } // 如果存在给定数据所在的节点，则删除节点。 void remove(T data) { // ... } protected: // 释放以给定节点为根节点的子树所占用的内存空间 void release(AVLTreeNode *node) { // ... } }; AVL节点类框架
而AVL树节点类有以下几个成员变量：数据、父节点、左右孩子节点、以该节点为根节点的子树高度（以下简称“该节点的高度”）。为了便于操作，类的内部也定义了一些接口，同时给AVL树类暴露了两个接口——插入和删除。注意这里AVL树节点类并没有定义为模板类，这是因为节点类的存放的数据类型是跟随着AVL树的数据类型的。
大体框架如下：
class AVLTreeNode { public: T data; AVLTreeNode *parent; AVLTreeNode *left; AVLTreeNode *right; std::size_t height; public: explicit AVLTreeNode(T data) : /* ... */ { // ... } protected: // 更新高度 void updateHeight() { // ... } // 计算平衡因子 int getBalanceFactor() { // ... } // 判断平衡因子是否在可接受的范围内 bool isBalanceFactorLegal() { // ... } // 判断是否为哑结点 bool isDummyHead() { // ... } // 判断是否为父节点的左孩子 bool isLeftChild() { // ... } // 将另一个节点作为当前节点的左孩子 void connectLeft(AVLTreeNode *child) { // ... } // 将另一个节点作为当前节点的右孩子 void connectRight(AVLTreeNode *child) { // ... } // 右旋 AVLTreeNode *rotateClockwise() { // ... } // 左旋 AVLTreeNode *rotateCounterclockwise() { // ... } // 对LL的情况进行重平衡 AVLTreeNode *reBalanceLeftLeft() { // ... } // 对LR的情况进行重平衡 AVLTreeNode *reBalanceLeftRight() { // ... } // 对RL的情况进行重平衡 AVLTreeNode *reBalanceRightLeft() { // ... } // 对RR的情况进行重平衡 AVLTreeNode *reBalanceRightRight() { // ... } // 重平衡 AVLTreeNode *reBalance() { // ... } public: // 以下两个接口虽然是public的，但是由于AVL树节点类在外层的AVL树类中是private的，所以这两个接口只对AVL树类可见，而在类外不可见。 // 将新节点插入到当前节点的底部 void insert(T newData) { // ... } // 删除当前节点 void remove() { // ... } }; AVL树节点接口实现
初始化节点对象时，我们只需要初始化数据即可，父节点、左右孩子均设为nullptr。按照此前对树高的定义，该节点的高度为1。
explicit AVLTreeNode(T data) : data(data), parent(nullptr), left(nullptr), right(nullptr), height(1) {} 在设置左右孩子节点的时候，自身的height成员变量不会自己变，因此我们需要手动更新高度为左右子树各自的高度的最大值加上1。
void updateHeight() { std::size_t leftHeight = left == nullptr ? 0 : left->height; std::size_t rightHeight = right == nullptr ? 0 : right->height; height = std::max(leftHeight, rightHeight) + 1; } 计算平衡因子，理论上只需要用左子树高度减去右子树高度即可，但是实际上由于左右子树高度都是用std::size_t存储的，虽然std::size_t在不同的平台上的具体实现有可能有所不同，但是都是unsigned的（可能是unsigned long long或unsigned long等），因此直接相减依然会得到unsigned的数据，可能不能得到正确的结果。所以这里需要根据左右子树的相对大小具体处理。因为平衡因子的取值只有可能在-1、0、1之间，以及短暂的处于-2、2，因此用int存储完全足够了。
int getBalanceFactor() { std::size_t leftHeight = left == nullptr ? 0 : left->height; std::size_t rightHeight = right == nullptr ? 0 : right->height; int diff = leftHeight > rightHeight ? leftHeight - rightHeight : rightHeight - leftHeight; return leftHeight > rightHeight ? diff : -diff; } 判断平衡因子是否在-1~1之间，我们单独定义一个函数，这样在需要判断的时候就不用单独定义一个变量存储平衡因子了：
bool isBalanceFactorLegal() { auto balanceFactor = getBalanceFactor(); return balanceFactor >= -1 && balanceFactor <= 1; } 判断节点是否为哑结点，根据此前的定义，只需要判断父节点是否为空：
bool isDummyHead() { return parent == nullptr; } 判断节点是否为父节点的左孩子：
bool isLeftChild() { return this == parent->left; } 将新节点作为当前节点的左/右孩子，我们首先需要更新当前节点的子节点，以及子节点（如果非空）的父节点，然后更新高度：
void connectLeft(AVLTreeNode *child) { left = child; if (child != nullptr) child->parent = this; updateHeight(); } void connectRight(AVLTreeNode *child) { right = child; if (child != nullptr) child->parent = this; updateHeight(); } 对节点进行左旋、右旋，并返回旋转后在原来位置上新的节点：
AVLTreeNode *rotateClockwise() { auto l = left; if (l == nullptr) return this; auto lr = l->right; auto p = parent; bool isLeft = isLeftChild(); // 节点之间的重连 connectLeft(lr); l->connectRight(this); if (isLeft) p->connectLeft(l); else p->connectRight(l); return l; } AVLTreeNode *rotateCounterclockwise() { auto r = right; if (right == nullptr) return this; auto rl = right->left; auto p = parent; bool isLeft = isLeftChild(); connectRight(rl); r->connectLeft(this); if (isLeft) p->connectLeft(r); else p->connectRight(r); return r; } 对不同的失衡类型进行重平衡，并返回重平衡后原来位置上新的节点：
AVLTreeNode *reBalanceLeftLeft() { return rotateClockwise(); } AVLTreeNode *reBalanceLeftRight() { left->rotateCounterclockwise(); return rotateClockwise(); } AVLTreeNode *reBalanceRightLeft() { right->rotateClockwise(); return rotateCounterclockwise(); } AVLTreeNode *reBalanceRightRight() { return rotateCounterclockwise(); } 重平衡的统一接口，失衡类型的判断在接口内部进行：
AVLTreeNode *reBalance() { int balanceFactor = getBalanceFactor(); int sonBalanceFactor; if (balanceFactor == 0) { // 如果平衡因子等于0，就不需要重平衡了 return this; } AVLTreeNode *son = nullptr; if (balanceFactor > 0) { // 左子树高于右子树 son = left; sonBalanceFactor = son->getBalanceFactor(); return sonBalanceFactor < 0 ? reBalanceLeftRight() // 对左孩子来说，其右子树高于左子树，为LR : reBalanceLeftLeft(); // 对左孩子来说，其左子树高于右子树或者等高，为LL } else { // 右子树高于左子树 son = right; sonBalanceFactor = son->getBalanceFactor(); return sonBalanceFactor > 0 ? reBalanceRightLeft() // 对右孩子来说，其左子树高于右子树，为RL : reBalanceRightRight(); // 对右孩子来说，其右子树高于左子树或者等高，为RR } } 在当前节点的下方插入一个新的节点，步骤：
- 判断要插入的数据是否与当前节点的数据相同，如果当前节点不是哑结点且新数据与存放的数据相同则不需要插入，直接退出。
- 判断新数据与当前节点的数据的大小关系，并决定是插入到左边还是右边。如果当前节点是哑结点则无条件插入到左边。
- 上溯到最深的失衡节点（边上溯边更新高度），直到上溯到哑结点为止。
- 如果上溯到哑结点了，说明没有节点出现失衡，结束。
- 如果发现某个节点失衡了，那就重新平衡。
代码：
void insert(T newData) { if (!isDummyHead() && newData == data) return; auto cur = new AVLTreeNode(newData, this); if (isDummyHead() || newData < data) { connectLeft(cur); } else { connectRight(cur); } do { cur = cur->parent; cur->updateHeight(); } while (!cur->isDummyHead() && cur->isBalanceFactorLegal()); if (cur->isDummyHead()) { return; } cur->reBalance(); } 删除当前节点，步骤：
- 按照二叉搜索树删除节点的步骤删除该节点。
- 上溯到第一个出现失衡的节点。
- 重平衡，继续上溯并重平衡，直到不再遇到失衡节点为止。
- 释放该节点所占用的内存空间。
代码：
void remove() { bool hasLeftChild = left != nullptr; bool hasRightChild = right != nullptr; AVLTreeNode *cur = parent; // 按照当前节点的子节点数量分情况讨论 if (hasLeftChild) { if (hasRightChild) { // 左右孩子节点都有，用当前节点的中序遍历后继替换掉，然后转而删除后继节点 auto successor = right; for (; successor->left != nullptr; successor = successor->left); data = successor->data; successor->remove(); return; } else { // 只有左子节点，将父节点的子节点设为当前节点的左子节点 if (isLeftChild()) { parent->connectLeft(left); } else { parent->connectRight(left); } } } else { if (hasRightChild) { // 只有右子节点，将父节点的子节点设为当前节点的右子节点 if (isLeftChild()) { parent->connectLeft(right); } else { parent->connectRight(right); } } else { // 没有孩子节点，将父节点的子节点置空 if (isLeftChild()) { parent->connectLeft(nullptr); } else { parent->connectRight(nullptr); } } } while (!cur->isDummyHead() && cur->isBalanceFactorLegal()) { cur = cur->parent; cur->updateHeight(); } for (; !cur->isDummyHead() && !cur->isBalanceFactorLegal(); cur = cur->parent) { cur = cur->reBalance(); } delete this; } AVL树接口实现
初始化：
AVLTree() : dummyHead(T()) {} find内部接口，按照二叉树查找节点的方法，查找给定数据所在的节点。如果不存在的话，就返回插入操作中所插入的节点的父节点。
AVLTreeNode *find(T data) { auto cur = dummyHead.left; if (cur == nullptr) return &dummyHead; while (cur->data != data) { if (data < cur->data) { if (cur->left == nullptr) { return cur; } cur = cur->left; } else { if (cur->right == nullptr) { return cur; } cur = cur->right; } } return cur; } 判断给定的数据是否存在，通过判断find接口返回的节点存储的数据是否为给定的数据来实现。（如果整棵树没有节点，那么find将会返回哑结点，因此还需额外判断返回的是否为哑结点）
bool exists(T data) { AVLTreeNode *found = find(data); return found != &dummyHead && found->data == data; } 插入节点：（由于在节点的insert接口内判断了新的数据与当前节点的数据是否相等，因此树的插入节点的接口无需再判断了）
void insert(T data) { AVLTreeNode *found = find(data); found->insert(data); } 删除节点：
void remove(T data) { AVLTreeNode *found = find(data); if (found != &dummyHead && found->data == data) found->remove(); } 内存释放：
void release(AVLTreeNode *node) { if (node == nullptr) return; release(node->left); release(node->right); delete node; } virtual ~AVLTree() { release(dummyHead.left); } 完整代码
由于嵌套类看起来非常冗长，不好看，因此我们将AVL树类和AVL树节点类单独放在两个文件内，AVL树类里面#include对应的文件。
AVLTreeNode.cpp文件内定义节点类：
// AVLTreeNode.cpp class AVLTreeNode { public: T data; AVLTreeNode *parent; AVLTreeNode *left; AVLTreeNode *right; std::size_t height; public: explicit AVLTreeNode(T data) : data(data), parent(nullptr), left(nullptr), right(nullptr), height(1) {} protected: // 更新高度 void updateHeight() { std::size_t leftHeight = left == nullptr ? 0 : left->height; std::size_t rightHeight = right == nullptr ? 0 : right->height; height = std::max(leftHeight, rightHeight) + 1; } // 计算平衡因子 int getBalanceFactor() { std::size_t leftHeight = left == nullptr ? 0 : left->height; std::size_t rightHeight = right == nullptr ? 0 : right->height; int diff = leftHeight > rightHeight ? leftHeight - rightHeight : rightHeight - leftHeight; return leftHeight > rightHeight ? diff : -diff; } // 判断平衡因子是否在可接受的范围内 bool isBalanceFactorLegal() { auto balanceFactor = getBalanceFactor(); return balanceFactor >= -1 && balanceFactor <= 1; } // 判断是否为哑结点 bool isDummyHead() { return parent == nullptr; } // 判断是否为父节点的左孩子 bool isLeftChild() { return this == parent->left; } // 将另一个节点作为当前节点的左孩子 void connectLeft(AVLTreeNode *child) { left = child; if (child != nullptr) child->parent = this; updateHeight(); } // 将另一个节点作为当前节点的右孩子 void connectRight(AVLTreeNode *child) { right = child; if (child != nullptr) child->parent = this; updateHeight(); } // 右旋 AVLTreeNode *rotateClockwise() { auto l = left; if (l == nullptr) return this; auto lr = l->right; auto p = parent; bool isLeft = isLeftChild(); // 节点之间的重连 connectLeft(lr); l->connectRight(this); if (isLeft) p->connectLeft(l); else p->connectRight(l); return l; } // 左旋 AVLTreeNode *rotateCounterclockwise() { auto r = right; if (right == nullptr) return this; auto rl = right->left; auto p = parent; bool isLeft = isLeftChild(); connectRight(rl); r->connectLeft(this); if (isLeft) p->connectLeft(r); else p->connectRight(r); return r; } // 对LL的情况进行重平衡 AVLTreeNode *reBalanceLeftLeft() { return rotateClockwise(); } // 对LR的情况进行重平衡 AVLTreeNode *reBalanceLeftRight() { left->rotateCounterclockwise(); return rotateClockwise(); } // 对RL的情况进行重平衡 AVLTreeNode *reBalanceRightLeft() { right->rotateClockwise(); return rotateCounterclockwise(); } // 对RR的情况进行重平衡 AVLTreeNode *reBalanceRightRight() { return rotateCounterclockwise(); } // 重平衡 AVLTreeNode *reBalance() { int balanceFactor = getBalanceFactor(); int sonBalanceFactor; if (balanceFactor == 0) { // 如果平衡因子等于0，就不需要重平衡了 return this; } AVLTreeNode *son = nullptr; if (balanceFactor > 0) { // 左子树高于右子树 son = left; sonBalanceFactor = son->getBalanceFactor(); return sonBalanceFactor < 0 ? reBalanceLeftRight() // 对左孩子来说，其右子树高于左子树，为LR : reBalanceLeftLeft(); // 对左孩子来说，其左子树高于右子树或者等高，为LL } else { // 右子树高于左子树 son = right; sonBalanceFactor = son->getBalanceFactor(); return sonBalanceFactor > 0 ? reBalanceRightLeft() // 对右孩子来说，其左子树高于右子树，为RL : reBalanceRightRight(); // 对右孩子来说，其右子树高于左子树或者等高，为RR } } public: // 以下两个接口虽然是public的，但是由于AVL树节点类在外层的AVL树类中是private的，所以这两个接口只对AVL树类可见，而在类外不可见。 // 将新节点插入到当前节点的底部 void insert(T newData) { if (!isDummyHead() && newData == data) return; auto cur = new AVLTreeNode(newData, this); if (isDummyHead() || newData < data) { connectLeft(cur); } else { connectRight(cur); } do { cur = cur->parent; cur->updateHeight(); } while (!cur->isDummyHead() && cur->isBalanceFactorLegal()); if (cur->isDummyHead()) { return; } cur->reBalance(); } // 删除当前节点 void remove() { bool hasLeftChild = left != nullptr; bool hasRightChild = right != nullptr; AVLTreeNode *cur = parent; // 按照当前节点的子节点数量分情况讨论 if (hasLeftChild) { if (hasRightChild) { // 左右孩子节点都有，用当前节点的中序遍历后继替换掉，然后转而删除后继节点 auto successor = right; for (; successor->left != nullptr; successor = successor->left); data = successor->data; successor->remove(); return; } else { // 只有左子节点，将父节点的子节点设为当前节点的左子节点 if (isLeftChild()) { parent->connectLeft(left); } else { parent->connectRight(left); } } } else { if (hasRightChild) { // 只有右子节点，将父节点的子节点设为当前节点的右子节点 if (isLeftChild()) { parent->connectLeft(right); } else { parent->connectRight(right); } } else { // 没有孩子节点，将父节点的子节点置空 if (isLeftChild()) { parent->connectLeft(nullptr); } else { parent->connectRight(nullptr); } } } while (!cur->isDummyHead() && cur->isBalanceFactorLegal()) { cur = cur->parent; cur->updateHeight(); } for (; !cur->isDummyHead() && !cur->isBalanceFactorLegal(); cur = cur->parent) { cur = cur->reBalance(); } delete this; } }; AVLTree.cpp文件内定义AVL树类：
// AVLTree.cpp template<typename T> class AVLTree { #include "AVLTreeNode.cpp" AVLTreeNode dummyHead; public: AVLTree() : dummyHead(T()) {} virtual ~AVLTree() { release(dummyHead.left); } protected: // 上述3个接口（存在、插入、删除）均依赖于这个内部接口。 // 返回给定数据所在的节点。如果不存在的话，就返回插入操作中所插入的节点的父节点。 AVLTreeNode *find(T data) { auto cur = dummyHead.left; if (cur == nullptr) return &dummyHead; while (cur->data != data) { if (data < cur->data) { if (cur->left == nullptr) { return cur; } cur = cur->left; } else { if (cur->right == nullptr) { return cur; } cur = cur->right; } } return cur; } public: // 判断AVL树中是否存在指定数据所在的节点。 bool exists(T data) { AVLTreeNode *found = find(data); return found != &dummyHead && found->data == data; } // 如果给定数据所在的节点不存在，则插入节点。 void insert(T data) { AVLTreeNode *found = find(data); found->insert(data); } // 如果存在给定数据所在的节点，则删除节点。 void remove(T data) { AVLTreeNode *found = find(data); if (found != &dummyHead && found->data == data) found->remove(); } protected: // 释放以给定节点为根节点的子树所占用的内存空间 void release(AVLTreeNode *node) { if (node == nullptr) return; release(node->left); release(node->right); delete node; } }; PS：事实上，实际的代码实现比这还要复杂，还要考虑到重载赋值运算符、传参的时候传入的是左值引用还是右值引用等等，这里主要是为了讲述原理就不搞那么复杂了。
