AVL 树的实现与应用

2024-08-28 14:44
文章标签 实现 应用 avl

本文主要是介绍AVL 树的实现与应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  1. 引言
  2. AVL 树简介
  3. AVL 树的性质
  4. AVL 树的旋转
    • 右单旋 (RR)
    • 左单旋 (LL)
    • 右左双旋 (RL)
    • 左右双旋 (LR)
  5. AVL 树的实现
    • AVL 树节点
    • AVL 树类
      • 插入
      • 删除
      • 旋转
      • 验证
  6. 代码示例
  7. 性能考量
  8. 总结
  9. 参考文献

引言

在计算机科学中，AVL 树是一种自平衡的二叉搜索树。它由 Adelson-Velsky 和 Landis 在 1962 年提出，以他们的名字首字母命名。AVL 树通过维持每个节点的平衡因子（即左右子树的高度差）在 [-1, 0, 1] 的范围内，来确保树的高度始终保持在对数级别。这使得 AVL 树非常适合那些需要频繁执行查找、插入和删除操作的应用场景。

本文将详细介绍 AVL 树的原理、实现细节以及一些实际的应用案例。

AVL 树简介

AVL 树是一种特殊的二叉搜索树，其中每个节点的两个子树的高度差至多为 1。这意味着 AVL 树在最坏的情况下也能保持良好的性能，其查找、插入和删除操作的时间复杂度均为 O(log N)。

AVL 树的性质

AVL 树具有以下性质：

  1. 平衡因子: 每个节点都有一个平衡因子，表示左右子树的高度差。
  2. 高度: AVL 树的高度始终保持在对数级别，这保证了高效的查找、插入和删除操作。
  3. 平衡性: 每个节点的两个子树的高度差至多为 1。

AVL 树的旋转

为了保持 AVL 树的平衡性，当插入或删除操作可能导致树失去平衡时，需要通过旋转操作来调整树的结构。AVL 树的旋转主要包括四种类型：

右单旋 (RR)

当一个节点的左子树的高度大于右子树的高度，并且左子树的左子树的高度又大于或等于其右子树的高度时，需要进行右单旋。

左单旋 (LL)

当一个节点的右子树的高度大于左子树的高度，并且右子树的右子树的高度又大于或等于其左子树的高度时，需要进行左单旋。

右左双旋 (RL)

当一个节点的左子树的高度大于右子树的高度，并且左子树的右子树的高度大于其左子树的高度时，需要先对该节点的左子树进行左单旋，然后对该节点进行右单旋。

左右双旋 (LR)

当一个节点的右子树的高度大于左子树的高度，并且右子树的左子树的高度大于其右子树的高度时，需要先对该节点的右子树进行右单旋，然后对该节点进行左单旋。

AVL 树的实现

接下来，我们将使用 C++ 来实现一个简单的 AVL 树。

AVL 树节点

首先定义 AVL 树的节点结构。

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;int _bf;   // 节点的平衡因子
};

AVL 树类

定义 AVL 树类，包含插入、删除、旋转等方法。

插入
template<class T>
bool AVLTree<T>::Insert(const T& data)
{// 省略插入逻辑...
}
删除
template<class T>
bool AVLTree<T>::Remove(const T& data)
{// 省略删除逻辑...
}
旋转

实现四种旋转操作。

template<class T>
void AVLTree<T>::RotateR(AVLTreeNode<T>* pParent)
{// 省略右单旋逻辑...
}template<class T>
void AVLTree<T>::RotateL(AVLTreeNode<T>* pParent)
{// 省略左单旋逻辑...
}template<class T>
void AVLTree<T>::RotateRL(AVLTreeNode<T>* pParent)
{// 省略右左双旋逻辑...
}template<class T>
void AVLTree<T>::RotateLR(AVLTreeNode<T>* pParent)
{// 省略左右双旋逻辑...
}
验证

验证 AVL 树的平衡性。

template<class T>
bool AVLTree<T>::IsAVLTree()
{return _IsAVLTree(_pRoot);
}template<class T>
bool AVLTree<T>::_IsAVLTree(AVLTreeNode<T>* pRoot)
{// 省略验证逻辑...
}

代码示例

下面是完整的 AVL 树实现示例。

#include <cassert>
#include <iostream>// 定义 AVL 树的节点结构
template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}// 指向左子节点的指针AVLTreeNode<T>* _pLeft;// 指向右子节点的指针AVLTreeNode<T>* _pRight;// 指向父节点的指针AVLTreeNode<T>* _pParent;// 存储的数据T _data;// 节点的平衡因子，表示左右子树的高度差int _bf;
};// 定义 AVL 树类
template<class T>
class AVLTree
{typedef AVLTreeNode<T> Node;
public:AVLTree(): _pRoot(nullptr){}// 在 AVL 树中插入值为 data 的节点bool Insert(const T& data);// 从 AVL 树中删除值为 data 的节点bool Remove(const T& data);// 验证 AVL 树是否平衡bool IsAVLTree(){return _IsAVLTree(_pRoot);}private:// 验证给定节点是否构成有效的 AVL 树bool _IsAVLTree(Node* pRoot);// 计算节点的高度size_t _Height(Node* pRoot);// 右单旋void RotateR(Node* pParent);// 左单旋void RotateL(Node* pParent);// 右左双旋void RotateRL(Node* pParent);// 左右双旋void RotateLR(Node* pParent);private:// AVL 树的根节点Node* _pRoot;
};// 实现插入操作
template<class T>
bool AVLTree<T>::Insert(const T& data)
{// 如果树为空，创建一个新的根节点if (_pRoot == nullptr){_pRoot = new Node(data);return true;}// 寻找插入位置Node* parent = nullptr;Node* current = _pRoot;while (current != nullptr){parent = current;if (data < current->_data){current = current->_pLeft;}else{current = current->_pRight;}}// 创建新节点Node* newNode = new Node(data);newNode->_pParent = parent;// 根据数据大小决定插入到左子树还是右子树if (data < parent->_data){parent->_pLeft = newNode;}else{parent->_pRight = newNode;}// 更新平衡因子while (parent != nullptr){// 计算左右子树的高度size_t leftHeight = _Height(parent->_pLeft);size_t rightHeight = _Height(parent->_pRight);// 设置平衡因子parent->_bf = static_cast<int>(rightHeight - leftHeight);// 如果不平衡，则进行旋转if (parent->_bf > 1 || parent->_bf < -1){// 判断需要哪种类型的旋转if (parent->_pLeft != nullptr && parent->_pLeft->_bf == 1){RotateL(parent->_pParent); // 左单旋}else if (parent->_pRight != nullptr && parent->_pRight->_bf == -1){RotateR(parent->_pParent); // 右单旋}else if (parent->_pLeft != nullptr && parent->_pLeft->_bf == -1){RotateLR(parent->_pParent); // 左右双旋}else if (parent->_pRight != nullptr && parent->_pRight->_bf == 1){RotateRL(parent->_pParent); // 右左双旋}break;}// 继续向上更新平衡因子parent = parent->_pParent;}return true;
}// 实现删除操作
template<class T>
bool AVLTree<T>::Remove(const T& data)
{// 删除逻辑省略...// ...// ...
}// 实现右单旋
template<class T>
void AVLTree<T>::RotateR(Node* pParent)
{assert(pParent->_pLeft != nullptr); // 确保父节点有左子节点// 获取父节点的左子节点Node* pChild = pParent->_pLeft;// 将父节点的左子节点设置为左子节点的右子节点pParent->_pLeft = pChild->_pRight;// 如果父节点的左子节点不为空，更新其父节点if (pParent->_pLeft != nullptr){pParent->_pLeft->_pParent = pParent;}// 将左子节点的右子节点设置为父节点pChild->_pRight = pParent;// 更新父节点的父节点pParent->_pParent = pChild;// 更新父节点的父节点指向if (pParent == _pRoot){_pRoot = pChild;}else if (pParent->_pParent->_pLeft == pParent){pParent->_pParent->_pLeft = pChild;}else{pParent->_pParent->_pRight = pChild;}// 更新左子节点的父节点指向pChild->_pParent = pParent->_pParent;
}// 实现左单旋
template<class T>
void AVLTree<T>::RotateL(Node* pParent)
{assert(pParent->_pRight != nullptr); // 确保父节点有右子节点// 获取父节点的右子节点Node* pChild = pParent->_pRight;// 将父节点的右子节点设置为右子节点的左子节点pParent->_pRight = pChild->_pLeft;// 如果父节点的右子节点不为空，更新其父节点if (pParent->_pRight != nullptr){pParent->_pRight->_pParent = pParent;}// 将右子节点的左子节点设置为父节点pChild->_pLeft = pParent;// 更新父节点的父节点pParent->_pParent = pChild;// 更新父节点的父节点指向if (pParent == _pRoot){_pRoot = pChild;}else if (pParent->_pParent->_pLeft == pParent){pParent->_pParent->_pLeft = pChild;}else{pParent->_pParent->_pRight = pChild;}// 更新右子节点的父节点指向pChild->_pParent = pParent->_pParent;
}// 实现右左双旋
template<class T>
void AVLTree<T>::RotateRL(Node* pParent)
{RotateR(pParent->_pLeft); // 先对父节点的左子节点进行右单旋RotateL(pParent);         // 再对父节点进行左单旋
}// 实现左右双旋
template<class T>
void AVLTree<T>::RotateLR(Node* pParent)
{RotateL(pParent->_pRight); // 先对父节点的右子节点进行左单旋RotateR(pParent);          // 再对父节点进行右单旋
}// 验证给定节点是否构成有效的 AVL 树
template<class T>
bool AVLTree<T>::_IsAVLTree(Node* pRoot)
{// 如果树为空，则它是平衡的if (pRoot == nullptr){return true;}// 验证左右子树是否为 AVL 树if (!_IsAVLTree(pRoot->_pLeft) || !_IsAVLTree(pRoot->_pRight)){return false;}// 计算左右子树的高度size_t leftHeight = _Height(pRoot->_pLeft);size_t rightHeight = _Height(pRoot->_pRight);// 检查当前节点的平衡因子是否有效if (abs(static_cast<int>(rightHeight - leftHeight)) > 1){return false;}return true;
}// 计算节点的高度
template<class T>
size_t AVLTree<T>::_Height(Node* pRoot)
{// 如果节点为空，则高度为 0if (pRoot == nullptr){return 0;}// 递归计算左右子树的高度size_t leftHeight = _Height(pRoot->_pLeft);size_t rightHeight = _Height(pRoot->_pRight);// 返回较大的高度值加 1return 1 + std::max(leftHeight, rightHeight);
}// 主函数
int main()
{AVLTree<int> avlTree;avlTree.Insert(10);avlTree.Insert(20);avlTree.Insert(30);avlTree.Insert(40);avlTree.Insert(50);avlTree.Insert(25);std::cout << "AVL Tree is balanced: " << avlTree.IsAVLTree() << std::endl;return 0;
}

性能考量

AVL 树的主要优势在于其高度始终保持在对数级别，这保证了高效的查找、插入和删除操作。然而，AVL 树在进行旋转操作时可能会带来一定的开销。对于频繁插入和删除操作的应用场景，AVL 树可能不是最佳选择，因为每次插入或删除操作后都需要进行旋转来维持平衡。

总结

本文介绍了 AVL 树的基本概念、性质、旋转操作以及在 C++ 中的实现。AVL 树是一种自平衡的二叉搜索树，适用于需要高效查找、插入和删除操作的应用场景。通过本文的学习，读者应该能够理解 AVL 树的工作原理，并能够在实际项目中运用它。

这篇关于AVL 树的实现与应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1115062。

相关文章

中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
zoj3820(树的直径的应用)

zoj3820(树的直径的应用)

题意：在一颗树上找两个点，使得所有点到选择与其更近的一个点的距离的最大值最小。 思路：如果是选择一个点的话，那么点就是直径的中点。现在考虑两个点的情况，先求树的直径，再把直径最中间的边去掉，再求剩下的两个子树中直径的中点。 代码如下： #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2