C++中AVL树的底层逻辑原理及其实现原理和过程

小编在学习完AVL树之后觉得AVL树的底层逻辑原理不是很难，在实现AVL树的过程中可能在调整过程中经过旋转调整会有点难，但是小编可以给大家讲解清楚，结合旋转过程的详细解图，相信大家一定可以学会并且理解AVL树的底层逻辑原理及其实现，话不多说，进入学习！~~~

前导：

继上个博客大家学习完搜索二叉树之后，会发现在下面这种情况下，搜索二叉树的效率会大大降低，附图

所以今天我们学习AVL树就是为了解决这种一边倒的情况，让这棵树一直保持在两侧高度差不超过1，以此来提高查找的效率。

一、AVL树的底层逻辑原理

底层原理：插入的过程和搜索二叉树相同，但是保证每次插入一个节点两边的高度差不超过1，这样就是一个AVL树。

二、AVL树的实现原理

实现原理：通过对搜索二叉树的修改来实现AVL树，在实现AVL树的过程中，我们需要引入一个平衡因子来保证每次插入的过程，树两边的高度差仍然是一，再次还要引入一个节点的指针，引入一个父节点的指针(后面旋转有用会讲)，引入平衡因子之后就为我们对树进行旋转做了准备，这样就可以通过旋转来保证AVL树的高度差不超过1。

三、AVL树的实现过程

1、在了解AVL树的底层原理之后，大家肯定会对这个新增的平衡因子有疑惑，现在我来告诉大家这个平衡因子的作用，在这里先说一下平衡因子的作用：

平衡因子作用：平衡因子的作用就是为了记录子树两侧的高度差，当高度差大于1的时候就需要进行操作旋转(后面就会讲)，来保证树的高度差不超过1，也就是AVL树。

请看下图及其平衡因子的讲解(在这里我们规定右边高度为正，左边高度为负)：

因为每次新插入一个节点的时候，树两边的高度差会被改变，所以我们每次插入之后需要更新平衡因子，当平衡因子超过绝对值1之后，也就是高度差超过1之后，就会引出旋转，来保持树的平衡，来做到AVL树。

2、在了解到平衡因子的作用之后，大家先跟着我实现一下AVL树的基础结构，代码如下：

template<class T1, class T2>
struct AVLTreeNode
{pair<T1,T2> _data;struct AVLTreeNode<T1,T2>* _left;struct AVLTreeNode<T1, T2>* _right;struct AVLTreeNode<T1, T2>* _parent;   // 存的是当前节点的父节点int bf;                                // balance factor 记录的是当前位置的平衡因子AVLTreeNode(const pair<T1,T2>& data):_data(data),_left(nullptr),_right(nullptr),bf(0)               // 因为每次插入的这个节点左右子节点都为空，所以它的平衡因子为0,_parent(nullptr){}
};

3、接下来我们就来实现一下AVL树的节点插入过程，和搜索二叉树不同的是，在插入的过程中我们需要更新每个节点的平衡因子，并且为了后面树不平衡来进行旋转做准备。大家先看下面的图和注释先来了解如何更新平衡因子，这样方便我们来实现插入节点和更新平衡因子的过程：

在更新平衡因子的过程中，这里还有两种不同的情况，请看下图分析：

总结：在向上更新节点的平衡因子过程中，如果更新到哪个节点的平衡因子为0，就不再继续往上更新平衡因子，因为插入的这个节点不会影响到其他节点，只会影响到自己的父节点。

接下来就该讲到大家最期待的旋转过程了，虽然有点难，但是我会给大家讲清楚的，首先我们应该明白当平衡因子到什么情况下才需要进行旋转的过程，如下图和注释供大家参考和学习：

以上就是所有关于平衡因子的内容，接下来我们来讲解旋转的过程，也就是大家最期待的过程，看了上面大家已经明白了当平衡因子到达什么情况才需要进行旋转，在这里我直接告诉大家旋转方法，旋转有四种情况，我一一来告诉大家：

a、左单旋

b、右单旋

因为左单旋和右单旋的操作类似，所以在这里不在讲解，大家不理解的话请先理解左单旋，右单旋也就会了。

c、先左旋再右旋

d、先右旋再左旋

因为先左旋再右旋和先右旋再左旋的操作类似，所以在这里不在讲解，大家不理解的话请先理解先左旋再右旋，先右旋再左旋也就会了。

总结：

1、左、右单旋：当即将旋转的时候，平衡因子为同号的话就只需要进行单旋即可。

2、先左、右单旋，再右、左单旋：当即将旋转的时候，平衡因子为异号的话就只需要进行双旋。

可能大家会有点疑惑，同号和异号有什么区别，所以我在这块给大家准备了图和注释，相信大家很容易就可以理解：

明白了上面这些，请大家和我一起实现一下节点插入的操作：

bool Insert(const pair<T1, T2>& x)
{// 第一次插入节点if (_root == nullptr){_root = new Node(x);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data.first < x.first){parent = cur;cur = cur->_right;}else if (cur->_data.first > x.first){parent = cur;cur = cur->_left;}else{// 走到else说明搜索二叉树里面有这个值，所以就不用插入return false;}}if (parent->_left == cur && parent->_data.first > x.first)  // 确定插入的值在哪边{parent->_left = new Node(x);parent->_left->_parent = parent;cur = parent->_left;}else{parent->_right = new Node(x);parent->_right->_parent = parent;cur = parent->_right;}// 更新 bf 的操作while (parent){if (parent->_left == cur && (parent->bf == 0 || parent->bf == 1)){parent->bf--;}else if (parent->_right == cur && (parent->bf == 0 || parent->bf == -1)){parent->bf++;}else  // 走到这块说明平衡因子为 2 或者 -2{// 旋转if (parent->_right == cur && parent->bf == 1 && cur->bf == 1){// 左单旋RotateL(parent);}else if (parent->_left == cur && parent->bf == -1 && cur->bf == -1){// 右单旋RotateR(parent);}else if (parent->_left == cur && parent->bf == -1 && cur->bf == 1){// 先左旋在右旋RotateLR(parent);}else if (parent->_right == cur && parent->bf == 1 && cur->bf == -1){// 先右旋在左旋RotateRL(parent);}else{assert(false);}break;}if (parent->bf == 0)               // 当平衡因子更新完等于 0 之后 便不再向上继续调整break;cur = parent;parent = parent->_parent;}return true;
}// 左单旋
void RotateL(Node* parent)
{Node* parent_Parent = parent->_parent;           // 记录此时根节点的父节点 为后面判断是子树还是根做准备Node* subR = parent->_right;Node* subRL = subR->_left;// 左单旋的操作 连接起来节点 并且改变父节点parent->_right = subRL;if(subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parent_Parent == nullptr)                    // 说明这个节点就为根节点{_root = subR;subR->_parent = nullptr;}else                                             // 说明这个节点只是一个子树的节点{if (parent_Parent->_left == parent)parent_Parent->_left = subR;elseparent_Parent->_right = subR;subR->_parent = parent_Parent;}subR->bf = parent->bf = 0;                       // 改变这些地方的平衡因子
}// 右单旋
void RotateR(Node* parent)
{Node* parent_Parent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if(subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (parent_Parent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent_Parent->_left == parent)parent_Parent->_left = subL;elseparent_Parent->_right = subL;subL->_parent = parent_Parent;}subL->bf = parent->bf = 0;
}// 先左旋再右旋
void RotateLR(Node* parent)
{Node* SubL = parent->_left;Node* SubLR = SubL->_right;int bf = SubLR->bf;RotateL(parent->_left);RotateR(parent);// 更新平衡因子if (bf == 0)                            // 处理 h == 0 的情况{parent->bf = 0;SubL->bf = 0;}else if (bf == 1)       // 后面的是处理 h > 0 的情况{parent->bf = 0;SubL->bf = -1;}else if(bf == -1){SubL->bf = 0;parent->bf = 1;}else{assert(false);}SubLR->bf = 0;
}// 先右旋再左旋
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);}}

好了以上就是今天最难的部分，相信大家看完这部分肯定会收获满满。

4、接下来就是AVL树的遍历和AVL树的销毁部分，这部分和搜索二叉树一样，我就不在这里做详细讲解了，大家如果有什么不理解的可以评论区留言或者私信我，我帮大家解答，代码及注释我就放到下面了，供大家参考：

// 查找二叉树的中序遍历刚好是顺序排序
void InOrder()
{// 中序遍历需要递归来解决，所以这个 _root 不好传 如果直接用_root 的话 _root 就会被改变Node* cur = _root;_InOrder(cur);cout << endl;
}void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_data.first << ":" << root->_data.second << endl;_InOrder(root->_right);
}~AVLTree()
{// 后序删除空间  左 右 根_AVLTreeDestory(_root);_root = nullptr;
}void _AVLTreeDestory(Node* root)
{if (root == nullptr)return;_AVLTreeDestory(root->_left);_AVLTreeDestory(root->_right);delete root;
}

5、为了验证自己写的AVL树是否满足条件，也就是否高度差为1，所以对于AVL树我们还有其他操作，比如树的高度，树的节点的计算方法，这里和初阶的二叉树的求解方法一样，所以我不在做详细解答，如果大家有什么不会的，可以评论区留言，或者私信我，代码及注释我放到下面了，供大家参考：

// 节点个数
int Size()
{return _size(_root);
}// 树的高度
int Height()
{return _Height(_root);
}int _size(Node* root)
{if (root == nullptr)return 0;return _size(root->_left) + _size(root->_right) + 1;
}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;
}// 判断是否为AVL树
bool IsAVLTree()
{return _IsAVLTree(_root);
}bool _IsAVLTree(Node* root)
{if (root == nullptr)return true;// 判断每一棵子树是否为AVL树int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果高度差大于1就说明不满足AVL树的底层原理if (abs(diff) > 1)return false;return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
}

好啦，以上就是今天的所有内容，相信大家看完一定会收获满满，我们下次再见！~~~~