1.AVL树介绍前面说过有二叉搜索树并且也说到了二叉搜索树会出现极端情况所有的新插入的节点都在同一边的可能这种情况非常不利于我们使用。因此出现了AVL树AVL树是最先发明的自平衡二叉搜索树。AVL树需要遵循以下规则首先它一定是一个二叉搜索树它的左右子树也都是AVL树并且左子树和右子树的高度差不能超过1。这样就可以保证我们在增删查改的时候的效率为log2(N)以2为底N的对数。为了方便我们实现左右子树的高度差不超过1我们引入了平衡因子的概念平衡因子的数值等于右子树的高度减去左子树的高度。在两边子树高度差不超过1的前提下那么平衡因子的大小只能取01-1这三个数。AVL树节点如下templateclass K,class V struct AVLTreeNode { AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; //在计算平衡因子和后面的旋转需要用到父节点 pairK, V _kv; //第一个数据存储key第二个数据存储value int _bf; //平衡因子 AVLTreeNode(const pairconst K, V kv) //构造函数 :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_bf(0) //新节点左右都为空平衡因子为0 {} };2.AVL树插入时平衡因子的更新AVL树的插入过程和二叉搜索树的插入是一样的但是我们要改变平衡因子并在平衡因子不是01-1的时候做出改变。我们可以分析一下平衡因子可能的情况我们先看在左边插入的情况在左边插入有两种情况一种是父节点没有右孩子这个时候父节点的平衡因子从0--1。还有一种情况则是父节点有右孩子这个时候父节点的平衡因子就从1-0。接下来是在右边插入的情况在右边插入有两种情况一种是父节点没有左孩子这个时候父节点的平衡因子从0-1。还有一种情况则是父节点有左孩子这个时候父节点的平衡因子就从-1-0。而在左插入和在右插入都有一种情况就是上面两张图左边的情况这个时候以父节点为根的这棵树的高度发生了变化都加了1。那么就会造成父节点的父节点的平衡因子改变这种改变可能会一直往上走造成上面的平衡因子的改变。那么什么时候应该停下平衡因子的改变呢在父节点的平衡因子变成0的时候平衡因子变成0只有两种情况1-0或者-1-0。这里我们设父节点叫A节点设A的父节点叫B节点B节点的另一个孩子节点是C节点A节点从1变成0那么说明A一开始插入之前A的右子树比左子树高出一而插入之后变成0说明左子树被插入了新节点这个时候左右子树的高度都变成了右子树的高度那么A整体的高度并没有变化所以AC的高度差也没有发生变化就不需要继续往上改变B的平衡因子。A节点从-1变成0那么说明A一开始插入之前A的左子树比右子树高出一而插入之后变成0说明右子树被插入了新节点这个时候左右子树的高度都变成了左子树的高度那么A整体的高度并没有变化所以AC的高度差也没有发生变化就不需要继续往上改变B的平衡因子。我们可以根据上面的在推出A的平衡因子变成1或-1的时候需要继续向上改变平衡因子这里作者就不再过多赘述了大家可以自行推导。而我们在插入时并不是只有上面四种情况还有两种情况需要我们讨论那就是造成极端情况的情况平衡因子变成2或-2如下情况这种情况下二叉树的平衡被打破我们就需要旋转来让它保持原来的平衡旋转的具体细节在后面标题3里面作者再详细说明。根据上面所述我们可以有以下代码#includeassert #includeiostream using namespace std; templateclass K, class V struct AVLTreeNode { AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; //在计算平衡因子和后面的旋转需要用到父节点 pairK, V _kv; //第一个数据存储key第二个数据存储value int _bf; //平衡因子 AVLTreeNode(const pairconst K, V kv) //构造函数 :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) //新节点左右都为空平衡因子为0 { } }; templateclass K, class V class AVLTree { typedef AVLTNodeK, V node; private: node* _root nullptr; public: bool insert(const pairK, V kv) { if (_root nullptr) //空树情况 { node* root new node(kv); _root root; return true; } else { //非空树先一直往下找要插入的位置 node* ptr nullptr; //父节点(比较节点) node* ptr1 _root; //子节点 while (ptr1 ! nullptr) { ptr ptr1; if (kv.first ptr-_kv.first) //比父节点大在右子树 { ptr1 ptr-_kv._right; } else if (kv.first ptr-_kv.first) //比父节点小在左子树 { ptr1 ptr-_kv._left; } else //跟父节点一样大已经存在不能插入重复元素 { cout 该节点已经存在无法插入 endl; return false; } } node* newnode new node(kv); //找到了要插入的位置插入并改变平衡因子 if (kv.first ptr-_kv.first) //比父节点大在右子树插入 { ptr-_right newnode; } else //比父节点小在左子树插入 { ptr-_left newnode; } newnode-_parent parent; node* cur newnode; //ptr是父节点 cur是孩子节点 //插入完成统一进行平衡因子的改变 while (ptr ! nullptr) { if (cur ptr-_left) //插入是左边不管ptr有没有右孩子都必须平衡因子-1 { ptr-_bf--; } else //插入是右边不管ptr有没有左孩子都必须平衡因子1 { ptr-_bf; } //改变完父节点的平衡因子之后再看看改变后的有没有超出范围 if (ptr-_bf 0) //平衡因子为0停止不用再继续 { break; } else if (ptr-_bf -1 || ptr-_bf 1) //平衡因子为-1或者1继续往上 { cur ptr; ptr ptr-_parent; } else if (ptr-_bf 2 || ptr-_bf -2) { //....... //....... //....... //按情况旋转 } else //用于防止超出预期情况用于发现可能自己未注意到的问题 { arrest(0); } } } } };这里需要说明最后的那个else其实可以不写而倒数第二个的else if改成else具体的平衡因子是2还是-2在后面再进行详细的完全的判断。加上最后的else是为了在测试代码多运行不同案例时帮助自己发现是否写的代码有所纰漏如果有直接报错终止程序就说明少写了某种可能而不用一个一个看前面是哪里出了纰漏。3.AVL树的旋转前面说了旋转是为了应对平衡因子出现2或者-2的情况旋转一共有4种旋转左旋右旋左右双旋右左双旋。下面一步步进行分析我们统一设平衡因子崩溃的那个节点为A节点左孩子为B节点右孩子为C节点。我们先看平衡因子变成2的情况平衡因子变成2说明右子树比左子树高2并且A节点原来的平衡因子为1因为平衡因子每次必定是/-1。A原来的平衡因子为1说明C子树比B子树高1并且需要注意的是在这种情况下C的左右子树的高度一定是B子树的高度如图DE子树的高度一定是等于B子树的高度的这个解释起来可能有些晕我会尽我可能的解释看不懂的可以结合着图或者自己画一下多看几遍实在看不懂的可以直接跳过默认是这样的就行。首先DE子树里面一定是至少有一个是比B子树高1的这样才符合原来A的平衡因子是1的情况。我们假设D是h高度E是h-1高度然后开始新增节点新增节点一定是在D上面那样C的高度才会比B大2A才能变成2的平衡因子但是这个时候E就比D小2个高度C的平衡因子就会变成-2。但是这是不可能出现的因为我们处理平衡因子的改变是从下往上的在发现A之前就一定会先发现C的平衡因子崩溃并且先处理完C的崩溃(这个时候C就是一个新的A)但是崩溃问题在旋转处理完成之后就不用继续往上A就不可能平衡因子崩溃。所以这种情况不可能。同理还有E的高度是h-1,D的高度是h的情况。所以A的平衡因子变成2只有DEB三者的高度相同的情况下才可能出现。这也是同理于A的平衡因子是-2的时候。解释完之后我们再看新插入节点有两种可能往D或者往E上插入第一种往E上插入此时C的平衡因子为1那么这种情况下就需要左旋C到AB之间B做C的左子树D做C的右子树E做A的右子树如下第二种往D上插入此时C的平衡因子为-1那么这种情况下就需要右左双旋先把D提出来作为D节点与D的左子树和右子树然后以D为中心右旋以C为中心左旋如下依次类推当A的平衡因子为-2的时候再根据B的平衡因子是1与-1分出了右单旋与左右双旋这里作者就不进行推导读者可以自行在纸上推导。最后就是代码部分#includeiostream using namespace std; templateclass K, class V class AVLTNode { public: pairK, V _kv; AVLTNode* _left; AVLTNode* _right; AVLTNode* _parent; int _bf; AVLTNode(pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} AVLTNode(const K key, const V val) :_kv(key, val) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} }; templateclass K, class V class AVLTree { typedef AVLTNodeK, V node; private: node* _root nullptr; public: //还是仅在insert的时候申请资源主要写单旋双旋 void RotateR(node* parent) //右单旋 { node* cur parent-_left; node* ppar parent-_parent; parent-_left cur-_right; if (parent-_left) parent-_left-_parent parent; cur-_right parent; cur-_parent ppar; parent-_parent cur; if (ppar) //parent一开始不是根 { if (parent ppar-_left) ppar-_left cur; else ppar-_right cur; } else { _root cur; } cur-_bf 0; parent-_bf 0; } void RotateL(node* parent) //左单旋 { node* cur parent-_right; node* ppar parent-_parent; node* chl cur-_left; if (chl) chl-_parent parent; parent-_right chl; cur-_left parent; parent-_parent cur; if (ppar) //parent一开始不是根 { if (parent ppar-_left) ppar-_left cur; else ppar-_right cur; } else { _root cur; } cur-_bf 0; parent-_bf 0; } void RotateRL(node* parent) //右左双旋 { node* cur parent-_right; node* childl cur-_left; int bf childl-_bf; RotateR(cur); RotateL(parent); if (bf -1) { parent-_bf 0; childl-_bf 0; cur-_bf 1; } else if (bf 1) { parent-_bf -1; childl-_bf 0; cur-_bf 1; } else { parent-_bf 0; childl-_bf 0; cur-_bf 0; } } void RotateLR(node* parent) //左右双旋 { node* cur parent-_left; node* childr cur-_right; int bf childr-_bf; RotateL(cur); RotateR(parent); if (bf -1) { parent-_bf -1; cur-_bf 0; childr-_bf 0; } else if(bf 1) { cur-_bf -1; parent-_bf 0; childr-_bf 0; } else { parent-_bf 0; cur-_bf 0; childr-_bf 0; } } //插入 bool insert(const pairK, V kv) { if (_root nullptr) { node* cur new node(kv); _root cur; return true; } node* cur _root; node* parent nullptr; while (cur) { parent cur; if (kv.first cur-_kv.first) { cur cur-_right; } else if (kv.first cur-_kv.first) { cur cur-_left; } else { cout 该值已经存在 endl; return false; } } node* newnode new node(kv); if (kv.first parent-_kv.first) parent-_right newnode; else parent-_left newnode; newnode-_parent parent; cur newnode; 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 cur-_parent; } else { if (cur parent-_right)//包含左单旋右左双旋 { if (cur-_bf 1 parent-_bf 2) //左单旋 { RotateL(parent); return true; } else if (cur-_bf -1 parent-_bf 2) { RotateRL(parent); return true; } } else//包含右单旋左右双旋 { if (cur-_bf -1 parent-_bf -2) { RotateR(parent); return true; } else if (cur-_bf 1 parent-_bf -2) { RotateLR(parent); return true; } } //if(parent _root) // break; } } return true; } };4.AVL树的验证AVL树验证我们主要验证平衡因子是否符合条件代码如下//前面的部分作者就不再赘述大家可以跟前面的结合的看 public: //判断是否是平衡二叉树 bool IsBalanceTree() { return _IsBalanceTree(_root); } private: bool _IsBalanceTree(node* root) { // 空树也是AVL树 if (nullptr root) return true; if (root-_bf -1 || root-_bf 1) return false; return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); }5.AVL树的删除与查找AVL树的删除较为困难建议自行查找学习而查找部分的知识与前面文章二叉搜索树的内容相同都是同样的原理可以自行观看。