私の ConsoleApplication は、入力から正しい AVL-Tree を作成します。私の大学では、次のプログラムを作成する必要があります。
- AVL ツリーに正しいデータを挿入する
- バランスを保つ
- 出力を十分に速く与え、特定の入力に対して正しい
私の質問は、このトピックの後半で紹介するプログラムのメソッド/部分が非常に遅いのはなぜですか (合計プログラム実行時間の 96%)。
ツリーウォークも使用する私のプログラムの他のメソッド/部分は、私のプログラムの約 0.05% 以下を占めます
DotTrace（分析ツール）に応じて、このメソッドがプログラム全体の96％を占める部分/メソッド「ツリー内のノードのランク」について説明します（他のすべてのメソッドは約0.05％以下になります）。そのため、dumjudge システムで提出された課題に timeLimit が与えられます。
- 入力行が T で始まる場合: AVL ツリーに新しいノードを挿入します
入力行がGで始まる場合:指定したノードランクの決定ランクは、Console.Writeline(変数)での出力よりも+1高いスコアを獲得した人の数です。
例：
ノード値: x(10) y(5) z(2) k(5) l(4) m(9)
ノードランク: X(1) y(3) z(6) k(3) l(5) m(2)
- 入力行が何か他のもので始まる場合: この部分は正しく動作することを説明する必要はありません
私は多くのことを試しましたが、なぜ遅いのかわかりません。皆さんが私が間違っていることを教えてくれることを願っています.
変数:
- MyAVLTree T: AVL ツリーのルートが含まれます
- MyNode NodeX、ランクを決定するノードが含まれています
- Int compareVALue は nodeX の値であり、他のノードと比較して、高い (counter++) か低い (何もしない) かを判断します。
nodeX より上位のノードがなくなると、メソッドはノードのランクを含むカウンター変数を返し、出力として出力できるようにします。
AVLツリーで出力または挿入データを生成するすべての入力行は、私のプログラムの約0.05％以下を占めます... AVLツリーのノードのランクを生成/返すプログラムのメソッド/部分を除いて（96％）
あなたの助けと時間を前もって感謝します。
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);
}
}