Java数据结构之AVL树实例分析

发布时间:2022-06-01 13:53:59 作者:iii
来源:亿速云 阅读:187

Java数据结构之AVL树实例分析

1. AVL树简介

AVL树是一种自平衡的二叉搜索树(BST),由Adelson-Velsky和Landis在1962年提出。AVL树通过维护每个节点的平衡因子(即左子树高度与右子树高度的差值)来确保树的高度始终保持在O(log n)范围内,从而保证查找、插入和删除操作的时间复杂度为O(log n)。

2. AVL树的基本性质

3. AVL树的Java实现

3.1 节点类定义

首先,我们定义一个表示AVL树节点的类AVLNode

class AVLNode {
    int key;
    int height;
    AVLNode left;
    AVLNode right;

    AVLNode(int key) {
        this.key = key;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}

3.2 平衡因子计算

为了计算节点的平衡因子,我们需要一个辅助方法来获取节点的高度:

int height(AVLNode node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}

int getBalance(AVLNode node) {
    if (node == null) {
        return 0;
    }
    return height(node.left) - height(node.right);
}

3.3 旋转操作

AVL树的旋转操作包括左旋和右旋:

AVLNode rightRotate(AVLNode y) {
    AVLNode x = y.left;
    AVLNode T2 = x.right;

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

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

    return x;
}

AVLNode leftRotate(AVLNode x) {
    AVLNode y = x.right;
    AVLNode T2 = y.left;

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

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

    return y;
}

3.4 插入操作

插入操作首先按照二叉搜索树的规则插入节点,然后更新节点的高度并检查平衡因子。如果树失去平衡,则进行相应的旋转操作:

AVLNode insert(AVLNode node, int key) {
    if (node == null) {
        return new AVLNode(key);
    }

    if (key < node.key) {
        node.left = insert(node.left, key);
    } else if (key > node.key) {
        node.right = insert(node.right, key);
    } else {
        return node; // 不允许插入重复的键
    }

    node.height = 1 + Math.max(height(node.left), height(node.right));

    int balance = getBalance(node);

    // 左左情况
    if (balance > 1 && key < node.left.key) {
        return rightRotate(node);
    }

    // 右右情况
    if (balance < -1 && key > node.right.key) {
        return leftRotate(node);
    }

    // 左右情况
    if (balance > 1 && key > node.left.key) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 右左情况
    if (balance < -1 && key < node.right.key) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

3.5 删除操作

删除操作与插入操作类似,首先按照二叉搜索树的规则删除节点,然后更新节点的高度并检查平衡因子。如果树失去平衡,则进行相应的旋转操作:

AVLNode deleteNode(AVLNode root, int key) {
    if (root == null) {
        return root;
    }

    if (key < root.key) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.key) {
        root.right = deleteNode(root.right, key);
    } else {
        if ((root.left == null) || (root.right == null)) {
            AVLNode temp = null;
            if (temp == root.left) {
                temp = root.right;
            } else {
                temp = root.left;
            }

            if (temp == null) {
                temp = root;
                root = null;
            } else {
                root = temp;
            }
        } else {
            AVLNode temp = minValueNode(root.right);
            root.key = temp.key;
            root.right = deleteNode(root.right, temp.key);
        }
    }

    if (root == null) {
        return root;
    }

    root.height = Math.max(height(root.left), height(root.right)) + 1;

    int balance = getBalance(root);

    // 左左情况
    if (balance > 1 && getBalance(root.left) >= 0) {
        return rightRotate(root);
    }

    // 左右情况
    if (balance > 1 && getBalance(root.left) < 0) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }

    // 右右情况
    if (balance < -1 && getBalance(root.right) <= 0) {
        return leftRotate(root);
    }

    // 右左情况
    if (balance < -1 && getBalance(root.right) > 0) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }

    return root;
}

AVLNode minValueNode(AVLNode node) {
    AVLNode current = node;
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

4. 实例分析

假设我们有一个空的AVL树,依次插入以下键值:10, 20, 30, 40, 50, 25。插入过程如下:

  1. 插入10:树平衡。
  2. 插入20:树平衡。
  3. 插入30:树失去平衡,进行左旋。
  4. 插入40:树平衡。
  5. 插入50:树失去平衡,进行左旋。
  6. 插入25:树失去平衡,进行左右旋。

最终,AVL树的结构如下:

      30
     /  \
   20   40
  /  \    \
10   25   50

5. 总结

AVL树通过维护每个节点的平衡因子来确保树的高度始终保持在O(log n)范围内,从而保证了查找、插入和删除操作的高效性。通过旋转操作,AVL树能够在插入或删除节点后迅速恢复平衡。本文通过Java代码实现了AVL树的基本操作,并通过实例分析了插入过程。AVL树在需要频繁插入和删除操作的场景中具有重要的应用价值。

推荐阅读:
  1. 浅析AVL树算法
  2. AVL树之删除算法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java avl

上一篇:SQL注入之盲注怎么实现

下一篇:Python如何实现SQL自动化

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》