保姆级认识AVL树【C++】（精讲：AVL Insert）

目录

前言

一，概念

二，定义

三，insert

1. 插入情况

情况一：

情况二：

情况三：

2. 旋转方法

法一：左单旋法

法二：右单旋法

法三：先左后右双旋法

法四：先右后左双旋法

测试（判断一棵树是否是AVL树）

代码如下：

3. 随机值案例

四，删除

---

前言

map,set这两个容器有个共同点是： 其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

搜索二叉树请查看本篇博文：【C++】搜索二叉树底层实现_花果山~程序猿的博客-CSDN博客

一，概念

二叉搜索树虽可以缩短查找的效率，但 如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法： 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1. 它的左右子树都是AVL树

2. 左右子树高度之差(简称平衡因子)的绝对值不超过 1  (-1/0/1) （AVL树不一定用平衡因子进行实现）

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log_2 n)，搜索时间复杂度O(log_2 n)。

二，定义

为方便循序渐进的学习，这里只放最出初始的树结点定义。

template <class K, class V>
class AVL_Data
{
public:pair<K, V> _kv;AVL_Data<K, V>* left = nullptr;AVL_Data<K, V>* right = nullptr;AVL_Data<K, V>* parent = nullptr;int _bf = 0; // ballance factorAVL_Data(const pair<K, V>& p):_kv(p){}};

上面定义在后面会进行完善修改。

三，insert

根据前面搜索二叉树的经验我们能快速写完插入函数，但AVL树是特殊的搜索二叉树，我们需要对树的高度进行调整。那么我们插入时就会遇到三种情况：

1. 插入情况

情况一：

情况二：

情况三：

代码实现如下：

template <class K, class V>
class AVL_Tree
{typedef AVL_Data<K, V>  AVL_Data;AVL_Data* root = nullptr;public:bool insert(const pair<K, V>& p){AVL_Data* new_a_d = new AVL_Data(p);if (!root){root = new_a_d;}else{AVL_Data* cur = root;AVL_Data* parent = nullptr;while (cur){if (p.first < cur->_kv.first){parent = cur;cur = cur->left;}else if (p.first > cur->_kv.first){parent = cur;cur = cur->right;}else{delete(new_a_d); // 插入失败，删除新建结点return false;}}if (p.first < parent->_kv.first){parent->left = new_a_d;}else{parent->right = new_a_d;}new_a_d->parent = parent;cur = new_a_d;//完成插入，进行平衡while (parent){   // 插入，修改parent平衡因子if (cur == parent->right){parent->_bf++;}else{parent->_bf--;}// 判断parent平衡因子是否是0，如果非0则需要向祖先更新平衡因子if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->parent;}else if (parent->_bf == 0){break;}else if(parent->_bf == 2 || parent->_bf == -2){ // 处理绝对值大于1,下面代码目的是记录未修改的平衡因子。// 需要旋转处理，这个我们下面再讲cur = parent;parent = parent->parent;}else{// 出现其他情况，在插入时这棵AVL树本身就是异常AVL树assert(false);}}return true;}}
};

2. 旋转方法

法一：左单旋法

我们以下面图为讲解例子，a,b,c表示的是子树。

h 表示子树的高度。

 请看下面场景:

h = 3, 4...组合方式会更多，这里画出图没什么意义，问题是失去平衡我们如何解决？？ 

通过下面方法解决：

总结：

1. 右边高，则向左旋转。

2. C树发生插入，平衡因子发生改变，进而发生旋转。

void RotateL(AVL_Data* parent){assert(parent->right);AVL_Data* par = parent;AVL_Data* par_R = par->right;AVL_Data* par_RL = par->right->left;AVL_Data* ppnode = par->parent;par->right = par_RL;if (par_RL)par_RL->parent = par;par_R->left = par;par->parent = par_R;par_R->parent = ppnode;if (!ppnode){root = par_R;}else if (ppnode->left == par){ppnode->left = par_R;}else{ppnode->right = par_R;}par->_bf = 0;par_R->_bf = 0;}// 实验例子AVL_Tree<int, string> tree;tree.insert(make_pair(30 , "李四"));tree.insert(make_pair(20, "二麻子"));tree.insert(make_pair(60, "张三"));tree.insert(make_pair(45, "王五"));tree.insert(make_pair(75, "王五"));tree.insert(make_pair(65, "王五"));

法二：右单旋法

思路跟左旋法差不多，图像是相反，这里就只给场景解法模板：

h = 0, 1, 2的发生场景：

学会了法一自然会了法二：

void RotateR(AVL_Data* parent){assert(parent->left);AVL_Data* par = parent;AVL_Data* par_L = par->left;AVL_Data* par_LR = par->left->right;AVL_Data* ppnode = par->parent;par->left = par_LR;if (par_LR)par_LR->parent = par;par_L->right = par;par->parent = par_L;par_L->parent = ppnode;if (!ppnode){root = par_L;}else if (ppnode->left == par){ppnode->left = par_L;}else{ppnode->right = par_L;}par->_bf = 0;par_L->_bf = 0;}

法三：先左后右双旋法

跟单旋一样，我们首先展示，当h = 0，1，2时需要左右双旋处理的场景。

双旋法步骤变化流程，如下：

从结果来看，就是将60这个位置推上去置于“根”。

代码如下：

void RotateLR(AVL_Data* parent){assert(parent->left);AVL_Data* par = parent;AVL_Data* par_L = par->left;AVL_Data* par_LR = par->left->right;AVL_Data* ppnode = par->parent;int par_LR_bf = par_LR->_bf;RotateL(par_L);RotateR(par);if (par_LR_bf == -1){par->_bf = 1;par_L->_bf = 0;}else if (par_LR_bf == 1){par->_bf = 0;par_L->_bf = -1;}else if (par_LR_bf == 0){par->_bf = 0;par_L->_bf = 0;}else{assert(false);}par_LR->_bf = 0;}// 测试案例
void Test_insert_L()
{AVL_Tree<int, string> tree;tree.insert(make_pair(90, "李四"));tree.insert(make_pair(30, "二麻子"));tree.insert(make_pair(100, "张三"));tree.insert(make_pair(25, "王五"));tree.insert(make_pair(60, "王五"));tree.insert(make_pair(50, "王五"));
}

法四：先右后左双旋法

我们学会法三后，照葫芦画瓢即可。

各场景： 

代码：

void RotateRL(AVL_Data* parent){assert(parent->right);AVL_Data* par = parent;AVL_Data* par_R = par->right;AVL_Data* par_RL = par->right->left;AVL_Data* ppnode = par->parent;int par_RL_bf = par_RL->_bf;RotateR(par_R);RotateL(par);if (par_RL_bf == -1){par->_bf = 0;par_R->_bf = 1;}else if (par_RL_bf == 1){par->_bf = -1;par_R->_bf = 0;}else if (par_RL_bf == 0){par->_bf = 0;par_R->_bf = 0;}else{assert(false);}par_RL->_bf = 0;}// 测试案例
void Test_insert_L()
{AVL_Tree<int, string> tree;tree.insert(make_pair(30, "李四"));tree.insert(make_pair(20, "二麻子"));tree.insert(make_pair(90, "张三"));tree.insert(make_pair(15, "王五"));tree.insert(make_pair(60, "王五"));tree.insert(make_pair(100, "王五"));tree.insert(make_pair(55, "王五"));tree.insert(make_pair(67, "王五"));tree.insert(make_pair(95, "王五"));tree.insert(make_pair(50, "王五"));
}

测试（判断一棵树是否是AVL树）

思路：

1.  检查高度（AVL中每棵子树都是AVL树）。

2.  检查平衡因子是否正确。

代码如下：

int Hight(const AVL_Data* root){if (root == nullptr)return 0;int left_H = Hight(root->left);int left_R = Hight(root->right);return left_H >= left_R ? left_H + 1 : left_R + 1;}bool B_balance(){return _B_balance(root);}bool _B_balance(const AVL_Data* root){if (root == nullptr)return true;int left_root = Hight(root->left);int right_root = Hight(root->right);if ((right_root - left_root) != root->_bf) // 利用Hight，进行平衡因子判断return false; return abs(left_root - right_root) < 2 && _B_balance(root->left) && _B_balance(root->right);}

3. 随机值案例

用这个代码多跑几次，差不多能遍历所有环境。

void Random_Test()
{srand(time(0));const size_t N = 10000000;AVL_Tree<int, int> t;for (size_t i = 0; i < N; i++){size_t x = rand();t.insert(make_pair(x, x));}cout << t.B_balance() << endl;
}

快来测试自己的代码吧

insert全代码

bool insert(const pair<K, V>& p){AVL_Data* new_a_d = new AVL_Data(p);if (!root){root = new_a_d;}else{AVL_Data* cur = root;AVL_Data* parent = nullptr;while (cur){if (p.first < cur->_kv.first){parent = cur;cur = cur->left;}else if (p.first > cur->_kv.first){parent = cur;cur = cur->right;}else{delete(new_a_d); // 插入失败，删除新建结点return false;}}if (p.first < parent->_kv.first){parent->left = new_a_d;}else{parent->right = new_a_d;}new_a_d->parent = parent;cur = new_a_d;//完成插入，进行平衡while (parent){   // 插入，修改parent平衡因子if (cur == parent->right){parent->_bf++;}else{parent->_bf--;}// 判断parent平衡因子是否是0，如果非0则需要向祖先更新平衡因子if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->parent;	}else if (parent->_bf == 0){break;}else if (parent->_bf == -2 || parent->_bf == 2){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);// cout << "RotateL" << endl;}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);// cout << "RotateR" << endl;}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);// cout << "RotateLR" << endl;}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);// cout << "RotateRL" << endl;}else{// 出现其他情况，在插入时这棵AVL树本身就是异常AVL树// 问题出现在旋转方法assert(false);}break;}else{assert(false);}}return true;}}

四，删除

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不 错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。 具体实现学生们可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

下期预告： 红黑树！！！

结语

   本小节就到这里了，感谢小伙伴的浏览，如果有什么建议，欢迎在评论区评论，如果给小伙伴带来一些收获请留下你的小赞，你的点赞和关注将会成为博主创作的动力。