AVL树介绍

AVL树分析

树

树（tree）是n（n>=0）个结点的有穷集。n=0时称为空树。在任意一个非空树中：

1. 每个元素称为结点（node）
2. 仅有一个特定的结点被称为根结点或树根（root）。
3. 当n>1时，其余结点可分为m（m≥0）个互不相交的集合T1，T2，……Tm，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作根的子树（subtree）。

 

AVL树概念

 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis。

AVL树特点

1. AVL树是一颗二叉搜索树。
2. AVL树每个节点的左右子树的高度只差最多为1，是一颗可以自动平衡的二叉树。

AVL树的概念介绍

 树的高度：结点的层次从根节点开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。

 平衡因子：每个结点的左右子树的高度之差的绝对值称为平衡因子。AVL树的平衡因子只有-1，0，1三种，如果是空节点，我们规定其高度为 -1，所以只有左子树，其平衡因子为1，只有右子树时，其平衡因子为-1。

AVL树的操作

 由于AVL树的插入和删除操作都是可能造成树的不平衡，因此需要自平衡，AVL树的自平衡是通过旋转操作来进行，通过旋转来改变一颗子树得分根，修改这个树的高度。以达到AVL树的第二个特点。

旋转

右旋(LL)

 在根节点的左孩子的左侧添加新节点 1 后，平衡因子从原来的 1 变为了 2，这时我们只需要对根节点 3 执行一次右旋操作树就平衡了。

 

 

左旋(RR)

 RR 型正好与 LL 型的互为镜像，如果向根节点的右孩子的右侧添加一个新节点（下图中的节点 3）后，平衡因子由 -1 变为 -2，导致树的不平衡，这时我们需要对根节点执行一次左旋操作。

 

 

先左后右(LR)

 如果往根节点的左孩子的右侧添加新节点（下图中的节点 2），平衡因子也会从 1 变为 2，但这里我们不能采用单次右旋，而是要先对根节点的左孩子执行一次左旋操作，使之变为 LL 型，然后再对根节点进行右旋。

 

 

先右后左(RL)

 RL 型与 LR 型也互为镜像，即如果将新节点（下图中的节点 2）插入到根节点的右孩子的左侧，平衡因子由 -1 变为 -2。同样，我们不能用一次左旋来使树重新平衡，而是先对根节点的右孩子执行一次右旋，变为 RR 型，然后再对根节点进行左旋。

 

 

    上述的四种情况都是基于两种基本操作：左旋和右旋。然而，我们讨论的并不是一般的情况。举个例子，如果要对下图中的根节点进行右旋，我们会发现根节点的左孩子的右子树不为空，这时该怎么办呢？我们知道，旋转之后的树必须保持二叉树的性质，所以我们可以让多余的右子树作为原根节点的左子树，使得原根节点的值还是大于被调整子树的所有节点的值。

 

 

 同理，下图也展示了左旋的一般情况，只是与右旋互为镜像操作。

 

 

搜索

  和二叉搜索树一样，AVL 树也是从根节点开始搜索，如果搜索的元素比根节点小，那么就从根节点的左子树中继续搜索，如果比根节点大，那么就从右子树中继续搜索，如果相等，则返回该节点，要是搜索到了叶子节点发现还是搜索失败，我们就返回NULL。

插入

  AVL 树的插入操作也跟二叉搜索树一样，先找到插入的位置，即通过搜索操作找到插入位点，然后创建一个新节点，最后父节点指向该新节点。但由于 AVL 树是一棵自平衡的树，所以每插入一个节点都会更新搜索过程中所经过节点的高度，如发现有节点的高度的绝对值大于等于 2，则采取相应的旋转操作使之保持平衡。