DS05.3:AVL树

概况

AVL树（平衡二叉树）

平衡二叉树是一种二叉搜索树，对于其中任意一个节点，左子树和右子树的高度差不能超过1。

两位俄罗斯数学家共同发明了一种解决平衡二叉树的算法，所以这种树也称为AVL树（取其名称）。

注意的地方：平衡二叉树从叶子节点向上记录节点的高度，即叶子节点高度为1，向上依次类推。而使用平衡因子用来表示左右子树高度差。

平衡二叉树的作用

根据之前对二叉搜索树的时间复杂度分析可知，其各项操作的时间复杂度介于O(log n)与O(n)之间，在节点足够多的情况下这两者的效率相差很大。O(n)复杂度的BST实际上已经退化成了一个链表，而复杂度接近O(log n)的情况则就是平衡二叉树的状态了，因此对二叉树进行“平衡处理”是很重要的。

平衡性分析

由于AVL树仍然是一个二叉搜索树，所以二叉搜索树的一切操作都可以进行调用，唯一需要注意的就是当有破坏平衡的操作发生时，需要进行对应操作维护树的平衡性。

显然，BST的相关操作中添加元素与删除元素这两个操作可能会破坏树的平衡性，因此在add与remove中递归实现的基础上，应该在递归完成之后沿着节点向上维护平衡性（有点后续遍历的味道）。

基本操作

1、右旋（左左）

这种情况发生在向左子树的左孩子添加一个元素，且正好打破了平衡时（即二叉树向左倾斜）。这种情况我们可以称为左左，需要进行右旋操作维持平衡

右旋操作简单来讲如下伪码：

右旋(L):	
	temp = L.right;
	L.right = T;
	T.left = temp;

如图所示：

2、左旋（右右）

这种情况发生在向右子树的右孩子添加一个元素，且正好打破了平衡时（即二叉树向右倾斜）。这种情况我们可以称为右右，需要进行左旋操作维持平衡。

左旋操作可以视为右旋的镜像

伪码如下：

左旋(R):
	temp = R.left;
	R.left = T;
	T.right = temp;

如图所示：

3、左右

顾名思义，也就是向左子树的右孩子插入一个节点。

这种情况下，我们需要先对右孩子进行一次左旋，再对对应的“根节点”进行一次右旋。如图所示：

伪码如下：

左旋(R);
右旋(L);

4、右左

与“左右”是镜像操作，故不再赘述

操作实现

node中新增height用于记录高度

private class Node {
    public E e;
    public Node left, right;
    public int height;	// 记录高度

    public Node(E e) {
        this.e = e;
        left = null;
        right = null;
        height = 1;
    }
}

功能函数

获取节点的高度

// 获取每个节点的高度
private int getHeight(Node node) {
    if(node == null)
        return 0;
    return node.height;
}

计算每个点的平衡因子

这个功能方法在AVL树的实现中至关重要，记住由于之后在维护平衡时需要判断是上述基本操作中的哪一种，因此该函数计算的平衡因子一定不能加上abs函数。

// 计算每个点的平衡因子
    private int getBalenceFactor(Node node) {
        if(node == null)
            return 0;
        return getHeight(node.left) - getHeight(node.right);	// 不要加abs函数
    }

右旋操作

// 对节点y进行向右旋转操作，返回旋转后新的根节点x
//        y                              x
//       / \                           /   \
//      x   T4     向右旋转 (y)        z     y
//     / \       - - - - - - - ->    / \   / \
//    z   T3                       T1  T2 T3 T4
//   / \
// T1   T2
private Node rightRotate(Node y) {
    Node x = y.left;
    Node T3 = x.right;

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

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

    return x;
}

左旋操作

// 对节点y进行向左旋转操作，返回旋转后新的根节点x
//    y                             x
//  /  \                          /   \
// T1   x      向左旋转 (y)       y     z
//     / \   - - - - - - - ->   / \   / \
//   T2  z                     T1 T2 T3 T4
//      / \
//     T3 T4
private Node leftRotate(Node y) {
    Node x = y.right;
    Node T2 = x.left;

    x.left = y;
    y.right = T2;

    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    return x;
}

判断是否是平衡二叉树

// 判断是否是平衡二叉树
public boolean isBalanced() {
    return isBalanced(root);
}

private boolean isBalanced(Node node) {
    if(node == null)
        return true;
    int balanceFactor = getBalenceFactor(node);
    if(Math.abs(balanceFactor) > 1)
        return false;
    return isBalanced(node.left) && isBalanced(node.right);
}

维护平衡与更新高度

// 返回进行平衡维护后的节点
private Node keepBalence(Node node) {
    // 更新height
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

    // 平衡维护
    int balanceFactor = getBalenceFactor(node);
    if(balanceFactor > 1 && getBalenceFactor(node.left) >= 0) {
        return rightRotate(node);
    }
    if(balanceFactor < -1 && getBalenceFactor(node.right) <=0) {
        return leftRotate(node);
    }
    // LR
    if(balanceFactor > 1 && getBalenceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    // RL
    if(balanceFactor < -1 && getBalenceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

插入节点

private Node add(Node node, E e) {
    if(node == null) {
        size++;
        return new Node(e);
    }
    if(e.compareTo(node.e) < 0) {
        node.left = add(node.left, e);
    }
    else if(e.compareTo(node.e) >0) {
        node.right = add(node.right, e);
    }

    return keepBalence(node);
}

删除节点

private Node remove(Node node, E e) {
    if(node == null)
        return null;

    Node retNode;
    if(e.compareTo(node.e) < 0) {
        node.left = remove(node.left, e);
        retNode = node;
    }
    else if(e.compareTo(node.e) > 0) {
        node.right = remove(node.right, e);
        retNode = node;
    }
    else {
        if(node.left == null || node.right == null) {
            node = (node.left == null) ? node.right : node.left;
            retNode = node;
        }
        else {
            Node temp = node.right;
            while (temp.left != null)
                temp = temp.left;
            node.e = temp.e;
            node.right = remove(node.right, temp.e);
            retNode = node;
        }
	}

    // 当前节点被删除时
    if(retNode == null)
        return null;

    return keepBalence(retNode);
}

参考链接：

https://www.cnblogs.com/linhaostudy/p/11300556.html （图画的相当清楚，点赞！）

https://github.com/liuyubobobo/Play-with-Data-Structures

Donate