4488
правок
Обмен ближайшими соседями и относительные расстояния: различия между версиями
Перейти к навигации
Перейти к поиску
Обмен ближайшими соседями и относительные расстояния (посмотреть исходный код)
Версия от 18:14, 26 декабря 2015
, 26 декабря 2015→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
Операция обмена ближайшими соседями (nni) обменивает два поддерева, разделенных внутренним ребром (u, v), как показано на рис. 1. | Операция обмена ближайшими соседями (nni) обменивает два поддерева, разделенных внутренним ребром (u, v), как показано на рис. 1. | ||
Считается, что операция nni действует на это внутреннее ребро. Расстояние обмена ближайшими соседями, | Считается, что операция nni действует на это внутреннее ребро. Расстояние обмена ближайшими соседями, <math>D_{nni}(T_1, T_2) \;</math>, между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> определяется как минимальное число операций nni, необходимое для преобразования одного дерева в другое. | ||
Операцию обмена ближайшими соседями также можно рассматривать как перемещение поддерева за соседнюю внутреннюю вершину. Более общая операция перемещает поддерево из одной точки дерева в другую произвольную точку. На рис. 2 представлена такая операция переноса поддерева. | Операцию обмена ближайшими соседями также можно рассматривать как перемещение поддерева за соседнюю внутреннюю вершину. Более общая операция перемещает поддерево из одной точки дерева в другую произвольную точку. На рис. 2 представлена такая операция переноса поддерева. | ||