阅读 1081

小码哥《恋上数据结构与算法》笔记(九):平衡二叉搜索树(AVL)

一、平衡二叉搜索树(Balance Binary Search Tree)

1、退化成链表的二叉搜索树

  • 删除节点时,可能会导致二叉搜索树退化成链表
  • 如果删除2,9,8,11四个节点,就会导致退化
  • 如何防止二叉搜素树退化成链表?让添加,删除,搜索的复杂度维持在O(logn)

2、平衡(Balance)

  • 当节点数量固定时,左右子树的高度越接近,这颗二叉树就越平衡(高度越低)。
  • 最理想的平衡,就是像完全二叉树满二叉树那样,高度是最小的。

2、如何改进二叉搜索树?

  • 节点的添加删除顺序是无法限制的,也就是随机的。
  • 那么改进方案是:在节点的添加,删除操作之后,想办法让二叉搜索树恢复平衡(减小树的高度)。
  • 如果接着继续调整节点的位置,完全可以达到理想平衡,但是付出的代价可能会比较大。如果调整次数太多,反而增加了时间复杂度。
  • 所以比较合适的方案是:用尽量少的调整次数达到适度平衡
  • 一颗达到适度平衡的二叉搜索树,可以称之为:平衡二叉搜索树

3、常见的平衡二叉搜索树

  • AVL树:Windows NT内核中广泛使用。
  • 红黑树:java的TreeMapTreeSetHashMapHashSet

二、AVL树

  • 什么是平衡因子:某节点的左右子树高度差
  • AVL树的特点:
    • 每个节点的平衡因子只可能是1,0,-1。即绝对值<=1,如果超过1,称之为失衡
    • 每个节点的左右子树高度差不超过1
    • 搜索,添加,删除的时间复杂度是O(logn)

  • AVL树和红黑树,都是在二叉搜索树的基础上,增加了自平衡的功能。

三、失衡的几种情况

1、添加导致的失衡

  • 示例:添加13导致失衡
  • 最坏的情况,可能会导致所有祖先节点14,15,9都失衡。
  • 但是父节点12,非祖先节点4,6,8,都不可能失衡。

2、添加失衡 LL - 右旋传(单旋)

  • n代表nodep代表parentg代表grandparent
  • 如果在T0节点位置增加节点,那么g失去平衡。
  • LL表示失衡节点添加节点的关系,添加节点失衡节点左边的左边
  • 因为是g左边的左边的节点使它失去平衡,所以这种情况称之为LL
  • LL的情况,一般需要右旋转
  • 思路:
    • g.left = p.right
    • p.right = g
    • p成为这颗子树的根节点
    • 改变之后整棵树仍然是一颗二叉搜索树:T0 < n < T1 < p < T2 < g < T3
    • 整棵树都达到平衡。
  • 还需要注意维护:
    • T2pgparent属性。
    • 先后更新gp高度属性。

3、添加失衡 RR - 左旋转(单旋)

  • 如果往T2或T3位置加入一个节点,则g会失衡。
  • RR表示失衡节点添加节点的关系,添加节点失衡节点右边的右边
  • 那么我们需要左旋转,使树达到平衡。
  • 思路:
    • g.right = p.left
    • p.left = g
    • p成为这颗子树的根节点
  • 整棵树都达到了平衡。
  • 还需要注意维护:
    • T1pgparent属性。
    • 先后更新gp高度属性。

4、添加失衡 LR - RR左旋转,LL右旋转(双旋)

  • pgleft节点,npright节点,此时往n添加节点,这种情况称为LR
  • LR表示失衡节点添加节点的关系,添加节点失衡节点左右
  • 如果是LR,首先要进行一次左旋转,将二叉树变为LL。然后再进行一次右旋转,即可使树达到平衡。

5、添加失衡 RL - LL右旋转,RR左旋转(双旋)

  • 首先进行右旋转,使树变成RR,然后再进行左旋转,即可达到平衡。
  • RL表示失衡节点添加节点的关系,添加节点失衡节点右边的左边

6、删除导致的失衡

  • 示例:删除16导致失衡
  • 删除节点可能会导致父节点祖先节点失衡(只有一个节点会失衡),其他节点都不可能失衡。

7、删除失衡 LL - 右旋传(单旋)

  • 删除红色节点,g的平衡因子变为2,需要对g进行右旋转
  • 旋转后,整棵树是否平衡,取决于旋转后子树的高度是否发生变化。其实就取决于绿色节点是否存在。
  • 如果绿色节点不存在,那么在右旋转后,子树的高度减少1,可能会导致更高层的祖父节点失衡。
  • 更高层的祖先节点失衡,则需要再次恢复平衡,然后又可能导致更高层的祖先节点失衡...
  • 极端情况下,所有祖先节点都需要进行恢复平衡的操作,共O(logn)次调整。

四、如何调整失衡

1、添加- afterAdd()函数

  • 失衡调整应该在添加节点之后。
  • 所以我们需要对二叉搜索树添加方法进行改造,即在完成添加节点后,进行失衡调整
  • 引入afterAdd()函数,当完成添加节点操作后,执行该方法。
public void add(E element) {
    ...
    // 添加第一个节点
    if (root == null) {
        ...
        // 新添加节点之后的处理
        afterAdd(root);
    }
    // 添加的不是第一个节点
    else {
        ...
        // 新添加节点之后的处理
        afterAdd(newNode);
    }
}
复制代码
  • 接下来我们再看如何实现这个afterAdd(newNode)函数。
  • 思路:通过newNodeparent属性,一路往上找,找到高度最低的那个失衡节点,然后对失衡节点进行调整。
  • 只要这个高度最低失衡节点恢复平衡,那么所有的节点都恢复平衡了。
protected void afterAdd(Node<E> node) {
    //可能添加新节点之后,整个树没有失衡。
    //所以我们需要一直查找到node.parent == null为止。
    while ((node = node.parent) != null) {
        // 判断节点是否平衡
        if (isBalanced(node)) {
            // 如果是平衡的,更新节点高度
            updateHeight(node);
        } else {
            // 否则,恢复平衡
            rebalance(node);
            // 整棵树恢复平衡
            break;
        }
    }
}
复制代码

2、添加- isBalanced(node)函数

  • afterAdd(newNode)中,需要实现isBalanced(node)函数,用于判断节点是否平衡,从而决定是更新高度恢复平衡
  • 判断节点平衡的方式是比较左右子节点高度,所以需要给节点增加一个高度属性。
  • 如果节点是平衡的,只需要更新节点高度,通过获取左右子树最大高度 + 1即可。
private static class AVLNode<E> extends Node<E> {
    // 高度,默认值为1,因为新节点肯定是叶子节点。
    int height = 1;
		
    public AVLNode(E element, Node<E> parent) {
        super(element, parent);
    }
		
    // 获取节点的平衡因子
    // 左子节点高度减去右子节点高度
    public int balanceFactor() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            return leftHeight - rightHeight;
    }
        
    // 更新节点高度
    public void updateHeight() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
        // 高度等于左右子树最大高度 + 1
        height = 1 + Math.max(leftHeight, rightHeight);
    }
}

// 判断节点是否平衡
private boolean isBalanced(Node<E> node) {
    // 通过比较该节点,左右节点平衡因子,来判断节点是否平衡。
    return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
}

// 更新某节点高度
private void updateHeight(Node<E> node) {
    ((AVLNode<E>)node).updateHeight();
}
复制代码

3、添加- rebalance(node)函数

  • 最后我们还需要实现rebalance(node)函数。
  • 能够进入rebalance(node)函数,那么node即为上面分析的失衡的几种情况中的gg代表grandparent
  • 接下来还要拿到pn节点。
  • pg左右子树高度最高的子节点。
  • np左右子树高度最高的子节点。
  • 那么我们首先实现一个获取较高子节点的函数。
public Node<E> tallerChild() {
    int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    if (leftHeight > rightHeight) return left;
    if (leftHeight < rightHeight) return right;
    // 如果高度一样,断该节点是父节点的左子节点,如果是,则返回left。
    return isLeftChild() ? left : right;
}
复制代码
  • AVLNode类中增加两个方法用于判断节点是父节点的左子节点或右子节点。
private static class AVLNode<E> extends Node<E> {
    ...

    // 判断该节点是父节点的左子节点
    public boolean isLeftChild() {
        return parent != null && this == parent.left;
    }
	
    // 判断该节点是父节点的右子节点
    public boolean isRightChild() {
        return parent != null && this == parent.right;
    }
}
复制代码
  • 那么rebalance(node)函数实现如下:
/**
* 恢复平衡
* @param grand 高度最低的那个不平衡节点
*/
private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>)grand).tallerChild();
    Node<E> node = ((AVLNode<E>)parent).tallerChild();
    //如果parent是grand的左子节点 L
    if (parent.isLeftChild()) { 
        //并且node是parent的左子节点 LL
        if (node.isLeftChild()) { 
            rotateRight(grand);
        } 
        //并且node是parent的右子节点 LR
        else { 
            rotateLeft(parent);
            rotateRight(grand);
            }
    } 
    //如果parent是grand的右子节点 R
    else { 
        //并且node是parent的左子节点 RL
        if (node.isLeftChild()) { 
            rotateRight(parent);
            rotateLeft(grand);
        } 
        //并且node是parent的右子节点 RR
        else { 
            rotateLeft(grand);
        }
    }
}
复制代码

4、添加- rotateLeft(node) 和- rotateRight(node) 函数

  • 最后我们实现rotateLeft()rotateRight()函数。
private void rotateLeft(Node<E> grand) {
    Node<E> parent = grand.right;
    Node<E> child = parent.left;
    grand.right = child;
    parent.left = grand;
    afterRotate(grand, parent, child);
}
	
private void rotateRight(Node<E> grand) {
    Node<E> parent = grand.left;
    Node<E> child = parent.right;
    grand.left = child;
    parent.right = grand;
    afterRotate(grand, parent, child);
}

// 旋转之后,更新各节点信息
private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
    // 让parent成为子树的根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else { // grand是root节点
        root = parent;
    }
		
    // 更新child的parent
    if (child != null) {
        child.parent = grand;
    }
		
    // 更新grand的parent
    grand.parent = parent;
		
    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
}
复制代码

5、添加 -afterRemove(node) 函数

  • 在节点被删除后,可能导致失衡,所以需要调用afterRemove函数调整失衡。
private void remove(Node<E> node) {
    ...
    if (node是度为1的节点) { 
        ...
        // 删除节点之后的处理
        afterRemove(node);
    } else if (node是叶子节点并且是根节点) { 
        ...
        // 删除节点之后的处理
        afterRemove(node);
    } else { 
        //node是叶子节点,但不是根节点
        ...
        // 删除节点之后的处理
        afterRemove(node);
    }
}
复制代码
  • 其中updateHeightrebalance在上面已经实现了。
protected void afterRemove(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢复平衡
            rebalance(node);
        }
    }
}
复制代码

四、示例

  • 输入数据:13,14,15,12,11,17,16,8,9,1
  • 输入13,14
  • 输入15,导致13不平衡,需要左旋转
  • 输入12
  • 输入11,导致13不平衡,需要右旋转
  • 输入1716
  • 那么15,16,17形成RL,需要先对17右旋转,然后对15左旋转。
  • 输入89
  • 那么11,8,9形成LR,需要先对8左旋转,然后对11右旋转。
  • 输入1,会导致12不平衡。
  • 12,9,8形成LL,需要对12右旋转。
  • 如果你能理解每一步,说明你已经掌握AVL树

五、总结

  • 添加
    • 可能会导致所有祖先节点都失衡。
    • 但是只要让高度最低的失衡节点恢复平衡,整棵树就恢复平衡(仅需O(1)次调整)。
  • 删除
    • 可能会导致父节点祖先节点失衡(只有一个节点会失衡)。
    • 恢复平衡后,可能会导致更高层的祖先节点失衡(最多需要O(logn)次调整)。
  • 平均时间复杂度
    • 搜索:O(logn)
    • 添加:O(logn),仅需O(1)次旋转操作。
    • 删除:O(logn),最多需要O(logn)次旋转操作。

六、算法