详解AVL树旋转调整过程

详解AVL树旋转调整过程

前言

AVL树，即平衡二叉树，是一种在搜索二叉树上进行改进的数据结构，搜索二叉树能够控制节点在树中位置的数据结构，能够做到建立数据的关联性。

对于单个元素搜索的一般场景下时间复杂度为$log_2N$,但是极端场景下：

搜索树的时间复杂度会退化到$O(log_2N)$

此时平衡二叉树被提出，能够在插入元素时动态地调整元素位置，使得二叉树的形状尽量“丰满”，达到左右子树较为平衡的状态，即左右子树高度差不超过1。

需要调整的四种状态

我们设置平衡因子bf对每个节点是否平衡进行判断，需要平衡的节点进行相应的操作，总结下来有四种情况需要进行调整。

左单旋

左单旋指的是在插入节点后parent的bf = 2,Cur的bf = 1的情况，具体来说，我们需要做的调整如下：

具体操作结合代码进行讲解：

详细代码

右单旋

右单旋指的是在插入节点后parent的bf = -2,Cur的bf = -1的情况，具体来说，我们需要做的调整如下：

详细代码

双旋->先左后右

双旋，也就是需要两次旋转才可以对树进行平衡，大体思路即对树进行两次旋转，先完成一个局部旋转，使整棵树的情况简单下来，再对整个数进行更改，先左后右实际上是新插入节点再较高左子树的右侧进行了插入，具体调整如下：

接下来结合代码进行具体讲解：

双旋->先右后左

双旋的第二种情况就是再右边高的子树左边进行插入，具体操作如下：

接下来结合具体代码进行分析

详细代码

注：以上所示图的仅为编号，相对位置关系仅在初始状况中成立

完整测试代码