无法修改Node类实现AVL树：大数据量下HashMap存高度报错求助

我正在学习二叉搜索树，学校作业要求实现自平衡二叉搜索树（选择AVL树），但Node类无法修改，不能在节点内部存储高度。我采用HashMap<Node, Integer>存储节点高度，递归计算高度与平衡因子，小数据量（如1000个节点）时可正常运行，但插入100万个随机生成的Student节点时抛出错误：

Exception in thread "main" java.lang.NullPointerException: Cannot read field "lc" because "y" is null

以下是我的实现代码与测试代码：

Tree类实现 #

public class Tree {
    static class Student {
        String id;
        String name;
        public Student(String id, String name) {
            this.id = id;
            this.name = name;
        }

        public String toString() {return id + ", " + name;}
    }
    
    private class Node {
        Student e;
        public Node lc, rc; // left child; right child

        @SuppressWarnings("unused")
        public Node(Student data) {
            this.e = data;
        }

        public String toString() {
            return e.toString();
        }
    }

    Node root;
    public HashMap<Node, Integer> map = new HashMap<>();
   
    public void insert(Student s) {
        root = insert(root, s);
    }

    public Node insert(Node curNode, Student s){
        if (curNode == null){
            Node newNode = new Node(s);
            map.put(newNode, 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;
        int l, r;
        map.put(curNode, max(nheight(curNode.rc), 
                nheight(curNode.lc)) + 1);
        
        int balance = getBalance(curNode);

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

    public int max(int a, int b){
        return a > b ? a : b;
    }
    
    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);
    }
    
    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;
    }

    public Node leftRotate(Node x){
        Node y = x.rc;
        Node T2 = y.lc;
        y.lc = x;
        x.rc = T2;
        map.put(x, max(nheight(x.lc), nheight(x.rc)) + 1);
        map.put(y, max(nheight(y.lc), nheight(y.rc)) + 1);
        return y;
    }
    
}

Main测试类 #

public class Main {
public static void main(String[] args) {
    Tree tree = new Tree();
    String[] surnames = {"Chan", "Leung", "Li", "Lai", "Cheung", "Yeung", "Tang", "Chow", "Fung", "Tsang", "Kwok", "Chu", "Liu", "Wong", "Mak"};
    SecureRandom random = new SecureRandom();
    String[] names = new String[1000000];
    for (int j = 0; j < names.length; j++) {
            StringBuilder a = new StringBuilder();
            for(int i = 0; i < 5; i ++) {
                a.append((char)('a' + random.nextInt(25)));
            }
            names[j] = surnames[random.nextInt(surnames.length)] + " " + a.toString();
    }
    int id = 22222222;
    for (String name : names) {
        id += random.nextInt(100);
        tree.insert(new Tree.Student(String.valueOf(id), name));
    }
}

请问有哪些可替代的数据结构或方法来跟踪节点高度，解决大数据量下的问题？

内容的提问来源于stack exchange，提问作者memonhama