在计算机的使用中查找是个很重要的算法，但是一般的简单查找算法效率都不高，其中比较显著的方法是二分查找，但是二分查找的局限性很大，他只能在有序的数组中进行查找，所以想要用二分查找就必须先要对查找的数据进行排序，但是排序的时间复杂度又是一个问题。所以就提出了用树形的储存方式去存放数据排序和查找。
二叉搜索树将存入的数据以特定的顺序存储，将大的数以迭代的方式存在结点的右边将小的数存在左边，这样不仅在查找时时间复杂度与二分查找持平而且中序遍历这棵树还能得到所有数据的升序序列。但是二叉搜索树还有一个缺点，这个缺点与快速排序的缺点有点像，就是快速排序再排有序的数据时会严重退化，时间复杂会变成O（n2）搜索二叉树也是这样子，再不断存入有序数据时会不断加大树的深度，是树的结构严重不平衡，以至于查找时时间复杂度变为O（n）.所以就有了二叉平衡搜索树也叫AVL树。
AVL树：他是高度平衡的二叉搜索树，他的所有左右树的根节点的最大深度相差不会超过一，实现了无论什么情况下查找的时间复杂度都与二分查找相同，且不需要提前排序。
首先是结点的数据结点模型：节点中包含左右子树根节点的指针，键值对，与二叉搜索树不同的是又新增了双亲结点的指针，和一个平衡因子。双亲结点的作用是用来调节平衡因子的，平衡因子的作用是用来检测树的平衡度。
1：首先判段根节点是否为空的情况，若不为空定义一个cur用来迭代定位要插入的位置，再定义一个结点指针parent用来记录cur的双亲。
2：不断迭代cur直至其为空，再用构造函数把cur构造了，然后将cur连接到树的特定位置。
3：此时就要用到parent了，用while循环判断parent不为空则向上更新每个结点的平衡因子，若cur是parent的右孩子这此结点的平衡因子加一，若为左则减一。
4：每次跟新完平衡因子后若平衡因子为零则表示，之前此结点为-1或1，被调节为零不影响整个树的平衡，此时退出循环。若为-1或1则树的变化在可接受范围之内，不用进行调节，但是还是要向上更新，因为上面可能还会有变化，若为-2或者2则需要进行旋转调节。
5：旋转调节分为左旋转和右旋转，和右左旋转和左右旋转四种。
1>：左单旋转：将根节点称为parent将根节点的左子树成为subL，首先将subL的右子树结点与parent的左子树链接，然后判断这个结点是否为空，若为空则不需要考虑空结点的双亲结点，若不为空则需要将其双亲结点设为parent.此时还要考虑sub和parent，若parent是根节点则不需要考虑sub的双亲结点，直接将根节点设为sub，将sub的双亲结点设为空即可，若不为根节点则需要先用Pparent将parent的双亲结点保存，然后将parent的双亲结点设为sub,ran然后将根据parent的位置将sub与Pparent链接。然后更新parent的结点和sub的结点的平衡因子为0，此时左单旋就结束了。
2>：右单旋：右单旋与左单旋大致相似但是方向不一样。
左右单旋的情况是，parent结点的平衡因子为2且sub的结点平衡因子为1且符号与parent相同，就是说树的平衡严重偏向一边，需要用到单旋调节，而若是平衡不是偏得很严重，就用双旋处理。就是子树的平衡偏转与其根节点的平衡偏向不一样。
3>:右左双旋：顾名思义先右旋转在左旋转，对其parent的右子树进行一次右旋转，然后对其parent结点进行一次左旋转，因为右左旋转有两种情况所以需要根据情况来判断其中每个参与旋转的节点的平衡因子的更新情况。左右旋转同理。
需要注意的一点是判断插入位置平衡因子的BFmark需要提前保存，不然会影响判断。
标签：结点,parent,23,旋转,AVL,插入,查找,平衡,节点 From： https://www.cnblogs.com/qjwxlj/p/17348123.html