Сортировка по: Дерево двоичного поиска

Question

Я немного смущен относительно худшего времени для случая и случайности Avg. Мой источник путаницы Here

Моя цель состоит в том, чтобы короткие данные в возрастающем порядке: я выбираю BST, чтобы выполнить мою задачу сортировки. Здесь я помещаю то, что я делаю для печати данных в порядке возрастания.

1) Construct a binary search tree for given input. 
     Time complexity: Avg Case O(log n) 
         Worst Case O(H) {H is height of tree, here we can Assume Height is equal to number of node H = n} 

2)After Finishing first work I am traversing BST in Inorder to print data in Increasing order. 
     Time complexity: O(n) {n is the number of nodes in tree} 

Now I analyzed total complexity for get my desire result (data in increasing order) is for Avg Case: T(n) = O(log n) +O(n) = max(log n, n) = O(n) 
     For Worst Case : T(n) = O(n) +O(n) = max(n, n) = O(n) 

Наверху было мое понимание, которое отличается от концепции выше ссылки. Я знаю, что я ошибаюсь. Пожалуйста, поправьте меня. Буду признателен за ваше предложение и мысль.

Пожалуйста, обратитесь это название Under Slide, который я mentined:

Answer 1

In (1) Вы предоставляете время для каждого элемента, необходимо умножить на # элементов.

Answer 2

Временная сложность, необходимая для построения двоичного дерева, в разы превышает сложность, которую вы предлагаете, поскольку вам нужно вставлять каждый узел.