算法与数据结构系列之[平衡二叉树-AVL树-上]

1.问题概述

我们在介绍二分搜索树的时候提到时间复杂度为O(logn),但是这并不是绝对的,有些时候树可能退化为链表,时间复杂度回到O(n)级别,所以为了性能考虑,应尽量避免这种退化,这就用到了平衡树。

算法与数据结构系列之[平衡二叉树-AVL树-上]
2.什么是平衡二叉树

平衡二叉树的定义是,对于任意一个节点,左子树和右子树的高度差不能超过1,且平衡二叉树的高度和节点的数量之间的关系一是O(logn)的。我们前面介绍的满二叉树、完全二叉树和线段树都是平衡二叉树,如下图中的这棵二叉树看似不太像平衡二叉树,但它满足平衡二叉树的定义,根节点的左子树的高度3,有子树的高度2,高度差为1;8的左子树的高度为2,右子树的高度为1,高度差为1;5的左子树的高度为1,右子树高度为0,高度差为1;18的左子树高度为1,右子树高度为0,高度差为1;4,11,17都是叶子节点,其没有左子树和右子树,高度差为0,所以这棵树是一棵平衡二叉树。

算法与数据结构系列之[平衡二叉树-AVL树-上]
给上图这棵平衡二叉树插入两个元素2和7,则得到下图这棵二叉树(这里的二叉树是二叉排序树),根据平衡二叉树的定义,显然得到的这棵二叉树不是平衡二叉树,因为8这个节点的左子树高度为3,右子树高度为1,高度差为2,超过了1,同理根节点12的左右子树高度差也是2,所以它不是一棵平衡二叉树。

算法与数据结构系列之[平衡二叉树-AVL树-上]
如果要想让一棵平衡二叉树添加节点后依然一棵平衡二叉树,那么不能只在左边添加,右边也需要添加相应的节点来维持整棵树的平衡关系。

那么如何判断一棵二叉树是否是平衡二叉树呢?就是比较左右子树的高度差是否大于1,大于1就不是平衡二叉树。这里涉及到一个概念叫做平衡因子,平衡因子其实就是左右子树的高度差。通过计算平衡因子就可以判断一棵树是否是平衡二叉树。

3.什么是AVL树

AVL树是自平衡的二分搜索树,是一种经典的平衡树的种类。要注意的是AVL树首先要是一棵二分搜索树,其次还得是一棵平衡树,也就是要求AVL树的任何节点的左右子树高度差的绝对值不超过1。

既然AVL是自平衡的,那么AVL树是如何来维持这种平衡的呢?答案是通过旋转,即左旋和右旋。在加入节点后,要沿着这个节点向上维护平衡性。

3.1、右旋转(LL): 当插入的元素在不平衡节点的左侧的左侧时,进行右旋转,如图,将发生不平衡节点y的左子节点x的右子树变为以y为根的子树,再把 先前x的右子树T3连接到当前y的左子节点上,此时就变成了一棵以x为根节点的平衡二分搜索树。

算法与数据结构系列之[平衡二叉树-AVL树-上]
代码实现

private Node rightRotate(Node y){
    Node x = y.left;
    Node T3 = x.right;
    //向右旋转
    x.right = y;
    y.left = T3;
    //更新height值,旋转后只有x和y的高度值发生变化
    y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
    return x;
}

3.2、左旋转(RR): 当插入的元素在不平衡节点的右侧的右侧时,进行左旋转,如图,将发生不平衡节点的右子节点x的左子树变为以y为根的子树,再把先前x的左子节点T3连接到当前y的右子节点上。此时变成了一棵以x根节点的二分搜索树。
算法与数据结构系列之[平衡二叉树-AVL树-上]
代码实现:

private Node leftRotate(Node y){
    Node x = y.right;
    Node T3 = x.left;
    //向左旋转
    x.left = y;
    y.right = T3;
    //更新height值,旋转后只有x和y的高度值发生变化
    y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
    return x;
}

3.3、LR: 当插入元素在不平衡节点的左侧的右侧时,需要先对x进行一次左旋转,再对y进行一次右旋转,如下图:
算法与数据结构系列之[平衡二叉树-AVL树-上]
代码实现:

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.left = add(node.left, key, value);
    else if(key.compareTo(node.key) > 0)
        node.right = add(node.right, key, value);
    else // key.compareTo(node.key) == 0
        node.value = value;
    //更新height
    node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
    //计算平衡因子
    int balanceFactor = getBalanceFactor(node);
    //平衡维护
    //LL
    if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
        rightRotate(node);
    //RR
    if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
        return leftRotate(node);
    //LR
    if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    //RL
    if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

3.4、RL:当插入元素在不平衡节点右侧的左侧时,需要先对x进行一次右旋转,再对y进行一次左旋转,如下图:

算法与数据结构系列之[平衡二叉树-AVL树-上]
代码实现:

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.left = add(node.left, key, value);
    else if(key.compareTo(node.key) > 0)
        node.right = add(node.right, key, value);
    else // key.compareTo(node.key) == 0
        node.value = value;
    //更新height
    node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
    //计算平衡因子
    int balanceFactor = getBalanceFactor(node);
    //平衡维护
    //LL
    if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
        rightRotate(node);
    //RR
    if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
        return leftRotate(node);
    //LR
    if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    //RL
    if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

上面我们介绍了添加元素时维护平衡性的方法和代码实现,其实在删除元素时也需要维护下平衡性,方法和添加类似。下面贴出删除元素的方法实现:

private Node remove(Node node, K key){

    if( node == null )
        return null;
    Node retNode; //要返回的node节点,
    if( key.compareTo(node.key) < 0 ){
        node.left = remove(node.left , key);
        retNode = node;
    }
    else if(key.compareTo(node.key) > 0 ){
        node.right = remove(node.right, key);
        retNode = node;
    }
    else{   // key.compareTo(node.key) == 0

        // 待删除节点左子树为空的情况
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            retNode = node;
        }

        // 待删除节点右子树为空的情况
        else if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size --;
            retNode = node;
        }
        // 待删除节点左右子树均不为空的情况
        // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
        // 用这个节点顶替待删除节点的位置
        else {
            Node successor = minimum(node.right);
            successor.right = remove(node.right, successor.key);
            successor.left = node.left;


            node.left = node.right = null;


            retNode = node;
        }
    }
    if(retNode == null)
        return null;
    //更新height
    retNode.height = 1 + Math.max(getHeight(retNode.left),getHeight(retNode.right));
    //计算平衡因子
    int balanceFactor = getBalanceFactor(retNode);
    //平衡维护
    //LL
    if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
        rightRotate(retNode);
    //RR
    if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
        return leftRotate(retNode);
    //LR
    if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
        retNode.left = leftRotate(retNode.left);
        return rightRotate(retNode);
    }
    //RL
    if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
        retNode.right = rightRotate(retNode.right);
        return leftRotate(retNode);
    }
    return retNode;
}

4.总结:

这篇介绍了平衡树和AVL树的概述,在二分搜索树的基础上,重点实现了AVL树添加和删除元素后平衡性的维护,下篇将AVL树的实现代码贴出来。

上一篇:部分仿真软件对比介绍


下一篇:算法与数据结构系列之[平衡二叉树-AVL树-下]