如何做系统集成公司网站,网站的种类,茂名企业网站开发,国外wordpress空间引子#xff1a;
在此之前#xff0c;我们学过了搜索二叉树#xff0c;这种树#xff0c;在如果数据有序或接近有序的情况下#xff0c;二叉搜索树将退化为单支树#xff0c;查找元素相当于在顺序表中搜索元素#xff0c;效率低下#xff0c;而且普通搜索二叉树无法有…引子
在此之前我们学过了搜索二叉树这种树在如果数据有序或接近有序的情况下二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下而且普通搜索二叉树无法有重复的元素对此我们提出了平衡二叉树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树代码的实现
我们可以先换一侧树的全部情况先写出“一半代码”然后仿照着写就可以了。
一先试着画出一半的图思考如何写以下是一个示范图
图一 图二 图三 二导入库
#includeiostream
#includeassert.h
using namespace std;
三创建节点
//创建节点
templateclass K,class V
class avlTreeNode
{
public:avlTreeNode* _left;//左节点avlTreeNode* _right;//右节点avlTreeNode* _parent;//上级节点int _bf;//平衡因子pairK, V_kv;//kv的值avlTreeNode(const pairK,Vkv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_kv(kv){}
};
四整体框架
templateclass K,class V
class avlTree
{typedef avlTreeNodeK,V Node;
public://构造函数avlTree() default;//拷贝构造函数,树形节点要一个一个拷贝avlTree(const avlTreeK, 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 pairK, 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树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不//错与删除不同的时删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。//重载avlTreeK, V operator(const avlTreeK, 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 (rootnullptr){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-_leftcopy(root-_left);temp-_rightcopy(root-_right);temp-_parentcopy(root-_parent);return temp;}Node* _root nullptr;
};
六说明对于erase部分先不做处理啦 七AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即log_2 (N)。但是如果要对AVL树做一些结构修改的操 作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时 有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数 据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
ok感谢大家的观看有问题可以发评论区微笑
