4488
правок
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 представлена такая операция переноса поддерева. |
правок