数据结构之－平衡二叉树(AVL)

背景

不同结构的二叉查找树，查找效率有很大的不同。如何解决这个问题呢？关键在于如何最大限度的减小树的深度。正是基于这个想法，平衡二叉树出现了。

前言

平衡二叉搜索树（英语：Balanced Binary Tree）是一种结构平衡的二叉搜索树。它能在O(log n)时间内完成插入、查找和删除操作。它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子）不超过1。也就是说平衡二叉树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度），最早被发明的平衡二叉搜索树为AVL树。

常见的平衡二叉搜索树有：

AVL树
红黑树
Treap
节点大小平衡树

如何使二叉查找树在添加数据的同时保持平衡呢？基本思想就是：当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。所谓最小不平衡子树指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

操作

１、查找操作

　　平衡二叉树的查找基本与二叉查找树相同。

２、插入操作

　　在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。那么调整不平衡树的基本方法就是： 旋转。

失衡情况分析

在平衡二叉树中，当我们插入新的元素时，为了保证二叉搜索树的特性，很容易导致某些结点失衡，即该结点的平衡因子大于1。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

所谓的左旋和右旋都是以子树为原点的：如b是a的子树，那么旋转就围绕b来进行。
如果b是a的左子树，那么就围绕b将a向右旋转，看着就像是a直接掉下来了，掉成了b的右子树。
如果b是a的右子树，那么就围绕b将a向左旋转，看着就像是a直接掉下来了，掉成了b的左子树。

四种失衡情况

　而在二叉树中，任意结点孩子最多只有左右两个，而且导致失去平衡的必要条件就是当前结点的两颗子树的高度差等于2。因此，对于被破坏平衡的节点 a 来说致使失衡的插入操作有以下4中，其中左左和右右是只需要一次旋转，而左右和右左需要两次旋转。

四种失衡情况
插入方式	描述	旋转方式
LL	在结点的左子树的左子树插入元素	右旋转
RR	在结点的右子树的右子树插入元素	左旋转
LR	在结点的左子树的右子树插入元素	先左旋后右旋
RL	在结点的右子树的左子树插入元素	先右旋后左旋

四种失衡情况的旋转策略

1. LL (左左) 模式　右旋转

1-1左左模式和1-4右右模式只需要旋转一次，其中旋转的方式是一样的，而旋转方向不同而已，下面拿一个左左的模式：数据结构之－平衡二叉树(AVL)

数据结构之－平衡二叉树(AVL) 　　由于在parent的左孩子subL的左子树上插入节点20，使Parent的平衡因子由-1增至-2而失去平衡，所以是左左模式，即需要进行右旋，右旋的时候将节点subL作为根节点，节点Parent绕节点subL向右边旋转成为节点subL的右子节点，并且将节点subLR和节点subL的连接断开，然后再作为节点Parent的左子节点，旋转完成。