挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

背景 :

AVL 是一种绝对平衡的二叉树,。这里的绝对平衡指的是 任意节点的左右字树高度差最大为1。 一旦发现左右子树高度差大于1, 则启动平衡维护机制(左旋, 右旋) 来强制维护二叉树的平衡。也正是因为AVL是一棵绝对平衡的二叉树, 所以维护平衡的代价特别大。对于多查询, 少增删的场景,可以大胆使用AVL。其他场景建议使用 红黑树。完整代码请访问我的 Github仓库。 这篇技术贴力争全网最详细 讲清讲透 AVL ,欢迎大家留言讨论!!!

什么是AVL?

AVL是一棵平衡的二分搜索树。这里所说的平衡是指每一个节点的左右子树高度差最大为1。比如下面这棵二分搜索树,就是一棵AVL,节点旁的数字表示当前节点的高度。为了简单表示,若节点左右孩子为NULL, 我们没有将NULL画出来。

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

我们可以看出看,所有节点左右子树的高度差最大为1,这样的二分搜索树就是AVL。

实现AVL

构造方法

AVL的构造方法,几乎和BST(二分搜索树)一模一样,唯一的区别在于每一个节点额外增加了一个高度 height 属性.

public class AVLTree<K extends Comparable<K>,V>  {

    private class Node{
        public K key;
        public V value;
        public Node left,right;
        public int height;//以当前node为根的树的高度

        public Node(K key, V value){
            this.key=key;
            this.value=value;
            left=null;
            right=null;
            height=1;
        }

        public Node(){
            this.key=null;
            this.value=null;
            left=null;
            right=null;
        }
    }

    private Node root;
    private  int size;

    public AVLTree(){
        root=null;
        size=0;
    }
    
}

我们额外定义了一个概念: 平衡因子,用于表示一个节点的左右子树高度之差。若高度只差大于1,我们需要通过 左旋 和 右旋 操作对树进行维护平衡. 为此,额外定义了两个方法: getHeight(Node node) 获取节点高度 与 private int getBalanceFactor(Node node) 获取平衡因子。

//获取以node为根的树的高度
private int   getHeight(Node node){
   if (node==null)
       return 0;
   return node.height;
}

//计算平衡因子,定义:左子树高度-右子树高度
private int getBalanceFactor(Node node){
   if (node==null)
       return 0;
   return getHeight(node.left)-getHeight(node.right);
}

以下方法和BST完全一样, 这里就不再细讲了。

  1. int getSize()
  2. bool isEmpty()
  3. bool contains (K key)
  4. V get (K key)
  5. Node getNode(Node node, K key)
  6. void set (K key, V newNode)
  7. minimum( Node node)

平衡树的维护机制: 右旋 和 左旋

这一部分,我将深入介绍 AVL 的核心部分,如何维护树的平衡。 不平衡的情况, 一共有4种,分别是 LL,RR, LR和 RL。针对这4种情况,都有特定的方法进行平衡维护。

LL

LL 表示 不平衡节点 y 的平衡因子为 2 且 y 的左孩子 x 节点的平衡因子 >=0。此时又可以分成两种情况:

  • y 节点的左孩子 x 的平衡因子为1
  • y 节点的右孩子 x 的平衡因子为 0

无论是上述哪种情况都可以通过 对 y 节点 右旋 达到平衡

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

根据上图,我们可以很轻易地写出 右旋 操作的代码

private Node rightRotate(Node y){
    Node x=y.left;
    Node T1=x.left;
    Node T2=x.right;
    Node T3=y.right;

    //右旋转
    x.right=y;
    y.left=T2;

    //更新height
    //因为x随y改变而改变,所以要先更新y
    y.height=1+Math.max(getHeight(T2),getHeight(T3));
    x.height=1+Math.max(getHeight(T1),getHeight(y));

    return x;
}

RR

RR 表示 不平衡节点 y 的平衡因子为 – 2 且 y 的右孩子 x 节点的平衡因子 <=0。此时又可以分成两种情况:

  • y 节点的右孩子 x 的平衡因子为 – 1
  • y 节点的右孩子 x 的平衡因子为 0

无论是上述哪种情况都可以通过对 y 节点 左旋 达到平衡

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

根据上图,我们可以很轻易地写出 左旋 操作的代码

private Node leftRotate(Node y) {
    Node x=y.right;
    Node T1=x.right;
    Node T2=x.left;
    Node T3=y.left;

    //左旋转
    x.left=y;
    y.right=T2;

    //更新height
    //因为x随y改变而改变,所以要先更新y
    y.height=1+Math.max(getHeight(T3),getHeight(T2));
    x.height=1+Math.max(getHeight(y),getHeight(T1));

    return x;
}

LR

LR 表示 不平衡节点 y 的平衡因子为 -2 且 y 的左孩子 x 节点的平衡因子 =- 1。这个条件包括多种情况(下图中的T2L子树和T2R子树的高度有多种情况), 但都可以通过 左旋 再 右旋 完成平衡化。具体操作如下图:

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

RL

RL 表示 不平衡节点 y 的平衡因子为 2 且 y 的右孩子 x 节点的平衡因子 =1 1。这个条件包括多种情况(下图中的T2L子树和T2R子树的高度有多种情况), 但都可以通过 右旋 再 左旋 完成平衡化。具体操作如下图:

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

什么时候要维护平衡?

很显然,只有 增加节点 和 删除节点的时候,树的高度才会改变,才可能打破平衡。

增加节点

add(K key, V value) 方法

public void add(K key, V value) {
    root=add(root, key,value);
}

公有的 add(K key, V value)方法和BST中一样,区别在于私有方法 add( Node node, K key, V value)。

private Node add(Node node, K key, V value){
    if (node==null){
        size++;
        return new Node(key,value);
    }

    if (key.compareTo(node.key)==0){
        node.value=value;
    }else if (key.compareTo(node.key)<0 ){
        node.left=add(node.left,key,value);
    }else {
        node.right=add(node.right,key,value);
    }

    //维护平衡
    return maintainBalance(node);

}

整个add(Node node, K key, V value)函数与 BST 中的方法几乎完全相同,区别只在于每一次当前节点向上return 之前需要调用 maintainBalance(Node node)方法,确保每一个节点在return之前是平衡的。 这样一层层return上去,整个树也就平衡了

maintainBalance(Node node) 方法,维护以node为根节点的树的平衡

private  Node maintainBalance(Node node){

    //更新height
    node.height=1+Math.max(getHeight(node.left),getHeight(node.right ));

    //计算平衡因子
    int balanceFactor=getBalanceFactor(node);


    //若当前节点的平衡因子绝对值超过1,则需要平衡维护
    //LL
    if (balanceFactor>1 && getBalanceFactor(node.left)>=0 ){
        return rightRotate(node);
    }

    //LR
    if (balanceFactor>1 && getBalanceFactor(node.left)<0 ){
        node.left=leftRotate(node.left);
        return rightRotate(node);
    }

    //RR·
    if (balanceFactor<-1 && getBalanceFactor(node.right)<=0 ){
        return leftRotate(node);
    }

    //RL
    if (balanceFactor<-1 && getBalanceFactor(node.right)>0 ){
        node.right=rightRotate(node.right);
        return leftRotate(node);
    }

    //已经平衡,无需维护
    return node;

}

maintainBalance(Node node) 方法的逻辑也非常简单,首先计算更新节点 node 高度,计算平衡因子,判断当前节点 是否从 处于 LL, LR, RR, RL 四种状态。若处于四种状态的一种,则进行 左旋 , 右旋 维护平衡,然后return node。若不处于在四种状态,说明当前节点 node 已经处于平衡状态,无需维护,直接return。

删除最小节点

removeMin(Node node) 方法删除最小节点

private Node removeMin( Node node){
    if (node.left==null){
        Node rightNode=node.right;
        node=null;
        size--;
        return rightNode;
    }
    node.left=removeMin(node.left);

    //node的左子树被改变了,需要维护node的平衡
    return maintainBalance(node);
}

removeMin(Node node) 方法和BST中的操作几乎完全相同, 只不过在每一次将当前节点 返回给上一层节点之前,都需要调用 maintainBalance(Node node)维护平衡。这样一层层return上去,整一棵树就是平衡的了。

删除节点

remove(K key) 方法

public V remove(K key) {
    Node delNode=getNode(root,key);
    if (delNode!=null){
        root=remove(root,key);
        return delNode.value;
    }else {
        return null;
    }
}

公有方法 remove(K key) 和BST 中的完全相同,区别在于 私有的 remove(Node node, K key)方法 由于掘金不支持行号,所以就从我的gitbook上面截图了。

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

先看17-38行代码,也就是 删除节点 时的代码:

  1. 19-23行,若 待删除节点的左孩子为NULL, 则删除操作和BST中的完全一样,因为以右孩子为根的子树并没有增加或删除节点,以右孩子为根的子树仍然是平衡的,直接return右孩子,交给上一层节点处理。
  2. 24-28行,若 待删除节点的右孩子为NULL, 则删除操作和BST中的完全一样,因为以左孩子为根的子树并没有增加或删除节点,以左孩子为根的子树仍然是平衡的,直接return左孩子,交给上一层节点处理。
  3. 31-37行,若待删除节点的左右孩子都不为NULL, 需要找到待删除节点的继任 succesor,随后将待删除节点的的右孩子中最小节点删去 ,最后将succesor代替待删除节点,返successor即可。因为实际上唯一的删除操作发生在 removeMin(Node node) 方法中,而removeMin(Node node)方法又已经维护了平衡,所以这一部分不需要额外维护平衡。

再来看第8-16行代码 也就是如何处理return上来的节点。只要return上来的子树发生了改变,那么当前节点 node 的平衡就有可能被打破。所以在将当前节点 node 返回给上一层节点时,需要维护以当前节点node为根节点的树的平衡,然后才能返回。

至此,我们已经实现了一个 AVL 平衡树的增,删,改,查的所有基本功能。