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

废旧电脑做网站服务器谷歌广告联盟

废旧电脑做网站服务器,谷歌广告联盟,网站风格 颜色搭配,南京模板做网站引子: 在此之前,我们学过了搜索二叉树,这种树,在如果数据有序或接近有序的情况下,二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下,而且普通搜索二叉树无法有…

引子:

在此之前,我们学过了搜索二叉树,这种树,在如果数据有序或接近有序的情况下,二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下,而且普通搜索二叉树无法有重复的元素,对此,我们提出了平衡二叉树,avl树就是比较基础的,一种基于搜索二叉树的改进树,引入了平衡因子与旋转的概念!avl树是由两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种方法。

什么是avl树?

AVL树是一种自平衡的二叉搜索树,它的名字来源于它的发明者Adelson-Velsky和Landis。AVL树的特点是任何节点的两个子树的高度(或深度)最大差异为1。这种平衡特性确保了树的查找、插入和删除操作都能在对数时间内完成,即时间复杂度为O(log n)。当向二叉搜索树中插入新结点后,如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均 搜索长度。

一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:

1,它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

2,如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O(log_2n),搜索时间复杂度O(log_2n)。

avl树的实现

如何实现avl树呢,我们要从图入手,并一步一步实现avl树代码的实现!

我们可以先换一侧树的全部情况,先写出“一半代码”,然后仿照着写就可以了。

一,先试着画出一半的图,思考如何写?以下是一个示范图

图一:

图二:

图三:

二,导入库

#include<iostream>
#include<assert.h>
using namespace std;

三,创建节点

//创建节点
template<class K,class V>
class avlTreeNode
{
public:avlTreeNode* _left;//左节点avlTreeNode* _right;//右节点avlTreeNode* _parent;//上级节点int _bf;//平衡因子pair<K, V>_kv;//kv的值;avlTreeNode(const pair<K,V>&kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_kv(kv){}
};

四,整体框架;

template<class K,class V>
class avlTree
{typedef avlTreeNode<K,V> Node;
public://构造函数avlTree() = default;//拷贝构造函数,树形节点要一个一个拷贝avlTree(const avlTree<K, V>& h){_root = copy(h._root);}//find K值Node* Find( const K& key){Node* cur = _root;while (cur){if (cur->_left->_kv.first < key){cur = cur->_right;}else if (cur->_left->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}//find V值Node* Find(const V& key){Node* cur = _root;while (cur){if (cur->_left->_kv.second < key){cur = cur->_right;}else if (cur->_left->_kv.second > key){cur = cur->_left;}else{return cur;}}return nullptr;}//中序有序,避免了_root是内部private的加密void _InOrder(){_InOrder(_root);cout << endl;}//insertbool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}//要先找到,插入位置Node* parent = nullptr;Node* current = _root;while (current){if (current->_kv.first < kv.first){parent = current;current = current->_right;}else if (current->_kv.first > kv.first){parent = current;current = current->_left;}else{return false;}}//新增节点再链接上去current = new Node(kv);if (kv.first > (parent->_kv.first)){parent->_right = current;}else if (kv.first < (parent->_kv.first)){parent->_left = current;}return true;current->_parent = parent;//更新平衡因子,新节点插入后,AVL树的平衡性可能会遭到破坏,此时就需要更新平衡因子,并检测是否//破坏了AVL树while (current){//左插--,右插++if (current == parent->_left){parent->_bf--;}else if (current == parent->_right){parent->_bf++;}if (parent->_bf == 0){//高度不变,达到最理想状态break;}else if (parent->_bf == -1 || parent->_bf == 1){//向上更新current = parent;parent = parent->_parent;}else if(parent->_bf == 2 || parent->_bf == -2)//不平衡情况{if (parent->_bf == 2 && current->_bf == 1)//左旋RotateL(parent);else if (parent->_bf == -2 && current->_bf == -1)//右旋RotateR(parent);else if (parent->_bf == 2 && current->_bf ==-1)//左右旋RotateRL(parent);else  //(parent->_bf == -2 && current->_bf == 1)RotateLR(parent);}elseassert(false);}return true;}//因为AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不//错与删除不同的时,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。//重载=avlTree<K, V>& operator=(const avlTree<K, V>& h){swap(_root, h._root);return *this;}//析构函数,注意开辟了空间后,对于树形结构的节点要一个一个删除~avlTree(){Destory(_root);_root = nullptr;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}

五,private部分

private://计算有效的节点int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}//计算树的高度,利用递归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 _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root) return true;//严格检验int TreeHeight_L = _Height(root->_left);int TreeHeight_R = _Height(root->_right);//我们默认的是右到左int diff = TreeHeight_R - TreeHeight_L;//高度与平衡因子的数值不匹配if (diff != root->_bf || (diff > 1 || diff < -1))return false;return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}//左根右;_InOrder(root->_left);cout << root->_kv.first << " :" << root->_kv.second << " ";_InOrder(root->_right);}void RotateL( Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;Node* parent_parent = parent->_parent;if (parent_parent == nullptr){_root = subR;parent_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subR;}else if (parent_parent->_right == parent){parent_parent->_right = subR;}subR->_parent = parent_parent;}subR->_bf = parent->_bf = 0;}void RotateR( Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;Node* parent_parent = parent->_parent;if (parent_parent == nullptr){_root = subL;parent_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subL;}else if (parent_parent->_right == parent){parent_parent->_right = subL;}subL->_parent = parent_parent;}subL->_bf = parent->_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 == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf =0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else{assert(false);}}//销毁void Destory(Node* root){if (root==nullptr){return;}Destory(root->_left);Destory(root->_right);Destory(root->_parent);delete root;}//拷贝Node* copy(const Node*& root){if (root == nullptr){return nullptr;}Node* temp = new Node(root->_kv);temp->_left=copy(root->_left);temp->_right=copy(root->_right);temp->_parent=copy(root->_parent);return temp;}Node* _root = nullptr;
};

六:说明,对于erase部分先不做处理啦!

七,AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这 样可以保证查询时高效的时间复杂度,即log_2 (N)。但是如果要对AVL树做一些结构修改的操 作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时, 有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数 据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。


ok,感谢大家的观看,有
问题可以发评论区(微笑!)

http://www.fp688.cn/news/165024.html

相关文章:

  • 物业网站建设武汉网站设计公司
  • 网站建设需要实现哪些目标优化seo公司哪家好
  • 佛山网站搭建公司网络推广关键词优化公司
  • 怎么搭建自己的网站卖货企业网络营销推广方法
  • 网站开发类毕业论文范例株洲seo
  • 网站在布局专业黑帽seo
  • 滨湖网站制作点点站长工具
  • 昭通市有做网站的吗排名优化seo公司
  • b2c网站结构分析安卓aso优化
  • 河北网站建设公司排名地推
  • 山东住房和城乡建设部网站首页石家庄整站优化技术
  • 科技开发公司长沙seo外包
  • 太原市建设局网站页面seo是什么意思
  • 男子替人做赌博网站百度帐号申请注册
  • 徐州网站建设托管百度热搜榜历史
  • 网站开发典型b站推广软件
  • 国外做机器的好的网站域名信息查询网站
  • 微微网站建设代码优化
  • 门户网网站seo怎么做站长工具中文
  • 通用网址通用网站查询网上培训课程平台
  • 网站开发php和ui谷歌浏览器 安卓下载2023版
  • 网站内容不显示不出来品牌推广策略分析
  • 做网站好的网站建设公司排名品牌网络推广
  • 百度企业查系统优化大师官方下载
  • 网站怎么做竞价百度 站长工具
  • 淘宝网店代运营哪家好整站seo优化
  • 用illustrator做网站点击器
  • wordpress主题带支付电商seo是指
  • 迁安建设局网站百度指数的数据来源
  • 江西做企业网站的公司百度百家号注册