《 C++ 修炼全景指南：十 》自平衡的艺术：深入了解 AVL 树的核心原理与实现

摘要

本文深入探讨了 AVL 树（自平衡二叉搜索树）的概念、特点以及实现细节。我们首先介绍了 AVL 树的基本原理，并详细分析了其四种旋转操作，包括左旋、右旋、左右双旋和右左双旋，阐述了它们在保持树平衡中的重要作用。接着，本文从头到尾详细描述了 AVL 树的插入、删除和查找操作，配合完整的代码实现和详尽的注释，使读者能够全面理解这些操作的执行过程。

此外，我们还提供了 AVL 树的遍历方法，包括中序、前序和后序遍历，帮助读者更好地掌握 AVL 树的结构和节点间关系。通过对 AVL 树的优缺点进行分析，本文揭示了其在不同应用场景中的适用性，为读者选择合适的数据结构提供了参考。通过对 AVL 树的全面解析，本文旨在为读者提供一个完整的学习路径，帮助他们掌握这一强大的数据结构。

1、引言

在计算机科学中，数据结构是程序设计的基石，而二叉搜索树 (BST) 则是最基本的树形数据结构之一。二叉搜索树提供了高效的查找、插入和删除操作，但在最坏情况下，这些操作的时间复杂度可能退化为线性。这种退化主要发生在 BST 呈现为链状结构时，例如在顺序插入数据时。因此，为了保证二叉搜索树的性能，出现了多种自平衡树，如红黑树、AVL树、B树等。

关于二叉搜索树的更多细节请见我的这篇博客：《 C++ 修炼全景指南：九 》打破编程瓶颈！掌握二叉搜索树的高效实现与技巧
关于红黑树的更多细节请见我的这篇博客：《 C++ 修炼全景指南：十一 》穿越数据的红与黑：掌握数据平衡的极致艺术

在这些自平衡树中，AVL 树是最早被发明的一种。它由 Adelson-Velsky 和 Landis 于 1962 年提出，因其发明者名字的首字母缩写而得名。AVL 树在插入和删除节点后，通过旋转操作保持树的平衡，从而确保所有操作的时间复杂度始终维持在 O(log⁡n) 。这一特性使得 AVL 树成为实现高效动态集合的一种重要选择。本文将深入探讨AVL树的结构、插入和删除操作的实现，以及其在实际应用中的优缺点。

本篇博客所涉及的所有代码均可从我的代码仓库获得：https://git.lenyiin.com/Lenyiin/AVLTree

2、AVL树概述

AVL 树是一种自平衡二叉搜索树，每个节点都存储一个平衡因子（Balance Factor，简称 BF），用于表示该节点的左子树和右子树的高度差。AVL 树的基本特性是，对于每个节点，要求其左子树和右子树的高度差至多为 1。因此，AVL 树的高度始终保持在 O(log⁡n) ，从而保证查找、插入和删除操作的时间复杂度为 O(log⁡n) 。

2.1、平衡因子

AVL 树中每个节点的平衡因子是该节点右子树的高度减去左子树的高度，即：

​ $$BF(node)=height(rightsubtree)-height(leftsubtree)$$

• 当平衡因子为 0 时，表示左子树和右子树高度相等。
• 当平衡因子为正数时，表示右子树比左子树高。
• 当平衡因子为负数时，表示左子树比右子树高。

AVL树通过限制每个节点的平衡因子在-1、0、1之间，确保树始终保持平衡状态。

2.2、旋转操作

为了保持AVL树的平衡，在插入或删除节点后，如果某个节点的平衡因子超出范围（即绝对值大于1），则需要进行旋转操作来恢复平衡。AVL树主要有四种旋转操作：

• 单右旋（LL型）：用于修复左子树的左子节点插入导致的不平衡。
• 单左旋（RR型）：用于修复右子树的右子节点插入导致的不平衡。
• 先左旋后右旋（LR型）：用于修复左子树的右子节点插入导致的不平衡。
• 先右旋后左旋（RL型）：用于修复右子树的左子节点插入导致的不平衡。

通过这些旋转操作，AVL树能够在插入和删除节点后迅速恢复平衡，从而保持其高效的操作性能。

2.3、AVL树的应用场景

AVL 树适用于需要频繁查找和插入操作的数据场景，并且对查询操作的效率要求较高。例如，数据库索引、内存中的有序集合、符号表等。虽然 AVL 树在插入和删除操作中需要更多的旋转操作来保持平衡，因此可能不如红黑树等自平衡树高效，但在需要严格平衡以保证查询效率的场景下，AVL 树仍然是一种理想的选择。

2.4、本文的结构

接下来，本文将详细阐述 AVL 树的节点结构、插入与删除操作的具体实现以及旋转操作的原理。随后，我们将对 AVL 树的优缺点进行分析，并探讨其在实际应用中的表现。通过对 AVL 树的全面分析，读者将能够深入理解这一数据结构，并在实际开发中灵活运用。

3、AVL 树的实现

3.1、AVL树节点结构

首先，我们需要定义一个基本的AVL树节点结构。该结构体将包含节点的键值对、左右子节点、父节点，以及用于维护树平衡的平衡因子。平衡因子表示节点右子树高度与左子树高度的差值。

template <class K, class V>
struct AVLTreeNode 
{AVLTreeNode<K, V>* _left;  // 左子节点AVLTreeNode<K, V>* _right; // 右子节点AVLTreeNode<K, V>* _parent; // 父节点int _bf; // 平衡因子 balance factorstd::pair<K, V> _kv; // 键值对// 构造函数AVLTreeNode(const std::pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv) {}
};

详细解释

• _left：指向左子节点的指针。
• _right：指向右子节点的指针。
• _parent：指向父节点的指针，用于在平衡调整时便于向上回溯。
• _bf：平衡因子，用于判断树是否需要旋转。平衡因子为右子树高度减去左子树高度。
• _kv：存储节点的键值对。

接下来，我们将基于这个节点结构体，开始AVL树的实现。我们将逐步构建各个功能模块，包括插入、删除、平衡操作等。

3.2、插入操作

插入节点时，首先遵循二叉搜索树的规则进行节点的插入，然后通过调整平衡因子和旋转来维护树的平衡。

bool Insert(const std::pair<K, V>& kv)
{// 1. 先按搜索树的规则进行插入if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;	// 如果相等, 表示已经有了, 不需要插入}}// 找到位置cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}// 2. 更新平衡因子while (parent){if (cur == parent->_right){parent->_bf++;	// 插在右边, 平衡因子++}else{parent->_bf--;	// 插在左边, 平衡因子--}if (parent->_bf == 0){// 说明 parent 所在的子树高度不变, 更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){// 说明 parent 所在子树的高度变了, 继续往上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// parent 所在的子树出现问题了, 需要旋转处理一下// 1. 旋转前提是保持它依旧是搜索二叉树// 2. 旋转成平衡树if (parent->_bf == 2){if (cur->_bf == 1){// 左旋RotateL(parent);}else if (cur->_bf == -1){// 右左双旋RotateRL(parent);}}else if (parent->_bf == -2){if (cur->_bf == -1){// 右旋RotateR(parent);}else if (cur->_bf == 1){// 左右双旋RotateLR(parent);}}// 旋转完成后, parent 所在的树的高度恢复到了插入节点前的高度// 如果是子树, 对上一层没有影响, 更新结束break;}}return true;
}

详细解释

• Insert：插入节点的函数。它根据键值对的大小关系选择插入到左子树还是右子树。

• _bf 的调整：如果插入在左子树，平衡因子减 1；如果插入在右子树，平衡因子加 1。

• 插入节点后，我们需要检查树是否仍然平衡。如果树失去平衡（平衡因子的绝对值大于1），就需要执行旋转操作来恢复平衡。

  • RotateL（右子树的右子节点插入）：左单旋
  • RotateR（左子树的左子节点插入）：右单旋
  • RotateRL（右子树的左子节点插入）：右左双旋。
  • RotateLR（左子树的右子节点插入）：先左旋后右旋。

3.3、旋转操作

在 AVL 树中，保持树的平衡性是至关重要的，这主要通过四种旋转操作来实现：左旋、右旋、左-右双旋和右-左双旋。这些旋转操作用于修复因插入或删除节点导致的树不平衡，确保 AVL 树的高度维持在 O(log⁡n) 。下面，我们详细描述这四种旋转方式。

3.3.1、左单旋

场景：当新节点插入到某个节点的右子树的右子节点时，可能导致该节点失衡。此时，需要进行单左旋操作来恢复平衡。

旋转过程：

• 假设不平衡节点为 A，其右子节点为 B。
• B 的左子树 BL 将成为 A 的右子树。
• B 成为新的子树根节点，而 A 成为 B 的左子节点。

示例图：

插入导致的结构：

  A\B\C

单左旋后的结构：

    B/ \A   C

代码实现：

// 左单旋
void RotateL(Node* parent)
{Node* ppNode = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;// 1. 原来 parent 是这棵树的根, 现在 subR 是根if (parent == _root){_root = subR;subR->_parent = nullptr;}// 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;
}

解释：

• subR 指向 A 的右子节点 B。
• B 的左子树 subRL 被挂接到 A 的右子树。
• B 成为新的根节点，A 成为 B 的左子节点。

3.3.2、右单旋

场景：当新节点插入到某个节点的左子树的左子节点时，可能导致该节点失衡。此时，需要进行右单旋操作来恢复平衡。

旋转过程：

• 假设不平衡节点为 A，其左子节点为 B。
• B 的右子树 BR 将成为 A 的左子树。
• B 成为新的子树根节点，而 A 成为 B 的右子节点。

示例图：

插入导致的结构：

    A/ B   / 
C 

单右旋后的结构：

    B/ \C   A

代码实现

// 右单旋
void RotateR(Node* parent)
{Node* ppNode = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;
}

详细解释：

• parent 是节点 A
• subL 指向 A 的左子节点 B。
• B 的右子树 subLR 被挂接到 A 的左子树。
• B 成为新的根节点，A 成为 B 的右子节点。

3.3.3、左右双旋

场景：当新节点插入到某个节点的左子树的右子节点时，可能导致该节点失衡。此时，需要先对其左子树进行左旋，再对整个子树进行右旋来恢复平衡。

旋转过程：

1. 左旋：对左子节点 B 进行单左旋，使得 B 的右子节点 C 成为新的根节点。
2. 右旋：对不平衡节点 A 进行单右旋，使得 C 成为新的根节点。

示例图：

插入导致的结构：

    A/B\C

左旋后的中间结构：

    A/C/
B

右旋后的最终结构：

    C/ \B   A

代码实现：

// 左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}
}

解释：

• 首先对 A 的左子节点 B 进行单左旋，使得 C 成为新的子树根节点。
• 然后对不平衡节点 A 进行单右旋，使得 C 成为新的根节点。

3.3.4、右左双旋

场景：当新节点插入到某个节点的右子树的左子节点时，可能导致该节点失衡。此时，需要先对其右子树进行右旋，再对整个子树进行左旋来恢复平衡。

旋转过程：

1. 右旋：对右子节点 B 进行单右旋，使得 B 的左子节点 C 成为新的根节点。
2. 左旋：对不平衡节点 A 进行单左旋，使得 C 成为新的根节点。

示例图：

插入导致的结构：

  A\B/C

右旋后的中间结构：

  A\C\B

左旋后的最终结构：

    C/ \A   B

代码实现：

// 右左双旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}
}

解释：

• 首先对 A 的右子节点 B 进行单右旋，使得 C 成为新的子树根节点。
• 然后对不平衡节点 A 进行单左旋，使得 C 成为新的根节点。

3.3.5、旋转操作总结

通过这四种旋转操作，AVL 树能够在插入或删除节点后迅速恢复平衡。无论是单旋转还是双旋转，这些操作的时间复杂度都为 O(1) ，因为它们只涉及常数级别的节点重新链接。这使得 AVL 树在保持自平衡状态的同时，能够保证所有基本操作的时间复杂度为 O(log⁡n) 。

3.4、删除操作

在 AVL 树中，节点的删除操作相对复杂，因为删除节点后不仅要移除目标节点，还需要重新平衡树，以保持 AVL 树的平衡性质。AVL 树的删除操作可以分为以下几个步骤：

1. 找到并删除节点：和普通的二叉搜索树（BST）删除操作类似。
2. 调整平衡因子：从删除的节点开始，沿着路径向上调整每个节点的平衡因子。
3. 执行旋转操作：在调整平衡因子的过程中，如果发现某个节点失衡（平衡因子的绝对值大于1），需要进行相应的旋转操作来恢复平衡。

我们将按照这三个步骤详细解释AVL树中节点的删除操作。

3.4.1、找到并删除节点

首先，我们需要在AVL树中找到要删除的节点，并按照 BST 的删除规则将其删除。BST中的删除操作有以下几种情况：

• 节点是叶子节点：直接删除该节点即可。
• 节点有一个子节点：用其唯一的子节点替换它。
• 节点有两个子节点：找到该节点的中序后继节点，用后继节点的值替换该节点的值，然后删除后继节点。

3.4.2、调整平衡因子

在删除节点后，需要调整其祖先节点的平衡因子。沿着从删除节点到根节点的路径进行调整，规则如下：

• 如果删除的是左子树的节点，则父节点的平衡因子增加1。
• 如果删除的是右子树的节点，则父节点的平衡因子减少1。

在调整平衡因子的过程中，如果某个节点的平衡因子的绝对值超过1，就需要通过旋转来恢复平衡。

3.4.3、执行旋转操作

在删除节点并调整平衡因子后，如果发现某个节点失衡，则需要根据不同的失衡情况进行旋转操作。

3.4.4、总结

删除操作是AVL树中较为复杂的一部分。需要仔细处理删除节点的不同情况，及时更新平衡因子，并在必要时进行旋转操作以保持树的平衡。每个步骤都需要在 O(log⁡n) 的时间内完成，确保 AVL 树的效率。通过精心设计的平衡调整机制，AVL 树在删除操作后能够快速恢复平衡，保持所有操作的时间复杂度为 O(log⁡n) 。

3.5、遍历操作

在 AVL 树中，遍历是一项基础操作，用于访问树中的每个节点。AVL 树继承了二叉搜索树（BST）的性质，因此可以使用与 BST 相同的遍历方法，包括前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）、后序遍历（Post-order Traversal）、层序遍历（Level-order Traversal）等。下面将详细介绍这些遍历方法，并给出相应的代码实现。

3.5.1、前序遍历（Pre-order Traversal）

前序遍历的顺序是：先访问根节点，再访问左子树，最后访问右子树。其遍历顺序为 “根 -> 左 -> 右”。

前序遍历的递归实现：

// 前序遍历的递归实现
// 辅助函数
void _PreOrder(Node* root)
{if (root == nullptr){return;}std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;   // 访问根节点_PreOrder(root->_left);   // 访问左子树_PreOrder(root->_right);  // 访问右子树
}void PreOrder()
{_PreOrder(_root);std::cout << std::endl;
}

前序遍历的非递归实现（使用栈）：

// 前序遍历的非递归实现
void PreOrder()
{if (_root == nullptr){return;}std::stack<Node*> stack;stack.push(_root);while (!stack.empty()) {Node* cur = stack.top();stack.pop();std::cout << cur->_kv.first << ":" << cur->_kv.second << std::endl;  // 访问当前节点// 先压入右子树再压入左子树（确保左子树先处理）if (cur->_right != nullptr){stack.push(cur->_right);}if (cur->_left != nullptr) {stack.push(cur->_left);}}std::cout << std::endl;
}

3.5.2、中序遍历（In-order Traversal）

中序遍历的顺序是：先访问左子树，再访问根节点，最后访问右子树。其遍历顺序为 “左 -> 根 -> 右”。对于 AVL 树，中序遍历会得到一个按序排列的节点序列。

中序遍历的递归实现：

// 中序遍历
void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;_InOrder(root->_right);
}void InOrder()
{_InOrder(_root);std::cout << std::endl;
}

中序遍历的非递归实现（使用栈）：

// 中序遍历 非递归
void InOrder()
{std::stack<Node*> stack;Node* cur = _root;while (cur != nullptr || !stack.empty()) {// 找到最左边的节点while (cur != nullptr) {stack.push(cur);cur = cur->_left;}// 处理当前节点cur = stack.top();stack.pop();std::cout << cur->_kv.first << ":" << cur->_kv.second << std::endl;// 转向右子树cur = cur->_right;}std::cout << std::endl;
}

3.5.3、后序遍历（Post-order Traversal）

后序遍历的顺序是：先访问左子树，再访问右子树，最后访问根节点。其遍历顺序为 “左 -> 右 -> 根”。

后序遍历的递归实现：

// 后序遍历的递归实现
// 辅助函数
void _PostOrder(Node* root) {if (root == nullptr){return;}_PostOrder(root->_left);    // 访问左子树_PostOrder(root->_right);   // 访问右子树std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;     // 访问根节点
}void PostOrder()
{_PostOrder(_root);std::cout << std::endl;
}

后序遍历的非递归实现（使用栈）：

// 后序遍历的非递归实现
void PostOrder()
{if (_root == nullptr){return;}std::stack<Node*> st;Node* cur = _root;Node* lastNode = nullptr; // 最近访问的节点while (cur || !st.empty()){while (cur){st.push(cur);cur = cur->_left;}Node* top = st.top();if ((top->_right == nullptr) || (lastNode == top->_right)){std::cout << top->_kv.first << ":" << top->_kv.second << std::endl;lastNode = top;st.pop();}else {cur = top->_right;}}std::cout << std::endl;
}

3.5.4、层序遍历（Level-order Traversal）

层序遍历是按层次逐层访问节点，先访问根节点，再访问其左右子节点，依次类推。可以使用队列来实现。

层序遍历的实现：

// 层序遍历
void LevelOrder()
{if (_root == nullptr){return;}std::queue<Node*> queue;queue.push(_root);while (!queue.empty()){Node* cur = queue.front();queue.pop();std::cout << cur->_kv.first << ":" << cur->_kv.second << std::endl;   // 访问当前节点if (cur->_left != nullptr) {queue.push(cur->_left);      // 将左子树压入队列}if (cur->_right != nullptr) {queue.push(cur->_right);     // 将右子树压入队列}}std::cout << std::endl;
}

3.5.5、总结

AVL 树的遍历方法与普通二叉搜索树类似，包括前序遍历、中序遍历、后序遍历和层序遍历。通过递归或非递归方式，我们可以访问 AVL 树的所有节点，并按照特定的顺序输出它们的键值。中**序遍历是最常用的遍历方法之一，特别是在需要输出一个有序序列时。层序遍历则常用于按层次输出或分析树的结构。**每种遍历方法都有其独特的应用场景，在编写和理解 AVL 树的相关算法时，选择合适的遍历方式十分重要。

3.6、查找操作

在AVL树中，查找操作主要依赖于树的有序性，即对于任意一个节点，左子树的所有节点都小于该节点，右子树的所有节点都大于该节点。查找过程从根节点开始，逐层向下比较查找值与当前节点的值，并根据比较结果选择进入左子树或右子树。

3.6.1、查找操作的步骤

1. 从根节点开始：从AVL树的根节点开始查找。
2. 比较当前节点的键值：
   • 如果查找的键等于当前节点的键，查找成功，返回当前节点。
   • 如果查找的键小于当前节点的键，进入左子树继续查找。
   • 如果查找的键大于当前节点的键，进入右子树继续查找。
3. 递归或迭代：重复上述步骤，直到找到匹配的节点或者子树为空（查找失败）。
4. 返回结果：找到目标节点则返回，否则返回 nullptr（表示查找失败）。

3.6.2、查找的递归实现

递归实现相对简单，直接通过函数递归调用在树中查找目标节点。

// 查找的递归实现
// 辅助函数
Node* _find(Node* root, const K& key)
{if (root == nullptr || root->_kv.first == key){return root;}if (key < root->_kv.first){return _find(root->_left, key);}else{return _find(root->_right, key);}
}

3.6.3、查找的非递归实现

非递归实现使用迭代方式，避免了递归调用带来的额外栈空间开销。

// 查找 非递归
Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first > key){cur = cur->_left;}else if (cur->_kv.first < key){cur = cur->_right;}else{return cur;}}return nullptr;
}

4、AVL 树的其他功能

除了基本的插入、查找、删除等操作，AVL 树还可以实现一些高级操作，如查找前驱和后继、区间查询、树的高度、判断是否是平衡二叉树等。这些操作可以扩展 AVL 树的功能，增加其实用性。

4.1、查找后继节点

前驱是指比某个节点值小的最大节点，后继则是比某个节点值大的最小节点。在 AVL 树中，查找前驱和后继是常见的操作，尤其在区间查询或范围搜索时非常有用。

查找后继的递归实现：

// 查找后继节点
Node* findMin(Node* node)
{while (node->_left != nullptr){node = node->_left;}return node;
}Node* FindSuccessor(Node* node)
{if (node->_right != nullptr){return findMin(node->_right);}Node* cur = _root;Node* successor = nullptr;while (cur != nullptr){if (node->_kv.first < cur->_kv.first){successor = cur;cur = cur->_left;}else if (node->_kv.first > cur->_kv.first){cur = cur->_right;}else{break;}}return successor;
}

查找后继时，如果节点有右子树，则后继为右子树中最小的节点；否则，后继为第一个大于该节点的祖先节点。

4.2、查找前驱节点

查找前驱的递归实现：

// 查找前驱节点
Node* findMax(Node* node)
{while (node->_right != nullptr){node = node->_right;}return node;
}Node* FindPredecessor(Node* node)
{if (node->_left != nullptr){return findMax(node->_left);}Node* cur = _root;Node* predecessor = nullptr;while (cur != nullptr){if (node->_kv.first < cur->_kv.first){cur = cur->_left;}else if (node->_kv.first > cur->_kv.first){predecessor = cur;cur = cur->_right;}else{break;}}return predecessor;
}

前驱的查找逻辑与后继类似，只是方向相反。

4.3、获取树的高度

// 获取树的高度
int Height(Node* root)
{if (root == nullptr){return 0;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

4.4、判断是否是平衡二叉树

// 判断是否是平衡二叉树
bool _IsBalance(Node* root)
{if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (abs(leftHeight - rightHeight) > 1){return false;}return _IsBalance(root->_left) && _IsBalance(root->_right);
}bool IsBalance()
{return _IsBalance(_root);
}

5、完整实现代码和测试

5.1、AVLTree.hpp

#pragma once#include <iostream>
#include <stack>
#include <queue>namespace Lenyiin
{template <class K, class V>struct AVLTreeNode{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;		// balance factor	平衡因子std::pair<K, V> _kv;	// key-value// 普通构造AVLTreeNode(const std::pair<K, V> &kv): _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}};template <class K, class V>class AVLTree{private:typedef AVLTreeNode<K, V> Node;public:bool Insert(const std::pair<K, V>& kv){// 1. 先按搜索树的规则进行插入if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;	// 如果相等, 表示已经有了, 不需要插入}}// 找到位置cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}// 2. 更新平衡因子while (parent){if (cur == parent->_right){parent->_bf++;	// 插在右边, 平衡因子++}else{parent->_bf--;	// 插在左边, 平衡因子--}if (parent->_bf == 0){// 说明 parent 所在的子树高度不变, 更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){// 说明 parent 所在子树的高度变了, 继续往上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// parent 所在的子树出现问题了, 需要旋转处理一下// 1. 旋转前提是保持它依旧是搜索二叉树// 2. 旋转成平衡树if (parent->_bf == 2){if (cur->_bf == 1){// 左旋RotateL(parent);}else if (cur->_bf == -1){// 右左双旋RotateRL(parent);}}else if (parent->_bf == -2){if (cur->_bf == -1){// 右旋RotateR(parent);}else if (cur->_bf == 1){// 左右双旋RotateLR(parent);}}// 旋转完成后, parent 所在的树的高度恢复到了插入节点前的高度// 如果是子树, 对上一层没有影响, 更新结束break;}}return true;}// 左单旋void RotateL(Node* parent){Node* ppNode = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;// 1. 原来 parent 是这棵树的根, 现在 subR 是根if (parent == _root){_root = subR;subR->_parent = nullptr;}// 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}// 右单旋void RotateR(Node* parent){Node* ppNode = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;}// 右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}}// 左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}}// 中序遍历//void _InOrder(Node* root)//{//	if (root == nullptr)//	{//		return;//	}//	_InOrder(root->_left);//	std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;//	_InOrder(root->_right);//}//void InOrder()//{//	_InOrder(_root);//	std::cout << std::endl;//}// 中序遍历 非递归void InOrder(){std::stack<Node*> stack;Node* cur = _root;while (cur != nullptr || !stack.empty()) {// 找到最左边的节点while (cur != nullptr) {stack.push(cur);cur = cur->_left;}// 处理当前节点cur = stack.top();stack.pop();std::cout << cur->_kv.first << ":" << cur->_kv.second << std::endl;// 转向右子树cur = cur->_right;}std::cout << std::endl;}// 前序遍历的递归实现// 辅助函数//void _PreOrder(Node* root)//{//	if (root == nullptr)//	{//		return;//	}//	std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;   // 访问根节点//	_PreOrder(root->_left);   // 访问左子树//	_PreOrder(root->_right);  // 访问右子树//}//void PreOrder()//{//	_PreOrder(_root);//	std::cout << std::endl;//}// 前序遍历的非递归实现void PreOrder(){if (_root == nullptr){return;}std::stack<Node*> stack;stack.push(_root);while (!stack.empty()) {Node* cur = stack.top();stack.pop();std::cout << cur->_kv.first << ":" << cur->_kv.second << std::endl;  // 访问当前节点// 先压入右子树再压入左子树（确保左子树先处理）if (cur->_right != nullptr){stack.push(cur->_right);}if (cur->_left != nullptr) {stack.push(cur->_left);}}std::cout << std::endl;}// 后序遍历的递归实现// 辅助函数//void _PostOrder(Node* root) {//	if (root == nullptr)//	{//		return;//	}//	_PostOrder(root->_left);    // 访问左子树//	_PostOrder(root->_right);   // 访问右子树//	std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;     // 访问根节点//}//void PostOrder()//{//	_PostOrder(_root);//	std::cout << std::endl;//}// 后序遍历的非递归实现void PostOrder(){if (_root == nullptr){return;}std::stack<Node*> st;Node* cur = _root;Node* lastNode = nullptr; // 最近访问的节点while (cur || !st.empty()){while (cur){st.push(cur);cur = cur->_left;}Node* top = st.top();if ((top->_right == nullptr) || (lastNode == top->_right)){std::cout << top->_kv.first << ":" << top->_kv.second << std::endl;lastNode = top;st.pop();}else {cur = top->_right;}}std::cout << std::endl;}// 层序遍历void LevelOrder(){if (_root == nullptr){return;}std::queue<Node*> queue;queue.push(_root);while (!queue.empty()){Node* cur = queue.front();queue.pop();std::cout << cur->_kv.first << ":" << cur->_kv.second << std::endl;   // 访问当前节点if (cur->_left != nullptr) {queue.push(cur->_left);      // 将左子树压入队列}if (cur->_right != nullptr) {queue.push(cur->_right);     // 将右子树压入队列}}std::cout << std::endl;}// 查找后继节点Node* findMin(Node* node){while (node->_left != nullptr){node = node->_left;}return node;}Node* FindSuccessor(Node* node){if (node->_right != nullptr){return findMin(node->_right);}Node* cur = _root;Node* successor = nullptr;while (cur != nullptr){if (node->_kv.first < cur->_kv.first){successor = cur;cur = cur->_left;}else if (node->_kv.first > cur->_kv.first){cur = cur->_right;}else{break;}}return successor;}// 查找前驱节点Node* findMax(Node* node){while (node->_right != nullptr){node = node->_right;}return node;}Node* FindPredecessor(Node* node){if (node->_left != nullptr){return findMax(node->_left);}Node* cur = _root;Node* predecessor = nullptr;while (cur != nullptr){if (node->_kv.first < cur->_kv.first){cur = cur->_left;}else if (node->_kv.first > cur->_kv.first){predecessor = cur;cur = cur->_right;}else{break;}}return predecessor;}// 获取树的高度int Height(Node* root){if (root == nullptr){return 0;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}// 判断是否是平衡二叉树bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (abs(leftHeight - rightHeight) > 1){return false;}return _IsBalance(root->_left) && _IsBalance(root->_right);}bool IsBalance(){return _IsBalance(_root);}// 查找 非递归//Node* Find(const K& key)//{//	Node* cur = _root;//	while (cur)//	{//		if (cur->_kv.first > key)//		{//			cur = cur->_left;//		}//		else if (cur->_kv.first < key)//		{//			cur = cur->_right;//		}//		else//		{//			return cur;//		}//	}//	return nullptr;//}// 查找的递归实现// 辅助函数Node* _find(Node* root, const K& key){if (root == nullptr || root->_kv.first == key){return root;}if (key < root->_kv.first){return _find(root->_left, key);}else{return _find(root->_right, key);}}// 查找节点Node* Find(const K& key){return _find(_root, key);}private:Node* _root = nullptr;};
}

5.2、AVLTree.cpp

#include "AVLTree.hpp"using namespace Lenyiin;void test_AVLTree()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};AVLTree<int, int> t;for (const auto& e : a){t.Insert(std::make_pair(e, e));}t.InOrder();t.PreOrder();t.PostOrder();t.LevelOrder();std::cout << t.IsBalance() << std::endl;auto ret = t.Find(6);if (ret == nullptr){std::cout << "没有找到" << std::endl;}else{std::cout << "找到了" << std::endl;std::cout << ret->_kv.first << ":" << ret->_kv.second << std::endl;}auto pre = t.FindPredecessor(ret);if (pre != nullptr){std::cout << ret->_kv.first << " 的前驱节点是: " << pre->_kv.first << std::endl;}else{std::cout << "前驱节点为空" << std::endl;}auto suc = t.FindSuccessor(ret);if (suc != nullptr){std::cout << ret->_kv.first << " 的后继节点是: " << suc->_kv.first << std::endl;}else{std::cout << "后继节点为空" << std::endl;}
}int main()
{test_AVLTree();return 0;
}

6、AVL树的优缺点和总结

6.1、优点

1. 平衡性保证：AVL 树是自平衡二叉搜索树，它严格保持了树的平衡状态。每个节点的左右子树高度差（平衡因子）最多为 1，因此在最坏情况下，AVL 树的高度被限制在 O(log⁡n) 级别。这保证了查找、插入、删除操作的时间复杂度始终为 O(log⁡n) ，使其在各种场景中表现出较高的效率。
2. 快速查找：由于 AVL 树保持了较高的平衡性，查找操作的性能得到了优化。相比于未平衡的二叉搜索树，AVL 树在查找操作中能够更快地找到目标节点。
3. 稳定的性能：AVL 树的平衡性维护使得其在最坏情况下（例如频繁的插入和删除操作）也能提供稳定的性能。无论数据插入的顺序如何，AVL 树都能保持平衡，避免出现链表化的情况。
4. 较好的空间利用率：AVL 树在保持平衡的同时，并不需要额外的节点空间，除了存储平衡因子。相比红黑树等其他自平衡树，AVL 树的平衡性更严格，查找性能更好。

6.2、缺点

1. 插入和删除的复杂性：AVL 树在插入和删除节点时，需要进行旋转操作以保持树的平衡。每次插入或删除操作都可能导致树的不平衡，从而触发重新平衡过程。虽然旋转操作的时间复杂度为 O(1) ，但在频繁的插入和删除场景中，这些旋转操作可能增加整体的处理时间。
2. 实现复杂性：AVL 树的实现相对较复杂，尤其是插入和删除操作。与红黑树相比，AVL 树需要更多的旋转操作来维持平衡，这使得其代码编写和维护的难度较大。
3. 额外的存储空间：为了维护平衡性，AVL 树的每个节点需要额外存储平衡因子(balance factor)，这增加了节点的内存开销。虽然这一开销较小，但对于内存非常敏感的系统，可能会有一定的影响。
4. 性能折衷：尽管 AVL 树在查找操作中表现优异，但其插入和删除操作的性能可能会受到影响。在一些场景中，如需要频繁插入和删除的情况下，红黑树可能比 AVL 树更具优势，因为红黑树的旋转操作次数通常比 AVL 树少。

6.3、总结

AVL 树是一种自平衡的二叉搜索树，它通过在每次插入和删除节点时自动调整自身结构，确保树的高度始终保持在 O(log⁡n) 级别，从而提供高效的查找、插入和删除操作。AVL 树的核心优势在于其严格的平衡性，这使得它在查找操作中具有较高的性能，并且在最坏情况下也能保持较优的时间复杂度。

然而，这种严格的平衡性也带来了更高的实现复杂性和插入、删除操作的额外开销。在需要频繁插入和删除的应用场景中，AVL 树的性能可能不如红黑树等其他自平衡树。此外，AVL 树的每个节点需要额外存储平衡因子，略微增加了内存开销。

尽管如此，AVL 树在追求高效查找操作的场景中仍然是一个非常实用的数据结构。它适用于需要快速数据访问、并且插入和删除操作相对较少的场景，如字典、集合等。在实际应用中，应根据具体的需求和场景，综合考虑选择适合的自平衡二叉树结构。

通过本博客对 AVL 树的全面阐述，希望能够帮助读者更好地理解和运用 AVL 树，并在实际开发中合理选择和实现这一数据结构。

希望这篇博客对您有所帮助，也欢迎您在此基础上进行更多的探索和改进。如果您有任何问题或建议，欢迎在评论区留言，我们可以共同探讨和学习。更多知识分享可以访问我的个人博客网站 ： https://blog.lenyiin.com/ 。本博客所涉及的代码也可以访问我的 git 仓库获取 ：https://git.lenyiin.com/Lenyiin/AVLTree