Зачем O (N Log N) строить двоичное дерево поиска?

Question

Готовимся к экзамену.Это не домашнее задание.

Я подумал, что наихудший вариант O (N ^ 2) для построения BST.(каждая вставка требует сравнения N-1, вы суммируете все сравнения 0 + 1 + ... + N-1 ~ N ^ 2).Это имеет место для искаженного BST.

Вставка для (сбалансированного) BST - это O (log N), так почему наилучшим случаем является O (N logN) для построения дерева?

Полагаю, лучшая догадка - поскольку одиночная вставка - это log N, то суммирование всех вставок так или иначе дает нам N log.

Спасибо!

Answer 1

Как вы уже писали :) Одиночная вставка - это O (log N). Поскольку взвешенная высота дерева N элемента - это log N, вам нужно зарегистрировать N сравнений, чтобы вставить один элемент. Вам нужно сделать N из этих вставок. Так что N * logN.