Как исправить неправильную вставку / балансировку Java AVL Tree

Question

Я пишу дерево AVL для домашней работы, но, похоже, я не получаю желаемых результатов. По какой-то причине балансировка не похожа на пример, приведенный в классе. Вот мой код:

public AVLInsert(File inputFile)
{
    try 
    {
        Scanner scanner = new Scanner(inputFile);
        PrintWriter writer = new PrintWriter(new File("output.txt"));

        AVLNode node = null;

        while (scanner.hasNextInt())
        {
            if (node == null)
            {
                node = new AVLNode(scanner.nextInt());
            }
            else
            {
                node.insert(scanner.nextInt(), node); // probably broken
            }

            String output = node.printTree(node);
            System.out.println(output);
            writer.println(output + "");

        }

        scanner.close();
        writer.close();

    }
    catch (Exception e)
    {
        e.printStackTrace();
    }
}

AVLNode:

public class AVLNode 
{

// 2 pointers for left and right nodes
AVLNode left, right;
int key, balance;
boolean h;

public AVLNode()
{
    left = null;
    right = null;
    key = 0;
    balance = 0;
    h = true;
}

public AVLNode(int key)
{
    left = null;
    right = null;
    this.key = key;
    balance = 0;
    h = true;
}

AVLNode insert(int k, AVLNode p)
{
    if (p == null)
    {
        // insert k at p;
        p = new AVLNode(k);
    }
    else if (k < p.key)
    {
        p.left = insert(k, p.left);

        if (p.h)
        {
            switch (p.balance)
            {
            case 0:
                p.balance--;
                break;

            case 1:
                p.balance = 0;
                p.h = false;
                break;

            case -1:
                AVLNode p1 = p.left;

                if (p1.balance == -1)
                {
                    // do LL
                    LL(p, p1);
                }
                else 
                {
                    // do LR
                    LR(p, p1);
                }
                break;
            }
        }
    }
    else 
    {
        p.right = insert(k, p.right);

        if (p.h)
        {
            switch (p.balance)
            {
            case 0:
                p.balance++;
                break;

            case -1:
                p.balance = 0;
                p.h = false;
                break;

            case 1:
                AVLNode p1 = p.right;

                if (p1.balance == 1)
                {
                    // do RR
                    RR(p, p1);
                }
                else 
                {
                    // do RL -- assuming it's opposite of LR
                    RL(p, p1);
                }
                break;
            }



        }
    }

    return p;
}

void LL(AVLNode p, AVLNode p1)
{
    p.left = p1.right;
    p1.right = p;
    p = p1;
    p.h = false;
}

void LR(AVLNode p, AVLNode p1)
{
    // do LR
    p1 = p.left;
    AVLNode p2 = p1.right;
    p1.right = p2.left;
    p.left = p2.right;
    p2.right = p;
    p2.left = p1;


    switch (p2.balance)
    {
    case 0:
        p.balance = 0;
        p1.balance = 0;
        break;
    case -1:
        p.balance = 1;
        p1.balance = 0;
        break;
    case 1:
        p.balance = 0;
        p1.balance = -1;
        break;
    }

    p = p2;

    p.balance = 0;
    p.h = false;
}

void RR(AVLNode p, AVLNode p1)
{
    p.right = p1.right;
    p1.left = p;
    p = p1;
    p.h = false;
}

void RL(AVLNode p, AVLNode p1)
{
    p1 = p.right;
    AVLNode p2 = p1.left;
    p1.left = p2.right;
    p.right = p2.left;
    p2.left = p;
    p2.right = p1;


    switch (p2.balance)
    {
    case 0:
        p.balance = 0;
        p1.balance = 0;
        break;
    case -1:
        p.balance = 0;
        p1.balance = 1;
        break;
    case 1:
        p.balance = -1;
        p1.balance = 0;
        break;
    }


    p = p2;

    p.balance = 0;
    p.h = false;
}

String printTree(AVLNode p)
{
    String output = "";

    if (p != null)
    {
        output += p.key + "(" + printTree(p.left) + ")(" + printTree(p.right) + ")";
    }

    return output;
}

}

Введите:

5 6 8 3 2 4 6 7

Мой вывод:

5()()
5()(6()())
5()(8()())
5(3()())(8()())
5(3(2()())())(8()())
5(3(2()())(4()()))(8()())
5(3(2()())(4()()))(8(6()())())
5(3(2()())(4()()))(8()())

Что должно быть:

5()() 
5()(6()()) 
6(5()())(8()()) 
6(5(3()())())(8()()) 
6(3(2()())(5()()))(8()()) 
5(3(2()())(4()()))(6()(8()())) 
5(3(2()())(4()()))(7(6()())(8()()))

Кто-нибудь имеет представление о том, почему мои результаты отличаются от примера? Я чувствую, что это как-то связано с моими вращениями RL LR, но любая помощь приветствуется!