Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.188.148.71] |
|
Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Сообщ.
#16
,
|
|
|
Т.е. пункт с перемещением узлов отпадает, да? |
Сообщ.
#17
,
|
|
|
Цитата Akina @ Я имел в виду не одиночный узел, а всё поддерево от указанного узла до листьев. На место существующей Null-ссылки листа или неполного узла. Ну и более сложный вариант - взаимное перемещение (обмен) двух узлов. Сюда же можно добавить и копирование ветви в указанное место. И какие из этих операций можно применить на ДДП (+ демонстрация принципа действия)? |
Сообщ.
#18
,
|
|
|
Еще встретил одну операцию: проверка бинарного дерева на то, что это ДДП, а не простая бинарка
|
Сообщ.
#19
,
|
|
|
Оказывается очень популярная операция в ДДП - нахождение пути (по различным критериям).
Какова сложность операции? Пусть в дереве n - узлов. В любом случае придется перебрать их все, это О(n). И для каждого узла искать высоты левого и правого поддерева. Какой здесь худший случай - не знаю, наверное брать по n/2 для обоих поддеревьев (хотя в реальности гораздо меньше, конечно), в итоге получается O(n * (n/2 + n/2) = O(n * n) = O(n^2) - странно все это)) |