Почему правильная медиана не получается с использованием моей структуры данных дерева AVL?

Question

Вопрос в том, чтобы получить медиану заданных элементов. Если нечетное, просто верните средний элемент, иначе верните среднее значение элементов n / 2 и n / 2 + 1.

Проблема в том, что он всегда возвращает 1 в качестве медианы, что, вероятно, означает, что вращение моего первого ввода не было, потому что 1 не было.

Я знаю, что это знаменитый вопрос о коде leet, но я сам написал весь свой код, и на панели обсуждений больше никого нет, чей код написан на avl дерево с нуля. Код:

'''
class Node{
    int data;
    Node left, right;
    int height;
    Node(int d){
        this.data = d;
        this.left = this.right = null;
        this.height = 1;
    }
    Node(){
        this.left = this.right = null;
    }
}

class MedianFinder {
    static Node root;
    MedianFinder(){
        root = new Node();
    }
    public void addNum(int num) {

        insert(root, num);
    }


    public static Node insert(Node root, int num){
        if(root == null)
            return (new Node(num));

        if(root.data < num){
            root.right = insert(root.right, num);
        }
        else if(root.data > num)
            root.left = insert(root.left, num);


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

        int balance = get_balance(root);
        // if left left
        if(balance > 2 && num < root.left.data){
            return rightRotation(root);
        }
        // left right case
        if(balance > 2 && num > root.left.data){
            leftRotation(root.left);
            return rightRotation(root);
        }
        // right right case
        if(balance < -1 && num > root.right.data)
            return leftRotation(root);

        // right left case
        if(balance < -1 && num < root.right.data){
            rightRotation(root.right);
            return leftRotation(root);
        }
        return root;

    }

    public static Node rightRotation(Node node){
        Node temp = node.left;
        Node tempright = temp.right;
        temp.right = node;
        node.left = tempright;

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

        return temp;
    }

    public static Node leftRotation(Node node){
        Node temp = node.right;
        Node templeft = temp.left;
        temp.left = node;
        node.right = templeft;

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

        return temp;
    }

    public static int get_balance(Node node){
        if(node == null)
            return 0;
        return height(node.left) - height(node.right);
    }

    public static int height(Node node){
        if(node == null)
            return 0;
        return node.height;
    }
    public static int max(int a, int b){
        return a>b?a:b;
    }

    public double findMedian() {

        if(height(root.left) == height(root.right))
            return root.data;
        return (root.data + root.right.data) / 2;

    }

    public static int count(Node node){
        if(node == null)
            return 0;
        return 1 + count(node.left) + count(node.right);
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

'''