C++复习——实现AVL树，包含单旋转、双旋转，会通过递归来检测我们建的AVL树是否是合格的

        这里先简单介绍一下AVL树的由来，看过我前面的文章的兄弟应该都知道对于一颗二叉搜索树，在一些极端情况下二叉搜索树会退化为链表，从而降低我们的搜索效率，这并不是我们希望的，我们希望的数的左子树和右子树的高度相差不大（最好就是一样）。

        就这这一思想我们的大佬引入了平衡因子这个概念（其实就是一个整数），通过平衡因子来判断我们的数是否平衡，但这只起到了判断的作用，那我们应该如何将这一颗不平衡的树变为平衡，这里更有大佬提出了旋转这个东西，通过旋转就可以让我们的不平衡树变成平衡的。

        好了现在开始实现

定义节点结构体（AVLTreeNode）

        这里使用struct是因为它在C++里默认的成员级别是public，_bf就是我们的平衡因子，对于每一个叶子结点他的_bf都是0因为他的左右子树都是空，一定是平衡的。

 template <class T>struct AVLTreeNode{AVLTreeNode(const T &data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}AVLTreeNode<T> *_left;AVLTreeNode<T> *_right;AVLTreeNode<T> *_parent;T _data;int _bf; // 平衡因子};

定义树类（AVLTree） 

        顺手就把构造函数实现了，因为比较简单。

template <class T>class AVLTree{public:AVLTree(){ _root = nullptr;}// 左旋void turnleft(AVLTreeNode<T> *parent);// 右转void turnright(AVLTreeNode<T> *parent);//插入bool insert(const T &data);//打印函数std::string _Avlprint(AVLTreeNode<T>* root);void Avlprint();//求树的高度int _AVLHeight(AVLTreeNode<T>* root);void AVLHeight();//判断树是否平衡bool _JudgeAvl(AVLTreeNode<T>* root);void JudgeAvl();//析构函数~AVLTree();private:AVLTreeNode<T> *_root;};

节点的插入（insert）

        节点的插入分两个步骤：

                1.首先按照二叉搜索树的规则找到新节点的位置

                2.更新平衡因子，通过旋转是树平衡

        在第一步中我们不仅要找到新节点的位置，还要找到新节点的父节点的位置，因为我们需要判断新节点接到父节点的左节点还是右节点。我们开始时定义一个parent和一个cur，parent初始化为空cur初始化为_root

        当cur->_data小于新的data时先将parent赋值为cur，然后将cur赋值为cur->_right

        当cur->_data大于新的data时先将parent赋值为cur，然后将cur赋值为cur->_left

        当cur->_data等于新的data时就退出函数，因为AVLtree并不存在相同的元素

        直到cur为空时就找到了新节点的位置和父节点

        通过判断parent->_data和新的data的大小关系来确定新节点是parent的左节点还是右节点

        现在是第二步的更新平衡因子：对于新节点cur和他的父节点parent如果cur是parent的左节点那么parent->_bf减减，如果是右节点那么parent->_bf加加。

        做完这个处理以后，如果需要判断现在parent->_bf和cur->_bf的关系

        如果parent->_bf ==0就不需要向上更新了。

        如果parent->_bf == 1或者parent->_bf == -1那么需要继续向上更新

        如果parent->_bf == -2 && cur2->_bf == -1 就需要进行右单旋

        如果parent->_bf == 2 && cur2->_bf == 1就需要进行左单旋

        如果parent->_bf == -2 && cur2->_bf == 1 就需要先进行左单旋再进行右单旋

        如果parent->_bf == 2 && cur2->_bf == -1就需要先进行右单旋再进行左单旋

                我的代码左单旋和右单旋是反的，你们看着图理解

  // 左旋void turnleft(AVLTreeNode<T> *parent){AVLTreeNode<T> *lparent = parent->_left;AVLTreeNode<T> *lrparent = parent->_left->_right;AVLTreeNode<T> *pparent = parent->_parent;lparent->_right = parent;parent->_parent = lparent;parent->_left = lrparent;if (lrparent != nullptr)lrparent->_parent = parent;if (parent != _root){lparent->_parent = pparent;if (parent == pparent->_left)pparent->_left = lparent;elsepparent->_right = lparent;}else{lparent->_parent = nullptr;_root = lparent;}}// 右转void turnright(AVLTreeNode<T> *parent){AVLTreeNode<T> *rparent = parent->_right;AVLTreeNode<T> *rlparent = parent->_right->_left;AVLTreeNode<T> *pparent = parent->_parent;rparent->_left = parent;parent->_parent = rparent;parent->_right = rlparent;if (rlparent != nullptr)rlparent->_parent = parent;if (parent == _root){// 需要更换头结点rparent->_parent = nullptr;_root = rparent;}else{rparent->_parent = pparent;if (pparent->_left == parent)pparent->_left = rparent;elsepparent->_right = rparent;}}public:bool insert(const T &data){if (_root == nullptr)_root = new AVLTreeNode<T>(data);else{AVLTreeNode<T> *tmp = new AVLTreeNode<T>(data);AVLTreeNode<T> *parent = nullptr;AVLTreeNode<T> *cur = _root;while (cur != nullptr){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else{return false;}}int Sign = 0;// 走到这里说明找到了data的父节点if (parent->_data > data){parent->_left = tmp;Sign = 1;}else{parent->_right = tmp;Sign = -1;}tmp->_parent = parent;// 已经完成插入现在进行平衡检验->不断向上更新bf值直到更新位置的bf值为0AVLTreeNode<T> *cur2 = tmp;while (parent){if (parent->_left == cur2)parent->_bf--;elseparent->_bf++;// 判断还需不需要向上更新if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur2 = parent;parent = parent->_parent;}else{// 走到这里说明当前parent节点的_bf值为2或者为-2// 需要先判断是同侧还是异侧，同侧单旋，异侧双旋if (parent->_bf == -2 && cur2->_bf == -1){// 此时情况为同在左侧，需要左旋turnleft(parent);cur2->_bf = parent->_bf = 0;}else if (parent->_bf == 2 && cur2->_bf == 1){turnright(parent);cur2->_bf = parent->_bf = 0;}else if (parent->_bf == -2 && cur2->_bf == 1){AVLTreeNode<T> *lrparent = parent->_left->_right;turnright(cur2);turnleft(parent);cur2->_bf = lrparent->_bf = 0;parent->_bf = Sign;}else{AVLTreeNode<T> *rlparent = parent->_right->_left;turnleft(cur2);turnright(parent);cur2->_bf = rlparent->_bf = 0;parent->_bf = Sign;}break;}}}return true;}

打印函数（_Avlprint）:这里如果设置成一个函数，那么必然涉及让用户传入参数，但是我们并不希望用户访问我们的内部节点。

        对于打印函数的思路我的想法来自力扣的一道题

https://leetcode.cn/problems/construct-string-from-binary-tree/description/

        你们做了就理解我为什么这么写了

 std::string _Avlprint(AVLTreeNode<T>* root){if(root == nullptr) return "";if(root->_left == nullptr && root->_right == nullptr) return std::to_string(root->_data);if(root->_right == nullptr) return std::to_string(root->_data)+"("+_Avlprint(root->_left)+")";return std::to_string(root->_data)+"("+_Avlprint(root->_left)+")"+"("+_Avlprint(root->_right)+")";}inline int max(int x,int y){return x>y?x:y;}void Avlprint(){std::string tmp = _Avlprint(_root);std::cout<<tmp<<std::endl;}

求树的高度，很简单的就是递归当前节点是空就直接返回0，否则继续去递归，注意看我写的注释，这里有记忆化搜索的思想在里面

 int _AVLHeight(AVLTreeNode<T>* root){if(root == nullptr) return 0;//通过运算符这种方式会导致建堆的次数变多，导致时间复杂度和空间复杂度上升// return _AVLHeight(root->_left) > _AVLHeight(root->_right) ? _AVLHeight(root->_left)+1 : _AVLHeight(root->_right)+1;int lheight = _AVLHeight(root->_left);int rheight = _AVLHeight(root->_right);return max(lheight,rheight)+1;}void AVLHeight(){std::cout<<_AVLHeight(_root)<<std::endl;}

判断树是否平衡：我们需要递归的判断每一颗树是否是平衡的

bool _JudgeAvl(AVLTreeNode<T>* root){if(root == nullptr) return true;int lheight = _AVLHeight(root->_left);int rheight = _AVLHeight(root->_right);if(lheight - rheight >= 2 || lheight - rheight <= -2) return false;return _JudgeAvl(root->_left) && _JudgeAvl(root->_right);}void JudgeAvl(){std::cout<<_JudgeAvl(_root)<<std::endl;}

析构函数（~AVltree）

        我们通过队列来层序释放

~AVLTree(){// 这里我不管原理直接层序遍历std::queue<AVLTreeNode<T> *> st;st.push(_root);while (!st.empty()){AVLTreeNode<T> *tmp = st.top();st.pop();if (tmp->_left != nullptr)st.push(tmp->_left);if (tmp->_right != nullptr)st.push(tmp->_right);delete tmp;tmp = nullptr;}}

完整代码

        头文件

#include <iostream>
#include <stack>
#include <queue>
#include <memory>namespace zkj
{template <class T>struct AVLTreeNode{AVLTreeNode(const T &data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}AVLTreeNode<T> *_left;AVLTreeNode<T> *_right;AVLTreeNode<T> *_parent;T _data;int _bf; // 平衡因子};template <class T>class AVLTree{public:AVLTree(){_root = nullptr;}public:// 左旋void turnleft(AVLTreeNode<T> *parent){AVLTreeNode<T> *lparent = parent->_left;AVLTreeNode<T> *lrparent = parent->_left->_right;AVLTreeNode<T> *pparent = parent->_parent;lparent->_right = parent;parent->_parent = lparent;parent->_left = lrparent;if (lrparent != nullptr)lrparent->_parent = parent;if (parent != _root){lparent->_parent = pparent;if (parent == pparent->_left)pparent->_left = lparent;elsepparent->_right = lparent;}else{lparent->_parent = nullptr;_root = lparent;}}// 右转void turnright(AVLTreeNode<T> *parent){AVLTreeNode<T> *rparent = parent->_right;AVLTreeNode<T> *rlparent = parent->_right->_left;AVLTreeNode<T> *pparent = parent->_parent;rparent->_left = parent;parent->_parent = rparent;parent->_right = rlparent;if (rlparent != nullptr)rlparent->_parent = parent;if (parent == _root){// 需要更换头结点rparent->_parent = nullptr;_root = rparent;}else{rparent->_parent = pparent;if (pparent->_left == parent)pparent->_left = rparent;elsepparent->_right = rparent;}}// 左单旋void _turnleft(AVLTreeNode<T> *parent){AVLTreeNode<T> *lparent = parent->_left;turnleft(parent);lparent->_bf = parent->_bf = 0;}// 右单旋void _turnright(AVLTreeNode<T> *parent){AVLTreeNode<T> *rparent = parent->_right;turnright(parent);rparent->_bf = parent->_bf = 0;}// 左右旋void _turnlr(AVLTreeNode<T> *parent, int Sign){int bf = parent->_right->_left->_bf;AVLTreeNode<T> *rparent = parent->_right;AVLTreeNode<T> *rlparent = parent->_right->_left;turnleft(rparent);turnright(parent);rparent->_bf = rlparent->_bf = 0;parent->_bf = Sign;}// 右左旋void _turnrl(AVLTreeNode<T> *parent, int Sign){int bf = parent->_left->_right->_bf;AVLTreeNode<T> *lparent = parent->_left;AVLTreeNode<T> *lrparent = parent->_left->_right;turnleft(lparent);turnright(parent);lparent->_bf = lrparent->_bf = 0;parent->_bf = Sign;}public:bool insert(const T &data){if (_root == nullptr)_root = new AVLTreeNode<T>(data);else{AVLTreeNode<T> *tmp = new AVLTreeNode<T>(data);AVLTreeNode<T> *parent = nullptr;AVLTreeNode<T> *cur = _root;while (cur != nullptr){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else{return false;}}int Sign = 0;// 走到这里说明找到了data的父节点if (parent->_data > data){parent->_left = tmp;Sign = 1;}else{parent->_right = tmp;Sign = -1;}tmp->_parent = parent;// 已经完成插入现在进行平衡检验->不断向上更新bf值直到更新位置的bf值为0AVLTreeNode<T> *cur2 = tmp;while (parent){if (parent->_left == cur2)parent->_bf--;elseparent->_bf++;// 判断还需不需要向上更新if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur2 = parent;parent = parent->_parent;}else{// 走到这里说明当前parent节点的_bf值为2或者为-2// 需要先判断是同侧还是异侧，同侧单旋，异侧双旋if (parent->_bf == -2 && cur2->_bf == -1){// 此时情况为同在左侧，需要左旋turnleft(parent);cur2->_bf = parent->_bf = 0;}else if (parent->_bf == 2 && cur2->_bf == 1){turnright(parent);cur2->_bf = parent->_bf = 0;}else if (parent->_bf == -2 && cur2->_bf == 1){AVLTreeNode<T> *lrparent = parent->_left->_right;turnright(cur2);turnleft(parent);cur2->_bf = lrparent->_bf = 0;parent->_bf = Sign;}else{AVLTreeNode<T> *rlparent = parent->_right->_left;turnleft(cur2);turnright(parent);cur2->_bf = rlparent->_bf = 0;parent->_bf = Sign;}break;}}}return true;}//不方便观察版本的printfvoid Avlprint(int val){// 这里我不管原理直接层序遍历std::queue<AVLTreeNode<T> *> st;st.push(_root);while (!st.empty()){AVLTreeNode<T> *tmp = st.front();st.pop();std::cout << tmp->_data << " ";if (tmp->_left != nullptr)st.push(tmp->_left);if (tmp->_right != nullptr)st.push(tmp->_right);}}//来源于力扣的题std::string _Avlprint(AVLTreeNode<T>* root){if(root == nullptr) return "";if(root->_left == nullptr && root->_right == nullptr) return std::to_string(root->_data);if(root->_right == nullptr) return std::to_string(root->_data)+"("+_Avlprint(root->_left)+")";return std::to_string(root->_data)+"("+_Avlprint(root->_left)+")"+"("+_Avlprint(root->_right)+")";}inline int max(int x,int y){return x>y?x:y;}void Avlprint(){std::string tmp = _Avlprint(_root);std::cout<<tmp<<std::endl;}int _AVLHeight(AVLTreeNode<T>* root){if(root == nullptr) return 0;//通过运算符这种方式会导致建堆的次数变多，导致时间复杂度和空间复杂度上升// return _AVLHeight(root->_left) > _AVLHeight(root->_right) ? _AVLHeight(root->_left)+1 : _AVLHeight(root->_right)+1;int lheight = _AVLHeight(root->_left);int rheight = _AVLHeight(root->_right);return max(lheight,rheight)+1;}void AVLHeight(){std::cout<<_AVLHeight(_root)<<std::endl;}bool _JudgeAvl(AVLTreeNode<T>* root){if(root == nullptr) return true;int lheight = _AVLHeight(root->_left);int rheight = _AVLHeight(root->_right);if(lheight - rheight >= 2 || lheight - rheight <= -2) return false;return _JudgeAvl(root->_left) && _JudgeAvl(root->_right);}void JudgeAvl(){std::cout<<_JudgeAvl(_root)<<std::endl;}~AVLTree(){// 这里我不管原理直接层序遍历std::queue<AVLTreeNode<T> *> st;st.push(_root);while (!st.empty()){AVLTreeNode<T> *tmp = st.top();st.pop();if (tmp->_left != nullptr)st.push(tmp->_left);if (tmp->_right != nullptr)st.push(tmp->_right);delete tmp;tmp = nullptr;}}private:AVLTreeNode<T> *_root;};
}

        测试文件

#include <iostream>
#include "AVRtree.hpp"
#include<vector>
#include<queue>
using namespace std;void turnleft(zkj::AVLTreeNode<int> *parent, zkj::AVLTreeNode<int> *_root)
{zkj::AVLTreeNode<int> *lparent = parent->_left;zkj::AVLTreeNode<int> *lrparent = parent->_left->_right;if (parent != _root){zkj::AVLTreeNode<int> *pparent = parent->_parent;lparent->_right = parent;parent->_parent = lparent;parent->_left = lrparent;if (lrparent != nullptr)lrparent->_parent = parent;lparent->_parent = pparent;if (parent->_data < pparent->_data)pparent->_left = lparent;elsepparent->_right = lparent;}else{lparent->_right = parent;parent->_parent = lparent;parent->_left = lrparent;if (lrparent != nullptr)lrparent->_parent = parent;lparent->_parent = nullptr;_root = lparent;}// parent->_bf = lparent->_bf = 0;
}void Avlprint(zkj::AVLTreeNode<int> *_root)
{// 这里我不管原理直接层序遍历std::stack<zkj::AVLTreeNode<int> *> st;st.push(_root);while (!st.empty()){zkj::AVLTreeNode<int> *tmp = st.top();st.pop();std::cout << tmp->_data << " ";if (tmp->_left != nullptr)st.push(tmp->_left);if (tmp->_right != nullptr)st.push(tmp->_right);}
}void text()
{std::unique_ptr<zkj::AVLTree<int>> root = std::make_unique<zkj::AVLTree<int>>();// root->insert(7);// root->insert(32);// root->insert(1);// root->insert(3);// root->insert(5);// root->insert(67);// root->insert(1);// root->Avlprint();// 测试左旋和右旋zkj::AVLTreeNode<int> *parent = new zkj::AVLTreeNode<int>(5);zkj::AVLTreeNode<int> *left = new zkj::AVLTreeNode<int>(3);zkj::AVLTreeNode<int> *lleft = new zkj::AVLTreeNode<int>(1);parent->_left = left;left->_parent = parent;left->_left = lleft;lleft->_parent = left;turnleft(parent, parent);Avlprint(parent);
}int main()
{// text();zkj::AVLTree<int> root;root.insert(5);root.insert(3);root.insert(1);root.insert(10);root.insert(12);root.insert(11);root.insert(11);root.insert(15);root.insert(18);root.Avlprint();root.JudgeAvl();return 0;
}