小编主页详情-请点击小编gitee代码仓库-请点击本文主要介绍了AVL树实现AVL的概念、AVL树的实现、旋转、AVL树的查找、AVL树平衡检测内容全由作者原创无AI并带有配图帮助博友们更好的理解点个关注不迷路下面进入正文~~目录1. AVL的概念2. AVL树的实现2.1 AVL树的结构2.2 AVL树的插入2.2.1 AVL树插入一个值的大概过程2.2.2 平衡因子更新2.2.3 插入结点及更新平衡因子的代码实现2.3 旋转2.3.1 旋转的原则2.3.2 右单旋2.3.3 右单旋代码实现2.3.4 左单旋2.3.5 左单旋代码实现2.3.6 左右双旋2.3.7 左右双旋代码实现2.3.8 右左双旋2.3.9 右左双旋代码实现2.4 AVL树的查找2.5 AVL树平衡检测结语1.AVL的概念AVL树是最先发明的自平衡二叉查找树AVL是一颗空树或者具备下列性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树通过控制高度差去控制平衡。AVL树实现这里我们引入一个平衡因子的概念每个结点都有一个平衡因子任何结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0、1、-1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡就像一个风向标一样。思考一下为什么AVL树是高度平衡搜索二叉树要求高度差不超过1而不是高度差是0呢0不是更好的平衡吗画画图分析我们发现不是不想这样设计而是有些情况是做不到高度差是0的。比如一棵树是2个结点4个结点等情况下高度差最好就是1无法做到高度差是0。AVL树整体结点数量和分布和完全二叉树类似高度可以控制在 log N那么增删查改的效率也可以控制在 O(log N)相比二叉搜索树有了本质的提升。2.AVL树的实现2.1AVL树的结构templateclass K, class V struct AVLTreeNode { // 需要parent指针后续更新平衡因子可以看到 pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; // balance factor AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: //... private: Node* _root nullptr; };2.2AVL树的插入2.2.1AVL树插入一个值的大概过程1. 插入一个值按二叉搜索树规则进行插入。2. 新增结点以后只会影响祖先结点的高度也就是可能会影响部分祖先结点的平衡因子所以更新从新增结点-根结点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可以停止了具体情况我们下面再详细分析。3. 更新平衡因子过程中没有出现问题则插入结束。4. 更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后本质调平衡的同时本质降低了子树的高度不会再影响上一层所以插入结束。2.2.2平衡因子更新更新原则• 平衡因子 右子树高度 - 左子树高度。• 只有子树高度变化才会影响当前结点平衡因子。• 插入结点会增加高度所以新增结点在parent的右子树parent的平衡因子新增结点在parent的左子树parent平衡因子--。• parent所在子树的高度是否变化决定了是否会继续往上更新。更新停止条件• 更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0或者1-0说明更新前parent子树一边高一边低新增的结点插入在低的那边插入后parent所在的子树高度不变不会影响parent的父亲结点的平衡因子更新结束。• 更新后parent的平衡因子等于1或-1更新前更新中parent的平衡因子变化为0-1或者0--1说明更新前parent子树两边一样高新增的插入结点后parent所在的子树一边高一边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲结点的平衡因子所以要继续向上更新。• 更新后parent的平衡因子等于2或-2更新前更新中parent的平衡因子变化为1-2或者-1--2说明更新前parent子树一边高一边低新增的插入结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把parent子树旋转平衡2、降低parent子树的高度恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新插入结束。• 不断更新更新到根根的平衡因子是1或-1也停止了。更新到10结点平衡因子为210所在的子树已经不平衡需要旋转处理。更新到中间结点3为根的子树高度不变不会影响上一层更新结束。最坏更新到根停止。2.2.3插入结点及更新平衡因子的代码实现templateclass K, class V class KVLTree { typedef AVLTreeNodeK, V Node; public: bool insert(const pairK, 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; } else { parent-_left cur; } cur-_parent parent; while (parent) { if (parent-_left cur) { parent-_bf--; } else { parent-_bf; } if (parent-_bf 0) { break; } else if (parent-_bf 1 || parent-_bf -1) { cur parent; parent cur-_parent; } else if (parent-_bf 2 || parent-_bf -2) { //旋转 break; } else { assert(false); } return true; } } private: Node* _root; };2.3旋转2.3.1旋转的原则1. 保持搜索树的规则2. 让旋转的树从不满足变平衡其次降低旋转树的高度旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。2.3.2右单旋图片展示的是10为根的树有a/b/c抽象为三棵高度为h的子树h0a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树是一种概括抽象表示他代表了所有右单旋的场景实际右单旋形态有很多种。在a子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树左边太高了需要往右边旋转控制两棵树的平衡。旋转核心步骤因为5b子树的值10将b变成10的左子树10变成5的右子树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转原则。如果插入之前10整棵树的一个局部子树旋转后不会再影响上一层插入结束了。2.3.3右单旋代码实现void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; if (subLR) { subLR-_parent parent; } Node* pParent parent-_parent; parent-_left subLR; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parent pParent-_left) { pParent-_left subL; } else { pParent-_right subL; } subL-_parent pParent; } subL-_bf parent-_bf 0; }2.3.4左单旋左单旋的逻辑和右单旋完全类似这里不作详细解析下面会给出左单旋代码。2.3.5左单旋代码实现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 (parentParent nullptr) { _root subR; subR-_parent nullptr; } else { if (parent parentParent-_left) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } parent-_bf subR-_bf 0; }2.3.6左右双旋通过图片看到左边高时如果插入位置不是在a子树而是插入在b子树b子树高度从h变成h1引发旋转右单旋无法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边高但是插入在b子树中10为跟的子树不再是单纯的左边高对于10是左边高但是对于5是右边高需要用两次旋转才能解决以5为旋转点进行一个左单旋以10为旋转点进行一个右单旋这棵树就平衡了。下面我们将a/b/c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树因为我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论。场景1h1时新增结点插入在e子树e子树高度从h-1并为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为-1旋转后8和5平衡因子为010平衡因子为1。场景2h1时新增结点插入在f子树f子树高度从h-1变为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为1旋转后8和10平衡因子为05平衡因子为-1场景3h0时a/b/c都是空树b自己就是一个新增结点不断更新5-10平衡因子引发旋转其中8的平衡因子为0旋转后8和10和5平衡因子均为0。2.3.7左右双旋代码实现void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf; RotateL(parent-_left); RotateR(parent); if (bf -1) { subL-_bf subLR-_bf 0; parent-_bf -1; } else if (bf 1) { parent-_bf subLR-_bf 0; subL-_bf -1; } else if(bf 0) { subL-_bf subLR-_bf parent-_bf 0; } else { assert(false); } }2.3.8右左双旋右左双旋的逻辑和左右双旋完全类似这里不作详细解析下面会给出右左双旋代码。2.3.9右左双旋代码实现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); } }2.4AVL树的查找那二叉搜索树逻辑实现即可搜索效率为O(logN)Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_right; } else if (cur-_kv.first key) { cur cur-_left; } else { return cur; } } return nullptr; }2.5AVL树平衡检测我们实现的AVL树是否合格我们通过检查左右子树高度差的程序进行反向验证同时检查一下结点的平衡因子更新是否出现了问题。void InOrder() { _InOrder(_root); cout endl; } int Height() { return _Height(_root); } int Size() { return _Size(_root); } bool IsBalanceTree() { return _IsBalanceTree(_root); } private: void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_kv.first : root-_kv.second endl; _InOrder(root-_right); } 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; } int _Size(Node* root) { if (root nullptr) return 0; return _Size(root-_left) _Size(root-_right) 1; } bool _IsBalanceTree(Node* root) { // 空树也是AVL树 if (nullptr root) return true; // 计算pRoot结点的平衡因子即pRoot左右子树的高度差 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; // 如果计算出的平衡因子与pRoot的平衡因子不相等或者 // pRoot平衡因子的绝对值超过1则一定不是AVL树 if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } // pRoot的左和右如果都是AVL树则该树一定是AVL树 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); } void TestAVLTree1() { AVLTreeint, int t; // 常规的测试用例 int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 特殊的带有双旋场景的测试用例 //int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { t.Insert({ e, e }); } t.InOrder(); cout t.IsBalanceTree() endl; } // 插入一堆随机值测试平衡顺便测试一下高度和性能等 void TestAVLTree2() { const int N 1000000; vectorint v; v.reserve(N); srand(time(0)); for (int i 0; i N; i) { v.push_back(rand() i); } size_t begin2 clock(); AVLTreeint, int t; for (auto e : v) { t.Insert(make_pair(e, e)); } size_t end2 clock(); cout Insert: end2 - begin2 endl; cout t.IsBalanceTree() endl; cout Height: t.Height() endl; cout Size: t.Size() endl; size_t begin1 clock(); // 确定在的值 for (auto e : v) { t.Find(e); } // 随机值 /*for (size_t i 0; i N; i) { t.Find((rand() i)); }*/ size_t end1 clock(); cout Find: end1 - begin1 endl; } int main() { TestAVLTree2(); return 0; }结语这篇文章全文由作者手写图片由画图软件所制无AI制作希望各位博友能有所收获欢迎各位博友的讨论觉得不错的小伙伴别忘了点赞关注哦~