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

标签：Node bf cur parent C++ AVL 修炼 root 节点

摘要

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

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

1、引言

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

关于二叉搜索树的更多细节请见我的这篇博客：《 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 树中每个节点的平衡因子是该节点右子树的高度减去左子树的高度，即：

B F ( n o d e ) = h e i g h t ( r i g h t s u b t r e e ) − h e i g h t ( l e f t s u b t r e e ) BF(node)=height(right subtree)−height(left subtree) 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 factor
    std::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 的左子节点。

示例图：

插入导致的结构：

单左旋后的结构：

    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、左右双旋

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

旋转过程：

左旋：对左子节点 B 进行单左旋，使得 B 的右子节点 C 成为新的根节点。
右旋：对不平衡节点 A 进行单右旋，使得 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、右左双旋

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

旋转过程：

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

示例图：

插入导致的结构：

  A
   \
    B
   /
  C

右旋后的中间结构：

左旋后的最终结构：

    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 树的删除操作可以分为以下几个步骤：

找到并删除节点：和普通的二叉搜索树（BST）删除操作类似。
调整平衡因子：从删除的节点开始，沿着路径向上调整每个节点的平衡因子。
执行旋转操作：在调整平衡因子的过程中，如果发现某个节点失衡（平衡因子的绝对值大于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、查找操作的步骤

从根节点开始：从AVL树的根节点开始查找。
比较当前节点的键值：
- 如果查找的键等于当前节点的键，查找成功，返回当前节点。
- 如果查找的键小于当前节点的键，进入左子树继续查找。
- 如果查找的键大于当前节点的键，进入右子树继续查找。
递归或迭代：重复上述步骤，直到找到匹配的节点或者子树为空（查找失败）。
返回结果：找到目标节点则返回，否则返回 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、优点

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

6.2、缺点

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

标签：Node,bf,cur,parent,C++,AVL,修炼,root,节点
From： https://blog.csdn.net/mmlhbjk/article/details/142290626

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

摘要

1、引言

2、AVL树概述

2.1、平衡因子

2.2、旋转操作

2.3、AVL树的应用场景

2.4、本文的结构

3、AVL 树的实现

3.1、AVL树节点结构

3.2、插入操作

3.3、旋转操作

3.3.1、左单旋

3.3.2、右单旋

3.3.3、左右双旋

3.3.4、右左双旋

3.3.5、旋转操作总结

3.4、删除操作

3.4.1、找到并删除节点

3.4.2、调整平衡因子

3.4.3、执行旋转操作

3.4.4、总结

3.5、遍历操作

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

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

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

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

3.5.5、总结

3.6、查找操作

3.6.1、查找操作的步骤

3.6.2、查找的递归实现

3.6.3、查找的非递归实现

4、AVL 树的其他功能

4.1、查找后继节点

4.2、查找前驱节点

4.3、获取树的高度

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

5、完整实现代码和测试

5.1、AVLTree.hpp

5.2、AVLTree.cpp

6、AVL树的优缺点和总结

6.1、优点

6.2、缺点

6.3、总结

相关文章

赞助商

阅读排行

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