平衡二叉树(AVL树）是数据结构中很重要的一种树结构，在很多的编程中有着很广泛的应用。但是相对来讲，平衡二叉树有比较难理解，本文教你如何快速的学会四种平衡二叉树的构建方法
文章来源：C++技术网原创文章版权所有，未经授权，禁止转载。
在这里感谢《平衡二叉树（解惑）》的作者，不得不说，我也是从这篇文章里面学会的。下面，我们进入正题：有四种平衡二叉树，分别是LL，RR,LR,RL型四种，下面，我将借鉴上面我提到过的作者的图片来讲解：对于LL型的平衡二叉树，其旋转是这么判断的，左边的图，以a为轴，将x顺时针转动，构成平衡二叉树，右边的图也是以a为轴，将x顺时针旋转，而原来的a的右子树变成了x的左子树。（x是插入的数据元素y的最近的不平衡二叉树的树结点）对于RR型的平衡二叉树，其旋转是这么判断的。两边的图都是以a为旋转轴，x逆时针旋转，而右边的图a的左子树，变成了x的右子树。对于LR型的平衡二叉树，其旋转需要经过两次（两张图都是一样的旋方向）。先是以a为轴，将y逆时针旋转，然后，以y为轴，将x顺时针转动。右边的图，c的右子树y变成了x的左子树。对于RL型的平衡二叉树，其旋转是这么判断的（两张图都是一样的旋方向）。先是以a为轴顺时针，而后以y为轴逆时针旋转。右边的图，c的右子树y变成了a的左子树。那么如何来判断平衡二叉树是哪种型别？很简单，首先，我们看离插入点最近的不平衡二叉树（x）的结点的平衡因子，而后就是结点b的平衡因子来判断。结点x的平衡因子为2，x的左孩子a的平衡因子为1,应采用LL型；若，a的平衡因子是-1,则表示是LR型。结点x的平衡因子为-2，x的右孩子a的平衡因子为-1,应采用RR型；若，a的平衡因子是1,则表示是RL型。
文章来源：C++技术网原创文章版权所有，未经授权，禁止转载。