数据结构:AVL Tree

AVL树

定义:适度调整平衡的BST Balanced Binary Search Tree

如何改进二叉搜索树,使得其变得尽量平衡:

1.添加和删除无法限制,只能在这些操作之后进行改进

2.改进方法:在添加删除后,想办法让二叉树恢复平衡

截屏2022-01-16 下午12.15.46

3.如果一直调整,可以达到完全二叉树的平衡状态,但是系统消耗大,且可能会因此增加时间复杂度

–解决方案:适度调整BST

常见的BBST:AVL树、红黑树 (self-balanced search tree)

AVL树是一个自平衡二叉树

平衡因子(Balance Factor):某节点左子树高度-右子树高度

1.AVL树的平衡因子只可能是-1、0、1(每个节点的左右子树高度差不超过1)

2.搜索、添加、删除的time complexity是O(logn)(和完全二叉树高度一样

)截屏2022-01-16 下午12.29.29

20141201123218032

补充一种RL的情况

截屏2022-02-09 下午8.48.57

因为一个节点的添加,可能会导致所有祖先节点(除父节点外)的失衡

(如下图中13节点的添加导致BBST–>BST)

截屏2022-02-09 下午8.49.42
1
2
3
BBST的父节点、非祖先节点,都不会因为添加了一个节点而失衡
因为父节点可能没有子节点或者有一个子节点,再添加一个节点并不会导致平衡的坍塌
旋转都是以发现者的子树z

1.不平衡的"发现者"是Mar,”麻烦节点“Apr在发现者左子树的左边,因而叫LL插入,需要LL旋转

2.把被破坏者的左子树节点拎上来,而发现者作为儿子

3.RR插入:插入的节点在发现者节点的左边的左边

截屏2022-02-09 下午8.50.19
1
2
3
1.将发现者A的左节点B拎上来作为根节点把发现者放下去

2.发现者左子树B的右子树Br的东西放到发现者A节点的左边而发现者左子树的左子树不变
截屏2022-02-09 下午8.50.47

为了保持二叉树的性质,子树B过继给了节点5。

截屏2022-02-09 下午8.51.18
1
2
3
4
5
6
0.将发现者的左子树拎上来
1.g.left = p.right//把发现者左子树的右子树上的东西放到发现者的右子树上
2.p.right = g //把发现者放下去
3.让p成为这颗子树的根节点
4.注意维护gpT1//注意维护发现者、发现者的左子树及发现者的左子树的右子树
5.注意更新gp的高度//注意更新发现者、发现者左子树的高度

因为添加只会导致祖父节点发生失衡(即n、T0、T1、T2、T3都不会发生失衡,只有p、g会发生失衡)

所以移动p、g即可

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-16%20%E4%B8%8B%E5%8D%882.14.13.png

1.不平衡的"发现者"是Mar,”麻烦节点“Nov在发现者右子树的右边,因而叫RR插入,需要RR旋转(右旋转)

2.把被破坏者的右子树节点拎上来,而发现者作为儿子

3.RR插入:插入的节点在发现者节点的右边的右边

截屏2022-02-09 下午8.51.54

1.将发现者(A)的右节点(B)拎上来作为根节点

2.发现者右子树的左子树(BI)的东西放到发现者节点的右边

1
2
3
4
5
6
0.将发现者的右子树拎上来
1.g.right = p.left//把发现者左子树的右子树上的东西放到发现者的右子树上
2.p.left = g //把发现者放下去
3.让p成为这颗子树的根节点
4.注意维护gpT1的parent//注意维护发现者、发现者的右树及发现者的右子树的左左子树
5.注意更新gp的高度//注意更新发现者、发现者左子树的高度

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-16%20%E4%B8%8B%E5%8D%883.43.40.png

1.不平衡的"发现者"是May,”麻烦节点“Jan在发现者左子树的右子树上,因而叫LR插入,需要LR旋转

截屏2022-02-09 下午8.52.37
1
2
3
4
5
1.先将发现者的左子树B为选择中心进行右旋转将C转为B的根
如果麻烦节点CI在发现者左子树(B)的右子树(C)的左边(CI)则将其移动到发现者(A)左子树(B)的右边(CI)
否则保持不动
2.再按照LL的方法进行调整
    BI<B<CI<C<A<Ar

1.不平衡的"发现者"是Aug,”麻烦节点“Feb在发现者右子树的左子树上,因而叫RL插入,需RL旋转

截屏2022-02-09 下午8.53.14 截屏2022-02-09 下午8.54.06
1
2
3
4
5
1.先将发现者的右子树B为选择中心进行左旋转将C转为B的根
如果麻烦节点CI在发现者右子树(B)的左子树(C)的右边(图中未画出)则将其移动到发现者(A)右子树(B)的右子树的左边
否则保持不动
2.再按照LL的方法进行调整
  AI<A<CI<C<B<Br

在添加、删除后在对BST进行平衡调整,使得其成为AVL树

1
2
3
4
5
6
7
8
 0.创建AVL树类
 1.为AVL树创建构造器 this super 的使用
 2.为AVL树创建添加之后的操作》(afterAdd的方法但add操作是在bst中完成的而afterAdd要写在AVL里因为普通bst不需要此方法
   解决办法在BST的add中写入protected的afterAdd方法在AVL里override
   //@param 所添加的节点 插入位置:1.添加的是root2.添加的是普通节点
   protected void afterAdd(Node<E> node)
 3.在AVL中如何重写afterAdd(Node<E> node) 具体方法见平衡调整算法

截屏2022-02-09 下午8.54.41
1
2
3
4
5
6
7
8
9
 protected void afterAdd(Node<E> node)
平衡调整算法分析
   1 明确node是哪个节点--是新添加的node 要根据此node去查找是否祖父里面有没有失衡节点
   2 找哪个失衡节点--找高度最低的失衡节点并将其修复--由此所有失衡节点都会平衡
     2.1 如果node.parent....!= null 就一直往上找能进去这句的节点一定都是叶子节点的父亲及祖法们
          判断找到的node是否失衡见失衡判断算法见平衡因此算法))
            2.1.1 如果平衡 更新高度见更新高度算法
          2.2.2 如果不平衡 恢复平衡 之后break是高度最低的不平衡节点 恢复方法见恢复平衡算法 恢复完成后整颗树都再次恢复平衡 break即可
       2.2 否则就从node开始一直往上找都找不到失衡节点就return
1
2
3
4
5
//使用平衡因子进行失衡判断
private boolean isBalanced(Node<E> node)  -- 写在AVL中
{
        return Math.abs((AVLNode<E>node).balanceFactor()) <=1;
}
 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
private int balanceFactor() --写在AVLNode中
/**
问题一:在avl树的node里设置height属性(方便查找balance factor),因为在BST里没必要维护height属性
解决办法:在avl树里新建一个node内部静态类(扩展了BT的静态内部类Node<E>)---设置为静态,切断内外关系
       并super父类的构造器
       
*/
/**
问题二:目前的add方法是在BST里创建的BT的Node,但是我们在AVL里面想要获得的是AVLNode
解决办法:在BT里面加入方法protected void creatNode(E element , Node<E> parent)
        在BST的add方法里使用该方法
        在AVL里重写该方法
        
       AVLTree<Integer> avl = new AVLTree<Integer>();
            //在调用add方法时 会调用到creatNode根据多态(avl)会调用在AVLTree里重写的createNode方法
            //afterAdd也同理
       avl.add(***);
*/
//在BT里
protected void createNode(E element , Node<E> parent)
{
  return new Node(element,parent);
}
//在AVL里 这是保证之后强转成功的关键
@override
protected void createNode(E element , Node<E> parent)
{
  return new AVLNode<E>(element, parent)
}

/**
问题三:将平衡因子算法写在哪?如何写?-- 写在AVLNode里
如何写?
1.获取左子节点的高度
2.获取右子节点的高度
3.左子节点的高度-右子节点的高度
*/


leftHeight-rightHeight
 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
使用两个方法是为了看起来比较好看而起
private void updateHeight() --在AVLNode中
private void updateHeight(Node<E> node)-- 写在AVL中

  
//如果不对生成节点的高度进行更新,高度将一直保持为0,由此我们要使用高度更新算法
//每次生产一个新的节点,我们就应该对其高度进行更新因此 我们将高度更新算法写在afterAdd中 而afterAdd算法是
//套在BST的Add中的 这样,我们就可以在添加过程中及时更新AVLNode的高度(updateHeight)
//可以说,更新高度算法是非常巧妙的设计,既防止了多余的递归,由可以让每个父亲和祖父的高度都得到更新 因为在判断失衡的时候,只要不失衡都会一直往上找
   /**
   更新自己的高度 public void updateHeight()
   将AVLNode的height属性默认赋值为1,因为刚加入的节点一定为叶子节点
   算法分析:
   1.查看左子节点的高度
   2.查看右子节点的高度
   3.返回自己的高度 = Math.max(左子节点的高度,右子节点的高度) +1;
   */
  
  /**
  更新某个节点的高度
  */
 private void updateHeight(Node<E> node)
{
  (AVLNode)node.updateHeight
}
  
 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
private void reBalance(Node<E> grand)
//来到这里,说明是被发现的高度最低的不平衡节点--grand
//找到高度最低的不平衡节点后,如何找他的p和n--找grand高度最高的子节点作为parent,找parent子节点中高度最高的节点做为n 因为失衡导致的 -- 使用找最高子节点算法 可以用反正法 假设grand高度最高的子节点不是parent 那么不平衡肯定就不会在parent这支上
/**
算法分析:
1.先找到grand的parent和node
2.判断是LL LR RR RL
3.分别使用LL RR算法到LL LR RR RL
4.不同情况使用L或者R算法
5.对于为什么LR RL要使用旋转两次见下图情况6 8
*/
private void reBalance(Node<E> node)
{
    //grand parent node 方便下一步操作
        AVLTree.avlNode<E> grandNode = avlNode;
        AVLTree.avlNode<E> parentNode = grandNode.tallerChild();
        AVLTree.avlNode<E> node = parentNode.tallerChild();
        //L
        if (grandNode.left == parentNode)
        {
            //LL
            if (parentNode.left == node)
            {
                clockwiseRotation(grandNode);
            }
            //LR
            if (parentNode.right == node)
            {
                unclockwiseRotation(parentNode);
                clockwiseRotation(grandNode);
            }
        }
        //R
        else
        {
            //RR
            if (parentNode.right == node)
            {
                unclockwiseRotation(grandNode);
            }
            //RL
            if (parentNode.left == node)
            {
                clockwiseRotation(parentNode);
                unclockwiseRotation(grandNode);
            }
        }

}

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/123.jpeg

这里使用统一旋转算法实现

 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
/**
     * 恢复平衡算法
     * @param avlNode
     */
    private void reBalance2(AVLTree.avlNode<E> avlNode)
    {
        //grand parent node 方便下一步操作
        avlNode<E> grandNode = avlNode;
        avlNode<E> parentNode = grandNode.tallerChild();
        avlNode<E> node = parentNode.tallerChild();
        //L
        if (grandNode.left == parentNode)
        {
            //LL
            if (parentNode.left == node)
            {
                //根据笔记中的图写出
                Rotation(node.left,node,node.right,parentNode,parentNode.right,grandNode,grandNode.right,grandNode);
            }
            //LR
            if (parentNode.right == node)
            {
                Rotation(parentNode.left,parentNode,node.left,node,node.right,grandNode,grandNode.right,grandNode);
            }
        }
        //R
        else
        {
            //RR
            if (parentNode.right == node)
            {
                Rotation(grandNode.left,grandNode,parentNode.left,parentNode,node.left,node,node.right,grandNode);
            }
            //RL
            if (parentNode.left == node)
            {
                Rotation(grandNode.left,grandNode,node.left,node,node.right,parentNode,parentNode.right,grandNode);
            }
        }

    }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
private AVLNode tallerChild()
/**
算法分析:
1.获取左子节点的高度
2.获取右子节点的高度
3.如果左子节点高度>右子节点的高度 返回左子节点
4.如果左子节点高度<右子节点的高度 返回右子节点
否则我是我父亲的什么节点 我就返回我的什么儿子给tallerChild -- 使用isleftChild、isrightChild进行判断ƒ
*/
private AVLNode tallerChild() -- 写在AVLNode里
{
              int leftHeight = left == null? 0 : ((avlNode<E>)left).height;
            int rightHeight = right == null? 0 : ((avlNode<E>)right).height;
            if (leftHeight>rightHeight) return (avlNode<E>) left;
            if (leftHeight<rightHeight) return (avlNode<E>) right;
            //如果两边高度一样高 我是我父亲的什么节点,我就返回我的什么儿子给tallerchild
            return (avlNode<E>) (isleftChild()? left : right);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**

*/
protected boolean isleftChild()
{
        return parent!=null && this = this.parent.left;
}

protected boolean isrightChild()
{
        return parent!=null && this = this.parent.right;
}

0.获取parentNode和T1

1.更新grandNode的left为T1

  1. 更新parent的right为grandNode属性

  2. 让parent成为根节点(更新parentNode的parent属性 更新grandgrandNode的left or right属性)

  3. 在T1不为空的前提下,更新T1的parent属性

  4. 更新grandNode的parent属性

  5. 更新grandNode、parentNode的高度

  6. parentNode.tallerChild的高度不需要更新,因为node高度发生变化的时候,树还在处于平衡状态,被平衡调整算法的2.1.1更新

     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
    
        private void clockwiseRotation(Node<E> grandNode)
        {
            //能进来 说明parent一定是LL
            Node<E> parentNode = grandNode.left;
            Node<E> T1 = parentNode.right;
            grandNode.left = T1;
            parentNode.right = grandNode;
            Node<E> grandgrandParent = null;
            if (grandNode.parent!=null)
            {
                //如果grandNode的父亲不为null
                grandgrandParent = grandNode.parent;
            }
    
            //让parentNode成为子树的根节点 更新parentNode的parent属性
            parentNode.parent =grandgrandParent;
    
            //更新grandgrandParent的left或者right
            if (grandNode.isleftChild())
                grandgrandParent.left = parentNode;
            else if (grandNode.isrightChild())
                grandgrandParent.right = parentNode;
            else
            {
                root = parentNode;
            }
    
            //更新T1(笔记中情况2中的45)
            if ( T1 != null)
            {
                T1.parent = grandNode;
            }
            grandNode.left = T1 ;
    
            //更新grandNode的parent属性
            grandNode.parent = parentNode;
            //只有parentNode和grandNode高度发生了变化 因此需要更新高度
            updateHeight((avlNode<E>) grandNode);
            updateHeight((avlNode<E>) parentNode);
        }
    
    截屏2022-02-09 下午8.59.52

0.获取parentNode和T2

1.更新grandNode的left为T2

  1. 更新parent的right为grandNode属性

  2. 让parent成为根节点(更新parentNode的parent属性 更新grandgrandNode的left or right属性)

  3. 在T2不为空的前提下,更新T2的parent属性

  4. 更新grandNode的parent属性

  5. 更新grandNode、parentNode的高度

  6. parentNode.tallerChild的高度不需要更新,因为node高度发生变化的时候,树还在处于平衡状态,被平衡调整算法的2.1.1更新

     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
    
        //RR
        private void unclockwiseRotation(Node<E> grandNode)
        {
            //
            Node<E> parentNode = grandNode.right;
            Node<E> T2 = parentNode.left;
            grandNode.right = T2;
            parentNode.left = grandNode;
    
            Node<E> grandgrandNode = null;
            if (grandNode.parent!=null)
            {
                grandgrandNode = grandNode.parent;
            }
    
            //更新parentNode的parent字段
            parentNode.parent = grandNode.parent;
            //更新grandgrandParent的left or right字段
            if (grandNode.isrightChild())
            {
                grandgrandNode.right = parentNode;
            }
            else if (grandNode.isleftChild())
            {
                grandgrandNode.left = parentNode;
            }
            else
            {
                root = parentNode;
            }
    
            //更新T1的parent字段
            if (T2 != null)
            {
                T2.parent = grandNode;
            }
    
            //更新grandNode的parent字段
            grandNode.parent = parentNode;
    
            //两次更新顺序不能颠倒
            updateHeight((avlNode<E>) grandNode);
            updateHeight((avlNode<E>) parentNode);
    
        }
    

    https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-19%20%E4%B8%8B%E5%8D%881.21.47.png

1.无论是LL、RR、LR、RL恢复平衡后,最终都会恢复一样的子树

  • 根据二叉搜索树中序遍历的性质,所有AVL失衡时的所有节点,从左到右是逐渐增大的

  • 恢复平衡后结构一样:

d都会成为子树的根节点

a、b、c都会独立成一颗子树(d的左边的家伙;且中间节点b成为子树根节点) e、f、g会独立成另一颗子树(d的右边的三个家伙;且中间节点b成为子树根节点)

  • 只要找到四种情况对应的a、b、c、d、e、f、g就可以恢复平衡
截屏2022-02-09 下午9.00.42
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void rotate(Node<E>a,Node<E>b,Node<E>c,
                   Node<E>d,
                   Node<E>e,Node<E>f,Node<E>g
                   Node<E>r)//r为该子树中根节点是谁b or f
/**
算法分析:
让d成为子树的根节点
1.更新d的parent属性
2.更新r的父亲的left or right属性
a-b-c
3.更新b的left属性 ,并更新a的parent属性 -- a可能为空
4.更新b的right属性,并更新c的parent属性 --c可能为空
5.更新b的高度
e-f-g
6.更新f的left属性,并更新e的parent属性
7.更新f的right属性,并更新g的right属性
8.更新f的高度
b-d-f
9.更新d的left属性,并更新b的parent属性
10.更新d的right属性,并更新f的parent属性
11.更新d的高度
*/

AVL删除算法afterRemove

1.删除节点只可能会导致父节点失衡或者祖先节点失衡

原因:当删除一个节点导致失衡时,先假设A为导致失衡的第一个节点,A失衡,说明A的左右子树肯定不平衡,BalanceFactor变为了2,但也说明A的高度不会受到影响(因为A的高度由度较高的子树决定,删除的节点肯定在较短的子树上才会发生失衡),所以A的父亲的高度也一定不会受到影响。

父节点失衡:

截屏2022-01-19 下午12.31.44

祖先节点(11)失衡:

截屏2022-01-19 下午12.39.22

afterRemove的插入位置

1.要在remove算法将节点删除后(node.parent不再指向node)

2.如果是度为2的节点删除的是前驱或者后继节点

恢复平衡可能导致更高层的祖先节点失衡

不会导致祖先节点失衡的情况(p的高度没有发生改变)

截屏2022-01-19 下午2.10.16 截屏2022-01-19 下午2.10.56

可能会导致祖先节点发生失衡的情况(p高度减一)

截屏2022-01-19 下午2.12.24

假设旋转钱大红圈的高度比g高了一 旋转完后p高度又减一了 所有旋转之后导致了不平衡的出现

截屏2022-01-19 下午2.13.11

总结

截屏2022-01-19 下午12.40.57