Java中的AVL树

Java中的AVL树

AVL树是一种自平衡二叉查找树，意味着任何时候任何操作后，它都会自动调整自己的结构以保持平衡状态。它的名字来源于其发明者G.M.Adelson-Velsky和E.M.Landis。

在AVL树中，任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。增加和删除元素的操作则可能需要借由一次到多次树旋转，以实现树的重新平衡。

AVL树的定义

AVL树的节点定义如下：

static class avlNode {
    int key;
    Object value;
    avlNode left;
    avlNode right;
    int height;

    public avlNode(int key) {
        this.key = key;
    }

    public avlNode(int key, Object value) {
        this.key = key;
        this.value = value;
    }

    public avlNode(int key, Object value, avlNode left, avlNode right) {
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

每个节点包含一个键、一个值、一个左子节点、一个右子节点以及一个表示节点高度的字段。

AVL树的旋转操作

AVL树通过四种旋转操作来保持平衡：左旋、右旋、左右旋和右左旋。

• 左旋（Left Rotate）

private avlNode leftRotate(avlNode node) {
    avlNode rightChild = node.right;
    node.left = rightChild.left;
    rightChild.left = node;
    node.height = getHeight(node);
    rightChild.height = getHeight(rightChild);
    return rightChild;
}

• 右旋（Right Rotate）

private avlNode rightRotate(avlNode node) {
    avlNode leftChild = node.left;
    node.left = leftChild.right;
    leftChild.right = node;
    node.height = getHeight(node);
    leftChild.height = getHeight(leftChild);
    return leftChild;
}

• 左右旋（Left Right Rotate）

private avlNode LRRotate(avlNode node) {
    node.left = leftRotate(node.left);
    return rightRotate(node);
}

• 右左旋（Right Left Rotate）

private avlNode RLRotate(avlNode node) {
    node.right = rightRotate(node.right);
    return leftRotate(node);
}

AVL树的插入和删除操作

AVL树的插入和删除操作需要在操作后检查并保持树的平衡。

• 插入操作

public void put(int key, Object value) {
    root = doPut(root, key, value);
}

private avlNode doPut(avlNode node, int key, Object value) {
    if (node == null) {
        avlNode avlNode = new avlNode(key, value);
        return avlNode;
    }
    if (node.key > key)
        node.left = doPut(node.left, key, value);
    else if (node.key < key)
        node.right = doPut(node.right, key, value);
    else
        node.value = value;
    return balance(node);
}

• 删除操作

public void remove(int key) {
    root = doRemove(root, key);
}

private avlNode doRemove(avlNode node, int key) {
    if (node == null) {
        return node;
    }
    if (node.key > key) {
        node.left = doRemove(node.left, key);
    } else if (node.key < key) {
        node.right = doRemove(node.right, key);
    } else {
        if (node.right == null) {
            return node.left;
        } else if (node.left == null) {
            return node.right;
        } else {
            avlNode p = node.right;
            while (p.left != null) {
                p = p.left;
            }
            p.right = doRemove(node.right,p.key);
            p.left = node.left;
            node = p;
        }
    }
    node.height = getHeight(node);
    return balance(node);
}