手机网站开发基础,温州做网站公司哪家好,温州做网站的公司,php网站建设网站前言
大家好#xff0c;我是jiantaoyab#xff0c;本篇文章给大家介绍AVL树。
基本概念
AVL树#xff08;Adelson-Velsky和Landis树#xff09;是一种自平衡的二叉搜索树#xff0c;得名于其发明者G. M. Adelson-Velsky和E. M. Landis。在AVL树中#xff0c;任何节点的…前言
大家好我是jiantaoyab本篇文章给大家介绍AVL树。
基本概念
AVL树Adelson-Velsky和Landis树是一种自平衡的二叉搜索树得名于其发明者G. M. Adelson-Velsky和E. M. Landis。在AVL树中任何节点的两个子树的高度最大差别为1因此它也被称为高度平衡树。
AVL树特点
二叉搜索树性质AVL树本质上是一棵二叉搜索树即每个节点的左子树中的所有节点的值都小于该节点的值而右子树中的所有节点的值都大于该节点的值。平衡条件AVL树的每个节点的左子树和右子树的高度差之绝对值不超过1。这是AVL树与其他二叉搜索树的主要区别保证了树的平衡性从而优化了查找、插入和删除操作的性能。平衡因子每个节点都有一个平衡因子定义为该节点的右子树高度减去左子树高度。在AVL树中平衡因子的取值只能是-1、0或1。
模拟实现
AVL树节点定义
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V *_left;AVLTreeNodeK, V *_right;AVLTreeNodeK, V *_parent;pairK,V _kv; //pair是将2个数据组合成一组数据int _bf; //balance factorAVLTreeNode(const pairK, Vkv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}};插入操作
bool Insert(const pairK, Vkv){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.firstkv.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;}//控制平衡//1、更新平衡因子 //2、异常旋转平衡处理//只会影响这条路径最坏更新到根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;}//旋转处理 //1树平衡了//2:树的整体高度降了1else if (parent-_bf 2 || parent-_bf -2){//右单旋if (parent-_bf -2 cur-_bf -1){RotateR(parent);}//左单旋else if (parent-_bf 2 cur-_bf 1){RotateL(parent);}//双旋左右else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}//双旋右左else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else{assert(false);}//旋转完之后不影响上面的可以直接退出break; }//插入之前平衡因子有问题else{assert(false);}}return true;
}旋转操作
右单旋 //右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;subL-_right parent;//更新父节点if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;parent-_parent subL;//如果原来是根if (parent _root){_root subL;_root-_parent nullptr;}//如果是别人的子树else{if (parentParent-_left parent)parentParent-_left subL;elseparentParent-_right subL;subL-_parent parentParent;}subL-_bf parent-_bf 0;}左单旋
void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}Node* parentParent parent-_parent;subR-_left parent;parent-_parent subR;//原来是根if (_root parent){_root subR;subR-_parent nullptr;}//原来是别人的子树else{if (parentParent-_left parent)parentParent-_left subR;elseparentParent-_right subR;subR-_parent parentParent;}subR-_bf parent-_bf 0;}
左右双旋 void RotateLR(Node *parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1){parent-_bf 1;subL-_bf 0;}else if (bf 1){parent-_bf 0;subL-_bf -1;}else{parent-_bf subL-_bf 0;}subLR-_bf 0;}右左双旋
void RotateRL(Node *parent) {// 30 (parent)// / \// a 90(subR)// / \ // 60(subRL) d// b cNode *subR parent-_right;Node *subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);//这里看图 变化后的图if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf -1){parent-_bf 0;subR-_bf 1; subRL-_bf 0;}else if (bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else{assert(false);}}判断是不是AVL树
int Height(Node *root){if (root NULL)return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool IsBalance(){return _IsBalance(_root);}//1.检查是不是搜索二叉树//2.检查每一课子树是不是AVL树bool _IsBalance(Node *root){if (root NULL)return true;//当前树检查int leftHeight Height(root-_left);int rightHeight Height(root-_right);//平衡因子出问题if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first NOW:: root-_bf endl;cout root-_kv.first CORRECT:: rightHeight - leftHeight endl;return false;}//左右高度差不能超过2return abs(rightHeight - leftHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);}
AVL树性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即O(log n)。
但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。
因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
AVL树使用场景
数据库和文件系统的索引 数据库系统经常需要快速检索、插入和删除记录。AVL树作为索引结构可以加速这些操作确保查询效率不会因为数据的不均匀分布而降低。 内存数据库 对于需要快速响应的内存数据库如Redis使用AVL树可以确保数据访问的高效性。 字典或词汇查找 在自然语言处理或文本编辑器中实现自动补全、拼写检查或同义词查找等功能时AVL树可以提供快速的词汇查找和插入。 路由表查找 在计算机网络中路由器需要根据路由表快速查找最佳路径。AVL树可以确保路由查找的高效性。 搜索引擎 搜索引擎在处理大量网页索引时需要快速检索和更新索引。AVL树可以帮助优化这些操作。 缓存系统 在实现缓存替换策略如LRU即最近最少使用策略时AVL树可以帮助维护一个有序的缓存项列表从而快速确定哪些项应该被替换。 事件处理系统 在需要按时间顺序处理事件的系统如日历应用或任务调度器中AVL树可以用于维护一个有序的事件列表。 科学计算和模拟 在科学计算和模拟中经常需要快速查找、插入或删除数据点。AVL树可以提供一个高效的数据结构来支持这些操作。 金融交易系统 实现自动补全、拼写检查或同义词查找等功能时AVL树可以提供快速的词汇查找和插入。
