algorithm - 二分探索木に n 個の数値を挿入する複雑さ

Question

質問があり、「二分探索木に n 個の数値を挿入するプロセスの厳しい時間の複雑さを計算してください」と書かれています。これがバランスのとれた木であるかどうかを示すものではありません。では、そのような質問にはどのような答えを与えることができますか? これがバランスの取れたツリーである場合、高さは logn であり、n 個の数値を挿入するには O(nlogn) の時間がかかります。しかし、これはアンバランスで、最悪の場合、O(n ^{2 ) 時間かかることもあります。}n 個の数値を bst に挿入する際の時間の複雑さを見つけるとはどういう意味ですか? 何か不足していますか？ありがとう

Answer 1

ツリーのバランスが取れていても、O(n^2) になる可能性があります。

並べ替えられた数字のリストを追加するとします。これらはすべて、ツリー内の最大の数字よりも大きくなっています。その場合、すべての数値はツリーの右端の葉の右の子に追加されるため、O(n^2) になります。

たとえば、数値 [15..115] を次のツリーに追加するとします。

数字は長いチェーンとして追加され、各ノードには右側の子が 1 つあります。リストの i 番目の要素については、~i ノードをトラバースする必要があり、O(n^2) になります。

一般に、挿入と取得を O(nlogn) に保ちたい場合は、Self Balancing treesを使用する必要があります。