与えられたN個の要素を持つBSTを構築するのはO（n lg n）ですか？

Question

与えられた任意のN要素でバイナリ検索ツリーを構築するのに、最悪の場合の時間の複雑さはどのくらいですか？

IはN所与の要素との間に差があると思うと要素が一つずつ来るし、それにより合計N個の要素のBSTを行います。前者の場合

、それはO（N Nログ）であり、二番目にはO（n^2）あります。私は正しい？

Answer 1

Binary Search Tree (BST)が完全にバランスしていない場合、最悪の場合の時間複雑度はO(n^2)です。一般的に、BSTは繰り返し挿入によって構築されるため、最悪の場合はO(n^2)になります。あなたは（O(nlogn)で）入力を並べ替えることができる場合でも、それはO(nlogn)

それBSTの全体的な複雑で、その結果、O(n)で構築することができ、その後、最悪の場合の時間の複雑さは、我々は挿入を繰り返している場合でもO(nlog n)で、self-balancingです。