树的旋转和AVL树

AVL树是一种自平衡二叉搜索树，由. M. Adelson-Velsky和E. M. Landis，在他们1962年的论文《An algorithm for the organization of information》中发表。名声很大，就算自己没写过，也应该都听说过。这两天也是重新看了一下，记录一些理解。

AVL树简介

AVL树首先是一个二叉搜索树，然后AVL树中任何两个子树的高度差最大不超过1，所以又被成为平衡高度树。ALV树的插入，删除，查找的时间复杂度无论是平均还是最坏情况均为。为了控制二叉树的平衡，引入了平衡因子的概念：

平衡因子：一般定义一个结点的左子树与右子树的高度之差，为该结点的平衡因子；即 结点平衡因子 = 左子树高度 - 右子树高度

也有说是右结点与左结点之差的说法，与上述相反，本文有第一种说法为准。当一棵二叉树的所有结点的平衡因子都在-1,0,1之间时，则认为这棵二叉树是一棵AVL树。当结点的平衡因子为+1时，表示以该结点为根结点的子树是左倾斜的；相反，当结点的平衡因子为-1时，表示以该结点为根结点的子树为右倾斜的。当树不平衡时则需要进行树的旋转，来使二叉树保持高度平衡。

AVL树的旋转

为了理解树的旋转，需要先整理清楚二叉搜索树的特性，即根结点的左子树全部小于它，而右子树全部大于它。那么对左子树的任何一个节点，它的父节点和右结点都大于自己；换种理解就是，父结点同时也可以作为自己的右结点。换做右子树同理，直接上图

关于树的旋转，分为左旋和右旋；一般认为旋转的子树在哪边则旋转方向即是哪边，即倾斜方向就是旋转方向（也有定义相反的结果，这个不重要）

树的左旋：子树为左倾斜，进行左旋转。以子树的根结点为根（root），根的左子结点为轴（pivot）；root 变为 pivot的右结点，而pivot的右结点则变成 root 的左结点。

树的右旋：子树为右倾斜，进行右旋转。以子树的根结点为根（root），根的右子结点为轴（pivot）；root 变为 pivot的左结点，而pivot的左结点则变成 root 的右结点。

动画展示，图像是网上找的，这GIF图太难了整了，尝试肝了几张放弃。图中的左旋和右旋与本文的定义相反，但是不重要，理解过程就行。