文章目录AVL树1. 概念基本功能插入旋转旋转的规则右单旋左单旋左右双旋右左双旋AVL树的查找AVL树1. 概念与红黑树的目标一样都是控制二叉搜索树的平衡他是由前苏联两个科学家弄出来的分别叫​G.M.Adelson-Velsky​和​E.M.Landis这也是AVL名称的由来也叫自平衡二叉查找树AVL树实现这里我们引入一个平衡因子balancefactor的概念每个结点都有一个平衡因子任何结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0/1/-1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡就像一个风向标一样。平衡因子右子树高度 - 左子树高度AVL树整体结点数量和分布和完全二叉树类似高度可以控制在logN那么增删查改的效率也可以控制在OlogN相比二叉搜索树有了本质的提升。‍基本功能插入逻辑基本跟搜索二叉树保持一致每插入一个元素就要从该节点向上查找节点平衡因子是否满足-1/0/1根据情况选择旋转方式来平衡平衡因子‍根据平衡因子的计算规则我们可以知道插入左边父亲平衡因子要减减插入右边平衡因子要加加‍插入template class K, class V struct AVLTreeNode { pair(K, V) _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} } templateclass K,class V class My_avl { typedef AVLTreeNodeK, V Node; bool insert(const pair(K, 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 cur) { parent-_right cur; } else { parent-_left 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) { //旋转处理 break; } else { assert(false); } } return true; } private: Node* _root nullptr; };旋转旋转的规则保持搜索树的原则让搜索树从不平衡变平衡其次降低旋转树的高度旋转分四种右单旋、左单旋、、左右双旋、右左双旋‍右单旋‍#pragma once #includeassert.h #includeiostream #includeset #includemap using namespace std; namespace My_AVL { template class K, class V struct AVLTreeNode { pair(K, V) _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }; templateclass K,class V class My_avl { typedef AVLTreeNodeK, V Node; void RotateR(Node* parent) //右旋 { Node* subL parent-_left; Node* subLR parent-_right; parent-_left subLR; if (subLR) subLR-_parent parent-_left; Node* Parentparent parent-_parent; subL-_right parent; parent-_parent subL; // parent有可能是整棵树的根也可能是局部的⼦树 // 如果是整棵树的根要修改_root // 如果是局部的指针要跟上⼀层链接 if (Parentparent nullptr) { _root subL; subL-_parent nullptr; } else { if (Parentparent-_left parent) { Parentparent-_left subL; } else if (Parentparent-_right parent) { Parentparent-_right subl; } subL-_parent Parentparent; } return; } private: Node* _root nullptr; }; }左单旋#pragma once #includeassert.h #includeiostream #includeset #includemap using namespace std; namespace My_AVL { template class K, class V struct AVLTreeNode { pair(K, V) _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }; templateclass K,class V class My_avl { typedef AVLTreeNodeK, V Node; void RotateL(const Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_left subRL; if (subRL) subRL-_parent parent-_left; Node* Parentparet parent-_parent; subR-_right parent; parent-_parent subR; if (Parentparet nullptr) { _root subR; subR-_parent nullptr; } else { if (Parentparet-_left parent) { Parentparet-_left subR; } else if (Parentparet-_right parent) { Parentparet-_right subR; } subR-_parent Parentparet; } return; } private: Node* _root nullptr; }; }左右双旋不需要再重头开始写在相应部分复用左旋和右旋代码不是纯粹的右边高或者左边高‍//为了更清晰的显示这里直接给关键代码头文件和相关成员变量可以参考上面代码 void RotateLR(const Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf; RotateL(parent-_left); RotateLR(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 ; } else if (bf -1) { subL-_bf 0; subLR-_bf 0; parent-_bf 1; } else { assert(false); } }右左双旋与左右双旋高度类似注意一点与上面的左右双旋相反的一点需要双旋的那一坨由根节点的左子树那一块变成了根节点的右子树那一块。那么在完成双旋后​parent​节点变成了左边​subR节点变成了右边//为了更清晰的显示这里直接给关键代码头文件和相关成员变量可以参考上面代码 void RotateRL(const Node* parent) { Node* subR parent-_right; Node* subRL subR-_right; int bf subR-_bf; RotateR(parent-_right); Rotate(parent); if (bf 0) { subL-_bf 0; subLR-_bf 0; parent-_bf 0; } else if (bf 1) { subL-_bf 0; subLR-_bf 0; parent-_bf -1 ; } else if (bf -1) { subL-_bf 1; subLR-_bf 0; parent-_bf 0; } else { assert(false); } }AVL树的查找AVL树的查找与二叉搜索树的查找是一样的搜索效率是O(log N)比它大就往右走比他小就往左走‍完