C# AVL-Tree: Method slowing down my program but why?

Question

My ConsoleApplication makes an correct AVL-Tree from input. For my university I need to make an program which:

• insert data correct in an AVL-Tree
• keep it balanced
• give output fast enough and correct to certain input

---

My question is why does the method/part of my program which I introduce later in this topic is so so very slow(96% of totaltime program run)?

Other methods/parts in my program who also uses treewalks takes around 0.05% or less of my program

---

I will explain the part/method "rank of node in tree" the one which accordingly to DotTrace(analytics tool) this method takes 96% of my whole program(all other methods takes around 0.05% or less). And that's why I get a timeLimit on my assignment when submitted with dumjudge system.

---

• if input line starts with T: insert new node in AVL tree

---

• if input line starts with G: derterminate rank of the specified node rank is number of people who got a higher score than you +1 than output with Console.Writeline(variable);

  example:

• node values: x(10) y(5) z(2) k(5) l(4) m(9)

• node ranks: X(1) y(3) z(6) k(3) l(5) m(2)

---

• if input line starts with something else: no need for explain this part works correct

---

I have tried a lot of things but i cannot see why its to slow I hope you guys can help me let me see what I am doing wrong.

---

variables:

• MyAVLTree T: contains the root of the AVL-tree
• MyNode NodeX, contains the node from which we want to determine the rank
• Int compareVAlue, is the value of nodeX which we compare to other nodes to determine if its higher(counter++) or lower(do nothing)

When there are no more higher nodes than nodeX the method will return the counter variable which contains the rank of the node so it can be printed as output.

---

all inputlines that produces output or insert data in AVL tree takes around 0.05% or less of my program... except the method/part of my program that produces/returns the rank of a node in the AVL-Tree(96%)

I hope my code is readable, thanks in advance for your help and time.

---

 public static int RankElement(MyAVLTree T, MyNode nodeX, int compareValue)
    {
        int counter = 1;

        while (true)
        {
            if (nodeX == T.root)
            {
                UnkownTreeWalk(T, nodeX.Right, compareValue, ref counter);
                return counter;
            }
            else if (nodeX == nodeX.Parent.Right)
            {
                UnkownTreeWalk(T, nodeX.Right, compareValue, ref counter);

                while (nodeX == nodeX.Parent.Right)
                {
                    nodeX = nodeX.Parent;
                    if (nodeX == T.root)
                    {
                        return counter;
                    }
                }
                nodeX = nodeX.Parent;
                if (nodeX.playerScore > compareValue)
                    counter++;
            }
            else
            {
                UnkownTreeWalk(T, nodeX.Right, compareValue, ref counter);

                nodeX = nodeX.Parent;
                if (nodeX.playerScore > compareValue)
                    counter++;
            }
        }


    }

    public static void UnkownTreeWalk(MyAVLTree T, MyNode nodeX, int compareValue, ref int counter)
    {
        if (nodeX != null)
        {
            if (nodeX.playerScore > compareValue)
            {
                counter++;
            }
            UnkownTreeWalk(T, nodeX.Right, compareValue, ref counter);

            UnkownTreeWalk(T, nodeX.Left, compareValue, ref counter);
        }
    }

Answer 1

There's three things to look into.

First, you have some conditionals that I think are unnecessary. In UnknownTreeWalk, we check if the node's value is less than compareValue. However, compareValue is the value of the initial node, and when we call UnknownTreeWalk we are always to the right of that initial node. Being to the right implies that its value is larger, so the check is unnecessary. There may be some similarly tiny changes that you can make to make things a bit snappier.

Second, you might have lots of CPU cache misses. You could try to arrange for your TreeNodes to be arranged contiguously in memory. This probably isn't a big deal in your case.

Third, and most importantly, I suspect you're spending a lot of time running around trees working around what size they are. You could keep the size of each subtree in it's MyNode object, then just consult it instead of going all over the place counting. It's this that I think is most likely to get you where you need to be quickly.

Finally, there's probably a vastly simpler implementation of Rank possible. I'd encourage you to take what you've learned about the problem from this implementation, and write a new one thinking about those learnings and about counting all the nodes to the right of this one.