Не вращается правильно - AVL Tree, JAVA

Итак, вот мое задание.

Напишите класс Java, который использует дерево AVL для хранения общих значений и ключей.

Методы

• Конструктор
• Пункт списка
• Вставлять
• Удалить
• Найдите значение для ключа
• InOrder - вернуть массив со значениями в упорядоченной последовательности
• PostOrder - вернуть массив со значениями в последовательности почтового заказа
• PreOrder - вернуть массив со значениями в порядке предварительного заказа
• Используйте внутренний класс узла, который содержит ключ и значение.
• Используйте ArrayList для массива, возвращенного в результате обходов.

Я думаю, что у меня есть основная идея, но мое дерево неправильно сбалансировано. Кроме того, inorder, preorder, postored находятся в разработке, пытаясь убедиться, что сортировка выполняется правильно, прежде чем я реализую ArrayList.

Любая помощь или исправления будут огромными. Вот что у меня есть на данный момент.

public class AVLTree {

    Node root;

    public class Node{ //subclass of Node in AVL tree
        private Node left; 
        private Node right;
        int height = 1;
        int key;

        public Node(int n)
        {
            this.key = n;
            height = 1;
        }
    }

    public int height(Node n){
        if(n == null)
            return 0;
        return n.height;
    }

    public void in(int key)
    {
        root = insert(root, key);
    }

    public Node insert(Node node, int key) //insert 
    {
        if(node == null)
        {
            node = new Node(key);
        }
        else if(key < node.key)
        {
            node.left = insert(node.left, key);
            if(height(node.left)- height(node.right) == 2) {
                if(key < node.left.key)
                {
                    node = rotateLeft(node);
                }
                else {
                    node.left = rotateRight(node.left);
                    rotateLeft(node);
                }
            }
        }
        else if(key > node.key)
        {
            node.right = insert(node.right, key);
            if(height(node.right)- height(node.left) == 2) {
                if(key < node.right.key)
                {
                    node = rotateRight(node);
                }
                else {
                    node.right = rotateLeft(node.right);
                    rotateRight(node);
                }
            }
        }
        else {
            node.height = Math.max(height(node.left), height(node.right)) + 1; //increase height of the node
        }
        return node;
    }

    public Node delete(Node root, int key) {
        if(root == null)
            return root;
        Node temp;
        if (key < root.key) {
            root.left = delete(root.left, key);
        }
        else if(key > root.key) {
            root.right = delete(root.right,key);
        }
        else if(key == root.key){

            if(root.left == null || root.right == null){ //root has one child


                if(root.left != null) 
                    temp = root.left;
                else  
                    temp = root.right;

                if( temp == null) { // no child
                    temp = root;
                    root = null;
                }
                else 
                    root = temp;

                temp = null;        
            }
        else {
            temp = minNode(root.right);
            root.key = temp.key;
            root.right = delete(root.right, temp.key);
            }
        }

        if(root == null)
            return root;

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

        //once deleted we must rebalance it 

        int balance =  height(root.left) - height(root.right); //check balance of top node

        if(balance > 1 && key < root.left.key) //left left rotation
            return rotateRight(root);
        else if(balance < -1 && key > root.right.key) //right right
            return rotateLeft(root);
        else if(balance > 1 && key > root.left.key) //left righ
            return rotateRight(root);
        else if(balance > -1 && key < root.right.key) //right left
            return rotateRight(root);

        return root;
    }


    private Node rotateLeft(Node y) {
        Node x = y.left;
        y.left = x.right;
        x.right = y; //rotates
        x.height = Math.max(height(x.left), height(x.right))+1;
        y.height = Math.max(height(y.left), height(y.right))+1;

        return x;
        }

    private Node rotateRight(Node x)
    {
        Node y = x.right;
        x.right = y.left;
        y.left = x; //rotates
        x.height = Math.max(height(x.left), height(x.right))+1;
        y.height = Math.max(height(y.left), height(y.right))+1;

        return y;
    }

    void TpreOrder(Node node)
    {
        if (node != null)
        {
            System.out.print(node.key + " ");
            TpreOrder(node.left);
            TpreOrder(node.right);
        }
    }


    void TpostOrder(Node node)
    {
        if (node != null)
        {
            TpreOrder(node.left);
            TpreOrder(node.right); 
            System.out.print(node.key + " ");

        }
    }

    public void TinOrder(Node root)
    {
        if(root != null) {
            TinOrder(root.left);    
            System.out.print(root.key+" ");
            TinOrder(root.right);           
        }
    }

    public void inOrder(Node root, ArrayList<Integer> pre)
    {
        if(root != null) {
            inOrder(root.left, pre);    
            pre.add(root.key);

            pre.add(root.key);
            inOrder(root.right, pre);           
        }
    }

    public ArrayList<Integer> toArray() {
        ArrayList<Integer> result = new ArrayList<Integer>();
        inOrder(root, result);
        return result;
    }


    public void preOrder(Node root, ArrayList<Integer> in)
    {
        if(root != null) {
            preOrder(root.left, in);
            in.add(root.key);
            preOrder(root.right, in);           
        }
    }

    public void postOrder(Node root, ArrayList<Integer> post)
    {
        if(root != null) {
            postOrder(root.right, post);    
            post.add(root.key);
            postOrder(root.left, post); 
        }
    }

    private Node minNode(Node node) {
        Node cur = node;

        while(cur.left != null)
            cur = cur.left;
        return cur;
    }
}