AVL树不正确的实现

Question

我正在尝试使用不同数量的节点对 AVL 树删除操作进行计时。我的目标是试验 O(log n) 时间复杂度。我尝试实现 AVL 树，在我的印象中它应该可以工作，但是当我对我的代码计时时，它根本不遵循 log n，这让我觉得实现是不正确的。我将列出我拥有的代码重要代码：

节点类：

class AVLNode {
    int key, height;    // Each node stores a key and its height in the AVL tree
    AVLNode left, right;    // Each node has references to its left and right child nodes

    AVLNode(int key) {    // Constructor for a new node with the given key
        this.key = key;
        height = 1;    // The height of a new node is always 1
    }
}

右旋转：

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

        // Perform rotation
        y.right = x;
        x.left = T3;

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

        // Return new root
        return y;
    }

左旋转：

public AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode z = y.left;
        y.left = x;
        x.right = z;
        x.height = 1 + Math.max(height(x.left), height(x.right));
        y.height = 1 + Math.max(height(y.left), height(y.right));
        return y;
    }

插入节点：

AVLNode insert(AVLNode node, int key) {
        // If the current node is null, create a new node with the given key
        if (node == null)
            return (new AVLNode(key));

        // Recursively insert the node in either the left or right subtree
        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else // If the key is already in the tree, return the current node
            return node;

        // Update the height of the current node
        node.height = 1 + max(height(node.left), height(node.right));

        // Check the balance factor of the current node and rebalance if necessary
        int balance = getBalance(node);

        if (balance > 1 && key < node.left.key) // Left-Left case
            return rightRotate(node);

        if (balance < -1 && key > node.right.key) // Right-Right case
            return leftRotate(node);

        if (balance > 1 && key > node.left.key) { // Left-Right case
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (balance < -1 && key < node.right.key) { // Right-Left case
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // Return the current node
        return node;
    }

删除节点：

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

        System.out.println(root.height);

        if (root.height == 1) {
            AVLNode temp;
            temp = root;
            root = null;
            return temp;
        }


        // Recursively delete the node in either the left or right subtree
        if (key < root.key)
            root.left = deleteNode(root.left, key);
        else if (key > root.key)
            root.right = deleteNode(root.right, key);
        else {
            // If the node has only one child, replace it with that child
            if ((root.left == null) || (root.right == null)) {
                AVLNode temp;
                if (root.left != null)
                    temp = root.left;
                else
                    temp = root.right;

                if (temp == null) {
                    temp = root;
                    root = null;
                } else
                    root = temp;

                temp = null;
            } else { // If the node has two children, replace it with its inorder successor
                AVLNode temp = minValueNode(root.right);

                root.key = temp.key;

                root.right = deleteNode(root.right, temp.key);
            }
        }

        // If the tree only had one node, return the root
        if (root == null) {
            return root;
        }

        // Update the height of the current node
        root.height = max(height(root.left), height(root.right)) + 1;

        // Check the balance factor of the current node and rebalance if necessary
        int balance = getBalance(root);

        if (balance > 1 && getBalance(root.left) >= 0) // Left-Left case
            return rightRotate(root);

        if (balance > 1 && getBalance(root.left) < 0) { // Left-Right case
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        if (balance < -1 && getBalance(root.right) <= 0) { // Right-Right case
            return leftRotate(root);
        }
        if (balance < -1 && getBalance(root.right) > 0) { // Right-Left case
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }

最后是主要方法： public static void main(String[] args) { AVLTree 树 = new AVLTree();

    List<Integer> nValues = new ArrayList<>();
    List<Double> timeValues = new ArrayList<>();

    for (int i = 1; i <= 100; i++) {
        tree.root = tree.insert(tree.root, i);
    }

    for (int n = 1; n <= 100; n++) {

        long startTime = System.nanoTime();
        tree.root = tree.deleteNode(tree.root, (int)(n*1.61)%100);
        long endTime = System.nanoTime();
        double duration = (endTime - startTime)/1000.0;

        nValues.add(n);
        timeValues.add(duration);
    }

    double[] logTimes = new double[100];
    for (int i = 1; i < 100; i++) {
        logTimes[i] = Math.log(i);
    }

    // create chart
    XYChart chart = QuickChart.getChart("Execution Time of Deletion Algorithm", "Number of Vertices", "Execution Time (us)", "Deletion Runtime", nValues, timeValues);



    chart.addSeries("Log(n)", logTimes).setMarker(SeriesMarkers.NONE);

    // display chart
    new SwingWrapper<>(chart).displayChart();

    // save chart
    try {
        BitmapEncoder.saveBitmapWithDPI(chart, "./Run_Time_Chart", BitmapEncoder.BitmapFormat.PNG, 300);
    } catch (IOException e) {
        e.printStackTrace();
    }
}

[This is the graph I get:](https://i.stack.imgur.com/odQtn.png)

Apologies for the lengthy code, i just cannot figure out where the issue is.
Thank you in advance