Хрестоматия алгоритмов, связанных с двоичным деревом поиска
, нужны возможные названия операций
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [18.226.96.61] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
| Страницы: (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) - странно все это)) |
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0,0347 ] [ 16 queries used ] [ Generated: 19.04.24, 09:54 GMT ]