当前位置： 首页 > news >正文

互联网App网站建设方案学校网站的系统建设方式

news 2025/9/16 6:39:50
互联网App网站建设方案,学校网站的系统建设方式,宁波网上办事大厅,杭州网站优化流程二叉搜索树：【C进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客 目录 一、AVL树的概念 二、AVL树的原理与实现 AVL树的节点 AVL树的插入 AVL树的旋转 AVL树的打印 AVL树的检查 三、实现AVL树的完整代码 四、总结 前言&#xff1a…

二叉搜索树：【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客

目录

一、AVL树的概念

二、AVL树的原理与实现

AVL树的节点

AVL树的插入

AVL树的旋转

AVL树的打印

AVL树的检查

三、实现AVL树的完整代码

四、总结

前言：

在前面我们学习二叉搜索树的时候，虽然大部分情况下二叉搜索树的效率都是很高的，但是如果是一组相对有序的数字，我们用二叉搜索树来排序就会显得比较麻烦了，因此，AVL树就出现了，下面就让我们一起来学习以下AVL树的相关知识

一、AVL树的概念

AVL树实际上就是特殊的二叉搜索树，是对二叉搜索树的改进，我们在用树形结构来查找或操作数据的时候，一般都是要从树根一层一层往下找，所以树高越低，效率越高，但是二叉搜索树在有些场景下比较麻烦，比如一个相对有序的数组{2，1，3，4，5，6}

这样一个数组如果通过二叉搜索树处理就会显得层数太多，效率很低

所以人们也就有了这样一种思考：我们可不可以通过某种操作让左右子树的高度差不超过1，这样就能极大的提高效率，这就是AVL树的概念

AVL树中任何节点的左右子树的高度差（平衡因子）绝对值不超过1。这意味着树始终保持平衡，避免了二叉搜索树在节点插入或删除后可能出现的退化现象。

二、AVL树的原理与实现

了解了AVL树的基本内容之后，接下来我们就来一步一步学习以下AVL树的原理到底是什么以及如何实现一个AVL树：

AVL树的节点

template<class K,class V>   
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;    //左子树AVLTreeNode<K, V>* _right;   //右子树AVLTreeNode<K, V>* _parent;  //父亲pair<K, V> _kv;       //存放节点值的int _bf;    //平衡因子（通过这个可以直到左右子树存在情况）//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0)     //平衡因子起始值是0，当左子树插入一个节点时-1，右子树插入一个节点时+1{}
};

AVL树的节点操作与二叉搜索树还是比较相似的，都有左子树右子树和父亲节点的叉式结构，比较不同的是加入了一个平衡因子

AVL树的插入

实现AVL树的重点就是解决AVL树的插入问题，而解决插入问题最关键的就是要做到如何让左右子树高度的绝对值适合不大于1，我们是通过合理的旋转来实现的，而且需要旋转的情况也是分为四种的：

RR型：左旋

LL型：右旋

RL型：先右旋，再左旋

LR型：先左旋，再右旋

下面我们来看这样几个例子：

1、RR型（左旋）

2、LL型（右旋）

3、LR型（先左旋，再右旋）

4、RL型（先右旋，再左旋）

操作与3正好相反，不过多赘述

下面就让我们看一下插入的代码：

	bool Insert(const pair<K,V>& kv)    //插入节点{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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//管控平衡while (parent)    //当为根时，停止{if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2) //旋转{if (parent->_bf == 2&&cur->_bf==1){//左单旋RotateL(parent);break;}else if (parent->_bf == -2 && cur->_bf == -1){//右单旋RotateR(parent);break;}else if (parent->_bf == 2 && cur->_bf == -1){//RL型RotateRL(parent);break;}else if (parent->_bf == -2 && cur->_bf == 1){//LR型RotateLR(parent);break;}}else{assert(false);}}return true;}

AVL树的旋转

	void RotateL(Node* parent)   //左单旋（RR型）{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;subR->_left = parent;if(subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_parent = subR;parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent)   //右单旋（LL型）{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;parent->_left = subLR;subL->_right = parent;if (subLR){subLR->_parent = parent;}if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_parent = subL;subL->_bf = parent->_bf = 0;}void RotateRL(Node* parent)      //先右单旋，再左单旋（RL型）{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){//subRL自己就是新增点parent->_bf = subR->_bf = 0;}else if (bf == -1){//subRL的左子树上新增parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){//subRL的右子树上新增parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent)      //先左单旋，再右单旋（LR型）{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){//subLR自己就是新增点parent->_bf = subL->_bf = 0;}else if (bf == -1){//subLR的左子树上新增parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){//subLR的右子树上新增parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}}

AVL树的打印

AVL树的打印与二叉搜索树一致，都是中序打印，我们就直接来看代码了

	//中序打印void Inorder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}

AVL树的检查

检查是否为AVL树，一方面我们可以通过打印的结果先来判断一下它是不是二叉搜索树，然后我们可以通过比较左右子树的高度差来判断它是否为AVL树（根据前面可知AVL树左右子树高度差最大为1）

	//检查是否为AVL树bool IsBalance(){return _IsBalance(_root);}int _High(Node* root){if (root == nullptr)return 0;int LeftHigh = _High(root->_left);int RightHigh = _High(root->_right);return LeftHigh > RightHigh ? LeftHigh + 1 : RightHigh + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int LeftHigh = _High(root->_left);int RightHigh = _High(root->_right);if (RightHigh - LeftHigh != root->_bf){cout << _root->_kv.first << "当前节点平衡因子有问题" << endl;return false;}return abs(LeftHigh- RightHigh) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}

三、实现AVL树的完整代码

AVLTree.h

template<class K,class V>   
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;    //左子树AVLTreeNode<K, V>* _right;   //右子树AVLTreeNode<K, V>* _parent;  //父亲pair<K, V> _kv;       //存放节点值的int _bf;    //平衡因子（通过这个可以直到左右子树存在情况）//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0)     //平衡因子起始值是0，当左子树插入一个节点时-1，右子树插入一个节点时+1{}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K,V>& kv)    //插入节点{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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//管控平衡while (parent)    //当为根时，停止{if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2) //旋转{if (parent->_bf == 2&&cur->_bf==1){//左单旋RotateL(parent);break;}else if (parent->_bf == -2 && cur->_bf == -1){//右单旋RotateR(parent);break;}else if (parent->_bf == 2 && cur->_bf == -1){//RL型RotateRL(parent);break;}else if (parent->_bf == -2 && cur->_bf == 1){//LR型RotateLR(parent);break;}}else{assert(false);}}return true;}void RotateL(Node* parent)   //左单旋（RR型）{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;subR->_left = parent;if(subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_parent = subR;parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent)   //右单旋（LL型）{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;parent->_left = subLR;subL->_right = parent;if (subLR){subLR->_parent = parent;}if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_parent = subL;subL->_bf = parent->_bf = 0;}void RotateRL(Node* parent)      //先右单旋，再左单旋（RL型）{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){//subRL自己就是新增点parent->_bf = subR->_bf = 0;}else if (bf == -1){//subRL的左子树上新增parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){//subRL的右子树上新增parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent)      //先左单旋，再右单旋（LR型）{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){//subLR自己就是新增点parent->_bf = subL->_bf = 0;}else if (bf == -1){//subLR的左子树上新增parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){//subLR的右子树上新增parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}}//中序打印void Inorder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}//检查是否为AVL树bool IsBalance(){return _IsBalance(_root);}int _High(Node* root){if (root == nullptr)return 0;int LeftHigh = _High(root->_left);int RightHigh = _High(root->_right);return LeftHigh > RightHigh ? LeftHigh + 1 : RightHigh + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int LeftHigh = _High(root->_left);int RightHigh = _High(root->_right);if (RightHigh - LeftHigh != root->_bf){cout << _root->_kv.first << "当前节点平衡因子有问题" << endl;return false;}return abs(LeftHigh- RightHigh) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}
private:Node* _root = nullptr;
};

test.c

//AVL树
#include"AVLTree.h"
int main()
{int a[] = { 16,3,7,11,9,26,18,14,15 };   AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.Inorder();cout << "输出1代表是AVL树，输出0代表不是：" << t.IsBalance() << endl;return 0;
}

运行结果：

四、总结

AVL树的理解和实现总体来说还是比较难的，思路一定要搞清楚，代码实现上尽力而为

感谢各位大佬观看，创作不易，还请各位大佬点一个小小的赞！！！

http://www.yayakq.cn/news/136253/

相关文章：

  • 自住房车各项建设部网站青岛百度网站排名优化
  • 做行业网站广告苏州工业园区最新通告
  • 受欢迎的丹阳网站建设云主机租用
  • 天津网站设计与制作wordpress aliyun oss
  • 网站建设需要资质么网站关键词怎么优化排名
  • 徐汇制作网站哪家好成都官网优化多少钱
  • 徐州做网站的公司有哪些WordPress连接微博
  • 网站建设与开发试题英语外贸网站建设
  • 网站建设合作品牌企点
  • 网网站建设公司注册完域名后如何做网站
  • 铁路网站建设论文德州做网站的公司
  • 做seo优化产品网站管理咨询公司起名大气上口的
  • 营销企业网站建设安徽省建设质量安全协会网站
  • 商标设计公司排名前十强网站优化做些什么
  • 如何做网站规划手机网站主页
  • 网站运营seo长安营销服务协同管理平台网站
  • 个人适合建什么网站网站搜索引擎推广
  • 建站程序下载wordpress 的主题修改
  • 网站开发 科技注册公司注册资金最低多少钱
  • 巴中网站建设有限公司网站模板 小说
  • 上海做网站设计的公司360社区app
  • 合肥建设网站公司wordpress标题调用标签
  • 江西网站制作的公司软件开发培训教程
  • 怎么建设可以收费的网站网站一般用什么工具做
  • 哪个公司做网站好网站不让百度收录
  • html5网站特效wordpress 仿站
  • 网站建设网页制作教程wordpress暴力
  • 怎么做自己的购物网站seo排名官网
  • jsp网站开发参考文献仿照别人的网站做违法吗
  • wordpress 常用小工具怎样做seo网站推广