实现不存储高度信息的AVL树-java教程-PHP中文网

实现不存储高度信息的AVL树

花韻仙語

发布： 2025-09-25 19:56:01

原创

445人浏览过

实现不存储高度信息的avl树

实现不存储高度信息的AVL树

本文旨在探讨如何在节点不直接存储高度信息的情况下实现AVL树。摘要中已经提到，我们将使用HashMap来维护节点的高度，并结合AVL树的旋转操作，实现自平衡二叉搜索树。文章重点分析在节点插入时如何动态更新节点高度，并提供了优化的代码示例，解决了大规模数据插入时可能出现的空指针异常问题。

AVL树是一种自平衡二叉搜索树，它通过保持树的平衡来确保高效的查找、插入和删除操作。传统的AVL树实现通常在每个节点中存储其高度信息，以便快速计算平衡因子并执行旋转操作。然而，在某些情况下，我们可能无法修改节点类来添加高度字段。本文介绍了一种替代方案，即使用额外的数据结构（例如HashMap）来存储节点的高度，并在此基础上实现AVL树的自平衡。

使用HashMap存储节点高度

由于节点类无法修改，我们不能直接在节点中存储高度信息。因此，我们使用HashMap<Node, Integer>来维护每个节点的高度。HashMap的键是Node对象，值是对应节点的高度。

插入操作

插入操作是AVL树的核心。在插入新节点后，我们需要更新受影响节点的高度，并检查是否需要进行旋转以保持树的平衡。以下是插入操作的实现步骤：

标准BST插入: 首先，执行标准的二叉搜索树插入操作。
更新高度: 在递归返回的过程中，更新每个经过节点的高度。节点的高度等于其左右子树高度的最大值加1。
计算平衡因子: 计算当前节点的平衡因子，即左子树的高度减去右子树的高度。
执行旋转: 根据平衡因子的值，执行相应的旋转操作（左旋或右旋）以恢复树的平衡。

以下是插入操作的关键代码片段：

public Node insert(Node curNode, Student s){
    if (curNode == null){
        Node newNode = new Node(s);
        map.put(newNode, 1); // 新节点高度为1
        return newNode;
    }
    else if (s.name.compareTo(curNode.e.name) < 0)
        curNode.lc = insert(curNode.lc, s);
    else if (s.name.compareTo(curNode.e.name) > 0)
        curNode.rc = insert(curNode.rc, s);
    else return curNode;

    map.put(curNode, max(nheight(curNode.rc), nheight(curNode.lc)) + 1);

    int balance = getBalance(curNode);

    if (balance > 1 && s.name.compareTo(curNode.lc.e.name) < 0)
        return rightRotate(curNode);
    if (balance < -1 && s.name.compareTo(curNode.rc.e.name) > 0)
        return leftRotate(curNode);
    if(balance > 1 && s.name.compareTo(curNode.lc.e.name) > 0){
        curNode.lc = leftRotate(curNode.lc);
        return rightRotate(curNode);
    }
    if(balance < -1 && s.name.compareTo(curNode.rc.e.name) < 0){
        curNode.rc = rightRotate(curNode.rc);
        return leftRotate(curNode);
    }
    return curNode;
}

登录后复制

注意： 上述代码中，关键的修正在于旋转判断条件中，需要确保curNode.lc和curNode.rc不为空，才能访问其e.name属性，否则会导致NullPointerException。

微信 WeLM

WeLM不是一个直接的对话机器人，而是一个补全用户输入信息的生成模型。

查看详情

旋转操作

AVL树的旋转操作包括左旋和右旋。旋转操作用于调整树的结构，使其保持平衡。旋转操作需要更新相关节点的高度信息。

以下是右旋操作的代码示例：

public Node rightRotate(Node y){
    Node x = y.lc;
    Node T2 = x.rc;
    x.rc = y;
    y.lc = T2;
    // 更新高度
    map.put(y, max(nheight(y.lc), nheight(y.rc)) + 1);
    map.put(x, max(nheight(x.lc), nheight(x.rc)) + 1);
    return x;
}

登录后复制

左旋操作类似，也需要更新相关节点的高度。

获取节点高度和平衡因子

为了计算平衡因子和更新节点高度，我们需要实现nheight和getBalance方法。nheight方法用于获取节点的高度，如果节点为空，则返回0。getBalance方法用于计算节点的平衡因子。

public int nheight(Node curRoot){
    if (curRoot == null) return 0;
    return map.get(curRoot);
}

public int getBalance(Node curNode){
    if (curNode == null) return 0;
    return nheight(curNode.lc) - nheight(curNode.rc);
}

登录后复制