Вставка нового значения в бинарное дерево поиска

Question

Используя алгоритм Tree-Insert(T, v), который вставляет новое значение v в двоичное дерево поиска T, следующий алгоритм увеличивает двоичное дерево поиска путем многократной вставки каждого значения в данном разделе массива в дерево:

<b>Tree-Grow(A, first, last, T)</b><br> 1 for i ← first to last<br> 2 do Tree-Insert(T, A[i])<br>

1. Если дерево изначально пустое, а длина секции массива (т.е. последний-первый + 1) равна n, каково время выполнения асимптотического алгоритма для наилучшего и наихудшего случаев вышеупомянутого алгоритма, соответственно?

2. Когда n = 7, задайте экземпляр в лучшем случае (в виде массива, содержащего цифры от 1 до 7 в определенном порядке) и экземпляр в худшем случае (в той же форме) алгоритма.

3. Если массив отсортирован и все значения различны, найдите способ изменить Tree-Grow, чтобы он всегда создавал самое короткое дерево.

4. Каково время выполнения модифицированного алгоритма для наилучшего и наихудшего асимптотического времени соответственно?

Answer 1

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

1) Требуется O (n) для итерации от первого до последнего. Для вставки в двоичное дерево требуется O (lg n), поэтому алгоритм, который вы показали, в лучшем случае принимает O (n lg n).

Худший случай вставки в двоичное дерево - это когда дерево действительно длинное, но не очень густое; похож на связанный список. В этом случае потребуется O (n) для вставки, поэтому в худшем случае потребуется O (n ^ 2).

2) Лучший вариант: [4, 2, 6, 1, 3, 5, 7], худший вариант: [1, 2, 3, 4, 5, 6, 7]

3) Используйте индекс n / 2 в качестве корня, затем рекурсивно сделайте это для левой и правой сторон массива.

4) O (n lg n) в лучшем и худшем случаях.

Надеюсь, это поможет.