摘要

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

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


1、引言

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


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


在这些自平衡树中,AVL 树是最早被发明的一种。它由 Adelson-VelskyLandis 于 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 的左子节点。

示例图

插入导致的结构:

  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



09-20 01:53