目录前言Part1. AVL树相关成员介绍Part1.1. AVL树节点相关Part1.2. AVL树本体Part2. 四大旋转操作Part2.1. 左单旋Part2.2. 右单旋Part2.3. 左右双旋Part2.4. 右左双旋Part3. 平衡因子作用解析Part3.1. 平衡因子与旋转Part3.2. 平衡因子与向上调整插入Part4. 插入操作Part5. 判断操作Part6. Find接口Part7. 删除操作Part7.1. 平衡因子与向上调整删除Part7.2. 删除的旋转操作Part7.3. 删除的实现Part8. 反思与总结Part9. 代码分享Part9.1. AVL实现Part9.2. 测试Part10. 结语前言前置知识【知识讲解】 二叉搜索树的相关知识与实现-CSDN博客AVL树作为经典的数据结构之一他的有些接口会稍显复杂接下来跟随小编的视角来剖析一下它的全部吧。lets go!!!!!!!!!Part1. AVL树相关成员介绍我们先来看构成AVL树的成员是哪些这方便我们去介绍后续的内容我们来看Part1.1. AVL树节点相关我们先来看代码templateclass k,class v struct AVLTreeNode { std::pairk, v _kv; AVLTreeNodek, v* _left; AVLTreeNodek, v* _right; AVLTreeNodek, v* _parent; int _bf; AVLTreeNode(const std::pairk, v kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) { } };我们来对各个成员详细介绍一下1_kv存储数据的地方key、value。2_left、_right当前节点的左右节点。3_parent当前节点的父亲节点。4_bf平衡因子用于衡量当前节点左右子树的情况_bf当前节点的右子树高度减去其左子树高度插入操作时插到左子树_bf--反之后续调整旋转的核心Part1.2. AVL树本体这个就比较简洁了我们来看代码typedef AVLTreeNodek, v Node; Node* _root nullptr;通过一个_root来统一管理整棵树。Part2. 四大旋转操作虽然这个按道理来说应该放到后面来讲但是把这个单拿出来详细讲解会对后面的的插入删除有很大的帮助毕竟这个就是整个AVL树的核心。四大旋转操作分为左单旋、右单旋、左右双旋、右左双旋我们来分别看看吧Part2.1. 左单旋代码实现void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; subR-_left parent; parent-_right subRL; if (subRL ! nullptr)//当h0的情况 { subRL-_parent parent; } subR-_parent parent-_parent;//记得还要更新_parent if (parent _root) { _root subR; } else { if (parent-_parent-_left parent) { parent-_parent-_left subR; } else { parent-_parent-_right subR; } } parent-_parent subR; parent-_bf 0;//更新平衡因子根据图片上来看 subR-_bf 0; }Part2.2. 右单旋代码实现void RotateR(Node* parent)//逻辑同上 { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; subL-_right parent; if (subLR ! nullptr) { subLR-_parent parent; } subL-_parent parent-_parent; if (parent _root) { _root subL; } else { if (parent-_parent-_left parent) { parent-_parent-_left subL; } else { parent-_parent-_right subL; } } parent-_parent subL; subL-_bf 0; parent-_bf 0; }Part2.3. 左右双旋void RotateLR(Node* parent) { Node* subL parent-_left; int bf subL-_right-_bf; RotateL(subL); RotateR(parent); if (bf 1)//更新平衡因子 //由于上面左旋右旋他对于平衡因子都会置为0 估值要修改不是0的就可以 { subL-_bf -1; } else if (bf -1) { parent-_bf 1; } else if (bf 0) { ; } else { assert(false); } }为什么这里要先采取一个左旋再来右旋呢首先这个场景下是由于左边太‘重’才导致的不平衡因此我们要把左边的节点掰到右边去这样才可以达到平衡但是这个场景又不像上面的右单旋直接右单旋是解决不了问题的。我们可以对比一下两者有什么区别两者的区别就在于右单旋在B这个子树中他的重量是全部都在左边左右单旋这个场景他是重在右边因此我们要先用左单旋把重量先移到左边让这个场景变成适用右单旋的场景再用右单旋解决问题。这里的平衡因子的更新也是充满细节我们来看也就是说新增节点具体在左子树右子树或者自身作为叶子结点的时候平衡因子的更新是有区别的我们可以直接依靠看c结点的_bf来判断是加到哪了从而来更新上面的平衡因子。Part2.4. 右左双旋void RotateRL(Node* parent)//逻辑同上 { Node* subR parent-_right; int bf subR-_left-_bf; RotateR(subR); RotateL(parent); if (bf 1) { parent-_bf -1; } else if (bf -1) { subR-_bf 1; } else if (bf 0) { ; } else { assert(false); } }Part3. 平衡因子作用解析上面我们这么大费周章的修改平衡因子是为了什么他的这个作用又是什么?实际上我们可以只通过两个结点的_bf就可以知道我们用哪种旋转了为什么我们来看Part3.1. 平衡因子与旋转旋转什么时候发生当这个节点不平衡的时候我们具体要对应与哪种旋转呢我们来看1当A处的_bf为2时候说明右边节点高度高则我们在最后一定要右旋但是在那之前具体要左旋来调整还是不要就要具体来看了具体到哪看自然是到右边去看因为是右子树比较重看什么看C处的_bf值如果为1说明新加的节点是在C的右边也就是纯粹的右边重也就是只需要一个整体的右旋就可以解决。反之要是为-1说明新加的是在左边就要先局部左旋将整体调整为右旋的模型在整体右旋解决。2 A处为-2逻辑同上。也就是说我们在遇到不平衡的节点时我们根据他是2还是-2具体在到出问题的那边子树在看那边的_bf值判断调用哪种旋转调整。Part3.2. 平衡因子与向上调整插入当我们A处的_bf不为2、-2时候怎么办什么时候我们要继续向上更新这里更新的依据是什么?旋转后怎么办还要继续向上调整吗针对这些问题我们来看首先我们是否向上调整关键在于我们一系列操作是否改变了树的高度我们来看上面的图我们修改的这个树也是上面的结点的子树当我们调整的这个树高度改变那么在上面看来就是它的一颗左子树与其右子树之间的高度差改变也就是我们要继续向上调整了。那平衡因子是怎么昭示高度改变呢我们来看1调整后_bf为0说明原本其为1/-1即就是原本它的子树有一个高现在相当于加到那个比较矮的子树上了相当于平衡了高度不变不用向上调整。2调整后_bf为1/-1说明原本为0不可能是2/-2不符合AVL树说明之前出问题了0就说明之前是平衡的现在1/-1一边子树高了高度改变要向上调整。为什么在插入操作流程旋转不用继续上向上调整了我们来看我们可以数一数调整前高度为h2调整后也是对于上面四个都是自然不用继续调整。前置知识差不多了我们来看插入和删除吧Part4. 插入操作我们来直接看代码bool insert(const std::pairk, v kv) { if (_root nullptr) { _root new Node(kv); return true; } Node* cur _root; Node* parent nullptr; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else if(cur-_kv.first kv.first) { parent cur; cur cur-_right; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_left cur; } else { parent-_right cur; } cur-_parent parent; //前面这些都是二叉平衡树的插入流程 不熟悉的可以看我前面博客 while (parent)//当parent为nullptr自动退出 { if (cur parent-_left)//根据新加入的节点更新 { parent-_bf--; } else { parent-_bf; } if (parent-_bf 0)//为0不用向上更新 退出 { break; } else if (parent-_bf 1 || parent-_bf -1)//1/-1继续向上更新 { cur parent; parent parent-_parent; } else if(parent-_bf 2 || parent-_bf -2)//根据_bf来决定用什么旋转 { 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; }插入操作就是综合前面的知识来还结合了之前二叉搜索树的插入操作接下来我们来看看其他的接口吧。Part5. 判断操作我们来看代码void IsAVLTree()const { if (_IsAVLTree(_root) -1) { cout NO endl; } else { cout YES endl; } } int _IsAVLTree(Node* root)const//利用后序遍历 从叶子节点往上判断 时间复杂度为ON { if (root nullptr) { return 0; } int left _IsAVLTree(root-_left); int right _IsAVLTree(root-_right); if (left -1 || right -1) { return -1; } if (abs(left - right) 1 || root-_bf ! right - left)//检查左右高度差以及_bf是否满足条件 { return -1; } if (left right) { right left; } return right 1; }Part6. Find接口我们来看代码Node* Find(const k key)//与二叉搜索树一致 { Node* cur _root; while (cur ! nullptr) { if (cur-_kv.second key) { cur cur-_left; } else if (cur-_kv.second key) { cur cur-_right; } else { return cur; } } return nullptr; }Part7. 删除操作删除的逻辑大致上与上面插入相似不过在一些地方还是有所区别我们来看看吧Part7.1. 平衡因子与向上调整删除删除不与插入相似对于相同的平衡因子数值两者的操作会不一样来看看吧1当_bf为0时说明之前的_bf数值为1或者-1也就是说之前会有一棵子树的高度高于另一棵现在删去了多的那一个导致高度改变需要向上调整。2当_bf为1/-1时说明之前为0现在是在两个高度相同的子树中的一个删去了不影响树的整体高度故直接停止向上调整。3当_bf为2/-2时旋转调整这个与插入有很大区别来具体看看吧。Part7.2. 删除的旋转操作当A处的_bf为2C处为1时我们来看旋转的过程由于高度改变了所以在旋转后还要向上调整对于插入的四个情况是这样的但是这里与上面的模型不同b、c的_bf还可以为0我们来看看当其为0的时候是什么情况所以在这种情况下不用向上调整了但要注意调整A、B的_bf。Part7.3. 删除的实现我们来看代码void erase(const k key) { Node* cur Find(key);//找到节点 if (cur nullptr) return; Node* parent cur-_parent; int curn 0;//用这个来标记上次处理是在左子还是右子 if (cur-_left nullptrcur-_right!nullptr)//这些与二叉搜索树相似 { if (cur _root) { _root cur-_right; _root-_parent nullptr; delete cur; return; } if (parent-_left cur) { parent-_left cur-_right; cur-_right-_parent parent; curn -1; } else { parent-_right cur-_right; cur-_right-_parent parent; curn 1; } delete cur; } else if (cur-_left ! nullptr cur-_right nullptr) { if (cur _root) { _root cur-_left; _root-_parent nullptr; delete cur; return; } if (parent-_left cur) { parent-_left cur-_left; cur-_left-_parent parent; curn -1; } else { parent-_right cur-_left; cur-_left-_parent parent; curn 1; } delete cur; } else if (cur-_left nullptr cur-_right nullptr) { if (cur _root) { _root nullptr; delete cur; return; } if (parent-_left cur) { parent-_left nullptr; curn -1; } else { parent-_right nullptr; curn 1; } delete cur; } else { Node* replace cur-_right; while (replace-_left ! nullptr) { replace replace-_left; } parent replace-_parent; cur-_kv replace-_kv; if (parent-_left replace) { parent-_left replace-_right; if(replace-_right!nullptr) replace-_right-_parent parent; curn -1; } else { parent-_right replace-_right; if (replace-_right ! nullptr) replace-_right-_parent parent; curn 1; } delete replace; } cur parent-_left; if (curn 1) { cur parent-_right; } while (parent) { if (curn-1)//更新_bf { parent-_bf; } else { parent-_bf--; } if (parent-_bf 1 || parent-_bf -1)//为1/-1时候退出向上调整 { break; } else if (parent-_bf 0)//为0的时候更新_bf { cur parent; parent parent-_parent; if (parent nullptr) { break; } curn 1; if (cur parent-_left) { curn -1; } } else if (parent-_bf -2)//依靠_bf来旋转 { cur parent-_left; if (cur-_bf -1) { RotateR(parent); parent cur-_parent; } else if(cur-_bf 1) { RotateLR(parent); parent parent-_parent-_parent; cur cur-_parent; } else//为0的时候 { RotateR(parent); parent-_bf -1; cur-_bf 1; return; } if (parent nullptr) { break; } curn 1; if (cur parent-_left) { curn -1; } } else if (parent-_bf 2) { cur parent-_right; if (cur-_bf 1) { RotateL(parent); parent cur-_parent; } else if (cur-_bf -1) { RotateRL(parent); parent parent-_parent-_parent; cur cur-_parent; } else { RotateL(parent); parent-_bf 1; cur-_bf -1; return; } if (parent nullptr) { break; } curn 1; if (cur parent-_left) { curn -1; } } } }Part8. 反思与总结通过上面的一系列过程其实可以认识到一个结论那就是整个调整的过程就是依靠平衡因子来实现的建立模型是为了具象化平衡因子带来的影响以及在调整后高度是否改变从而来影响是否继续向上调整。所以平衡因子是全局的关键。Part9. 代码分享Part9.1. AVL实现#pragma once #includeiostream #includeassert.h #includealgorithm #includecstdlib #includevector using namespace std; templateclass k,class v struct AVLTreeNode { std::pairk, v _kv; AVLTreeNodek, v* _left; AVLTreeNodek, v* _right; AVLTreeNodek, v* _parent; int _bf; AVLTreeNode(const std::pairk, v kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) { } }; templateclass k,class v class AVLTree { typedef AVLTreeNodek, v Node; public: AVLTree() default; bool insert(const std::pairk, v kv) { if (_root nullptr) { _root new Node(kv); return true; } Node* cur _root; Node* parent nullptr; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else if(cur-_kv.first kv.first) { parent cur; cur cur-_right; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_left cur; } else { parent-_right 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) { 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 erase(const k key) { Node* cur Find(key); if (cur nullptr) return; Node* parent cur-_parent; int curn 0; if (cur-_left nullptrcur-_right!nullptr) { if (cur _root) { _root cur-_right; _root-_parent nullptr; delete cur; return; } if (parent-_left cur) { parent-_left cur-_right; cur-_right-_parent parent; curn -1; } else { parent-_right cur-_right; cur-_right-_parent parent; curn 1; } delete cur; } else if (cur-_left ! nullptr cur-_right nullptr) { if (cur _root) { _root cur-_left; _root-_parent nullptr; delete cur; return; } if (parent-_left cur) { parent-_left cur-_left; cur-_left-_parent parent; curn -1; } else { parent-_right cur-_left; cur-_left-_parent parent; curn 1; } delete cur; } else if (cur-_left nullptr cur-_right nullptr) { if (cur _root) { _root nullptr; delete cur; return; } if (parent-_left cur) { parent-_left nullptr; curn -1; } else { parent-_right nullptr; curn 1; } delete cur; } else { Node* replace cur-_right; while (replace-_left ! nullptr) { replace replace-_left; } parent replace-_parent; cur-_kv replace-_kv; if (parent-_left replace) { parent-_left replace-_right; if(replace-_right!nullptr) replace-_right-_parent parent; curn -1; } else { parent-_right replace-_right; if (replace-_right ! nullptr) replace-_right-_parent parent; curn 1; } delete replace; } cur parent-_left; if (curn 1) { cur parent-_right; } while (parent) { if (curn-1) { parent-_bf; } else { parent-_bf--; } if (parent-_bf 1 || parent-_bf -1) { break; } else if (parent-_bf 0) { cur parent; parent parent-_parent; if (parent nullptr) { break; } curn 1; if (cur parent-_left) { curn -1; } } else if (parent-_bf -2) { cur parent-_left; if (cur-_bf -1) { RotateR(parent); parent cur-_parent; } else if(cur-_bf 1) { RotateLR(parent); parent parent-_parent-_parent; cur cur-_parent; } else { RotateR(parent); parent-_bf -1; cur-_bf 1; return; } if (parent nullptr) { break; } curn 1; if (cur parent-_left) { curn -1; } } else if (parent-_bf 2) { cur parent-_right; if (cur-_bf 1) { RotateL(parent); parent cur-_parent; } else if (cur-_bf -1) { RotateRL(parent); parent parent-_parent-_parent; cur cur-_parent; } else { RotateL(parent); parent-_bf 1; cur-_bf -1; return; } if (parent nullptr) { break; } curn 1; if (cur parent-_left) { curn -1; } } } } void InOrder()const { _InOredr(_root); cout endl; } void IsAVLTree()const { if (_IsAVLTree(_root) -1) { cout NO endl; } else { cout YES endl; } } size_t Height()const { return _Height(_root); } size_t Size()const { return _Size(_root); } Node* Find(const k key) { Node* cur _root; while (cur ! nullptr) { if (cur-_kv.second key) { cur cur-_left; } else if (cur-_kv.second key) { cur cur-_right; } else { return cur; } } return nullptr; } private: void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; subL-_right parent; if (subLR ! nullptr) { subLR-_parent parent; } subL-_parent parent-_parent; if (parent _root) { _root subL; } else { if (parent-_parent-_left parent) { parent-_parent-_left subL; } else { parent-_parent-_right subL; } } parent-_parent subL; subL-_bf 0; parent-_bf 0; } void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; subR-_left parent; parent-_right subRL; if (subRL ! nullptr) { subRL-_parent parent; } subR-_parent parent-_parent; if (parent _root) { _root subR; } else { if (parent-_parent-_left parent) { parent-_parent-_left subR; } else { parent-_parent-_right subR; } } parent-_parent subR; parent-_bf 0; subR-_bf 0; } void RotateLR(Node* parent) { Node* subL parent-_left; int bf subL-_right-_bf; RotateL(subL); RotateR(parent); if (bf 1) { subL-_bf -1; } else if (bf -1) { parent-_bf 1; } else if (bf 0) { ; } else { assert(false); } } void RotateRL(Node* parent) { Node* subR parent-_right; int bf subR-_left-_bf; RotateR(subR); RotateL(parent); if (bf 1) { parent-_bf -1; } else if (bf -1) { subR-_bf 1; } else if (bf 0) { ; } else { assert(false); } } void _InOredr(Node* root)const { if (root nullptr) return; _InOredr(root-_left); cout root-_kv.second :root-_kv.secondendl; _InOredr(root-_right); } int _IsAVLTree(Node* root)const { if (root nullptr) { return 0; } int left _IsAVLTree(root-_left); int right _IsAVLTree(root-_right); if (left -1 || right -1) { return -1; } if (abs(left - right) 1 || root-_bf ! right - left) { return -1; } if (left right) { right left; } return right 1; } int _Height(Node* root)const { if (root nullptr) return 0; int leftH _Height(root-_left); int rightH _Height(root-_right); if (leftH rightH) { rightH leftH; } return rightH 1; } int _Size(Node* root)const { if (root nullptr) return 0; int leftSize _Size(root-_left); int rightSize _Size(root-_right); return leftSize rightSize1; } Node* _root nullptr; };Part9.2. 测试#include头.h void test() { const int N 1000; vectorint arr; arr.reserve(N); srand(time(0)); for (int i 0; i N; i) { arr.push_back(rand()i); } //int arr[] { 54,0,55,16,5,4,29,38,22,14 }; AVLTreeint, int aaa; for (auto e : arr) { aaa.insert({e,e}); } for (auto e : arr) { aaa.erase(e); aaa.InOrder(); aaa.IsAVLTree(); cout -------------------------------------------------------------- endl; } } int main() { test(); }Part10. 结语这篇文章我们认识到了AVL树的实现接下来小编也会带来更复杂的红黑树的讲解敬请期待~最后祝大家可以春风得意马蹄疾一日看尽长安花最后的最后要是觉得本文还可以的话可以点点赞关注小编一波谢谢大家~
