最小ノードから BST で n-1 回の後継者を見つけることが O(n) であることを証明する方法は?
問題は、ソート順を作成できることです
1) ノード = BST の最小ノードとします。
2) そのノードから、後継者の検索を再帰的に呼び出します。
結果はO(n)と言われたのですが、意味がわからず、証明の仕方もわかりません。
代わりに O(n*log n) であるべきではありませんか? ステップ 1 の場合はO(log n)であるため、ステップ 2 の場合もO(log n)ですが、n-1回呼び出されます。したがって、O(n*log n)になります。
私の疑問を明確にしてください。ありがとうございました！:)