AVL 平衡树

AVL平衡树，每个节点的左右子树高度差最大为1

什么是AVL?

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

我们可以看出看，所有节点左右子树的高度差最大为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;
    }
    
}

getHeight(Node node) 获取节点高度 与 private int getBalanceFactor(Node node) 获取平衡因子

我们额外定义了一个概念： 平衡因子，用于表示一个节点的左右子树高度之差。若高度只差大于1，我们需要通过 左旋 和 右旋 操作对树进行维护平衡

//获取以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 的核心部分，如何维护树的平衡。

LL

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

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

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

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

rightRotate(Node y) 对 节点 y 进行右旋

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

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 节点 左旋 达到平衡

lefttRotate(Node y) 对 节点 y 进行左旋

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

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子树的高度有多种情况)， 但都可以通过 左旋 再 右旋 完成平衡化。具体操作如下图:

RL

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

什么时候要维护平衡？

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

增加节点

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)方法

//从以node为根节点的子树中删除,并返回node
private  Node remove(Node node, K key){
    //需要删除的节点不存在, return NULL
    if (node==null){
        return null;
    }

    if (key.compareTo(node.key)<0){
        node.left=remove(node.left,key);
        //node的左子树平衡可能被破坏了
        return maintainBalance(node);

    }else if (key.compareTo(node.key)>0){
        node.right=remove(node.right,key);
        //node的右子树平衡可能被破坏了
        return maintainBalance(node);

    }else {//key==node.key 找到了被删除的节点

        if (node.left==null){
            Node rightNode=node.right;
            node=null;
            size--;
            return rightNode;
        }else if (node.right==null){
            Node leftNode=node.left;
            node=null;
            size--;
            return  leftNode;
        }else {
            //找到待删除节点右子树中最小的节点,替代待删除节点的位置
            Node successor=minimum(node.right);
            successor.right=removeMin(node.right);//已经size--了
            successor.left=node.left;
            node=null;
            //successor在removeMin中删掉的时候已经维护了平衡
            //successor替换被删去的node的位置,就不用再维护平衡了,
            return  successor;
        }
    }

}

先看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 平衡树的所有重要功能。AVL 一般不会单独暴露给用户，而是以 Map (称为映射或字典) 或 Set (称为集合)的方式给用户调用。后面将会讲解如何用AVL二分搜索树实现一个Map 和一个Set.

PreviousBST Map & SetNextAVL Map & Set

Last updated

Was this helpful?