数据结构:AVL树(进击的Java新人Week.6学习笔记)

Posted on |

Author: Mike

问题背景

时间复杂度

image

  • 平衡二叉树基于二叉查找树的特性，在查找的过程中，在每一层只会访问一个结点，也即平衡二叉树的时间复杂度与树的高度有关。
    对于一颗 满二叉树，时间复杂度为

image

故 O(n) = logN;

  • 树的层数越少，查找数据的平均查找时间就会越少

    平衡二叉树是具有以下性质的二叉查找树：对于树中的任意一个结点，都有该结点的左子树的高度与右子树的高度之差的绝对值小于2。与普通的BST相比，AVL树只是多定义了旋转操作，使得当左右子树的高度差的绝对值大于或者等于2时，平衡树可以自动地进行树形调整，以重新满足上述性质。

存在的问题

当所给予的关键字序列是有顺序的时候，将会出现如下尴尬的二叉树。树的结构会变为单向左子树或者单向右子树，二叉树退化为单向链表，时间复杂度为 O(n)，
image

结论

尽可能降低树的高度，主要是通过二叉树的旋转来达到降低树高度的目的，也就是接下来讨论的内容。

旋转

先来看几个概念

平衡因子

某结点的 左子树 与 右子树 的高度(深度) 差 即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。
举例子如下, 结点旁边数据即为平衡因子

image

最小不平衡子树

最小不平衡子树以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。

结点失衡

调整失衡结点的手段为旋转操作，一共有日下四种旋转

  • LL 在结点A的左孩子（L）的左子树（L）插入新结点导致不平衡 –> LL单右旋操作
    image

  • RR 在结点A的右孩子（R）的右子树（R）插入新结点导致不平衡 –> RR单左旋操作
    image

  • LR 在结点A的左孩子（L）的右子树（R）插入新结点导致不平衡 –> LR旋转。
    可以先假设在D结点有一个右孩子，为null，也即虚构的右孩子，由此可见 LR 旋转 = LL旋转 + RR旋转

image

具体例子

image

  • RL 在结点A的右孩子（R）的左子树（L）插入新结点导致不平衡 –> RL旋转，与LR旋转的理论类似，RL 旋转 = RR旋转 + LL旋转

image

具体例子
image

操作

平衡二叉树的增删查改操作
https://zhuanlan.zhihu.com/p/25320155?refer=hinus

结点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
public class AVLNode<T extends Comparable> {
    public AVLNode<T> left;
    public AVLNode<T> right;
    public T data;
    public int height;

    public AVLNode(T data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

LL

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
     * 左左单旋转(LL旋转) w变为x的根结点, x变为w的右子树
     *
     * @param x
     * @return
     */
    private AVLNode<T> singleRotateLeft(AVLNode<T> x) {
        //把w结点旋转为根结点
        AVLNode<T> w = x.left;
        //同时w的右子树变为x的左子树
        x.left = w.right;
        //x变为w的右子树
        w.right = x;
        //重新计算x/w的高度
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        w.height = Math.max(height(w.left), x.height) + 1;
        return w;//返回新的根结点
    }

RR

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
     * 右右单旋转(RR旋转) x变为w的根结点, w变为x的左子树
     *
     * @return
     */
    private AVLNode<T> singleRotateRight(AVLNode<T> w) {

        AVLNode<T> x = w.right;

        w.right = x.left;
        x.left = w;

        //重新计算x/w的高度
        x.height = Math.max(height(x.left), w.height) + 1;
        w.height = Math.max(height(w.left), height(w.right)) + 1;

        //返回新的根结点
        return x;
    }

LR

image

1
2
3
4
5
6
7
8
9
10
/**
 * 左右旋转(LR旋转) x(根) w y 结点 把y变成根结点
 * @return
 */
private AVLNode<T> doubleRotateWithLeft(AVLNode<T> x){
    //w先进行RR旋转
    x.left=singleRotateRight(x.left);
    //再进行x的LL旋转
    return singleRotateLeft(x);
}

RL

image

1
2
3
4
5
6
7
8
9
10
11
/**
 * 右左旋转(RL旋转)
 * @param w
 * @return
 */
private AVLNode<T> doubleRotateWithRight(AVLNode<T> x){
    //先进行LL旋转
    x.right=singleRotateLeft(x.right);
    //再进行RR旋转
    return singleRotateRight(x);
}

插入

与BST（二叉查找树）的插入实现原理一样，使用递归算法，根据值大小查找到插入位置，然后进行插入操作，插入完成后，我们需要进行平衡判断，评估子树是否需要进行平衡修复，需要则利用上述的四种情景套入代码即可，最后要记得重新计算插入结点路径上的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* 插入方法
* @param data
*/
@Override
public void insert(T data) {
   if (data==null){
       throw new RuntimeException("data can\'t not be null ");
   }
   this.root=insert(data,root);
}

private AVLNode<T> insert(T data , AVLNode<T> p){

   //说明已没有孩子结点,可以创建新结点插入了.
   if(p==null){
       p=new AVLNode<T>(data);
   }else if(data.compareTo(p.data)<0){//向左子树寻找插入位置
       p.left=insert(data,p.left);

       //插入后计算子树的高度,等于2则需要重新恢复平衡,由于是左边插入,左子树的高度肯定大于等于右子树的高度
       if(height(p.left)-height(p.right)==2){
           //判断data是插入点的左孩子还是右孩子
           if(data.compareTo(p.left.data)<0){
               //进行LL旋转
               p=singleRotateLeft(p);
           }else {
               //进行左右旋转
               p=doubleRotateWithLeft(p);
           }
       }
   }else if (data.compareTo(p.data)>0){//向右子树寻找插入位置
       p.right=insert(data,p.right);

       if(height(p.right)-height(p.left)==2){
           if (data.compareTo(p.right.data)<0){
               //进行右左旋转
               p=doubleRotateWithRight(p);
           }else {
               p=singleRotateRight(p);
           }
       }
   }
   else
    ;//if exist do nothing
   //重新计算各个结点的高度
   p.height = Math.max( height( p.left ), height( p.right ) ) + 1;

   return p;//返回根结点
}