найти дерево, учитывая данные на его листьях

Question

пусть будет неориентированное дерево T, и пусть будет: T.leaves - все листья (каждый v такой, что d(v) = 1). мы знаем: |T.leaves| и distance between u and v for each u,v in T.leaves.
другими словами : у нас есть ненаправленное дерево, и мы знаем, сколько у него листьев, и расстояние между каждыми 2 листьями.
нам нужно найти how many inside vertices (d(v)>1) are in the tree.

примечание: построить полное дерево невозможно, потому что если у нас всего 2 листа, но расстояние между ними составляет 2 ^ 30, это займет слишком много времени ...

Я попытался начать с кратчайшего расстояния и посчитать, сколько вершин между ними, а затем добавить ближайшую к ним вершину, но для этого мне нужна формула f (leaves_counts, next_leaf), но я не смог чтобы найти это д ...
есть идеи?

Answer 1

Продолжение обсуждения в комментариях.Это как проверить конкретное (сжатое) ребро, чтобы увидеть, можете ли вы присоединить новую вершину n где-то в середине, без итерации по расстояниям.

Итак, вам нужно найти три числа: l (расстояние от точки присоединения до левого узла рассматриваемого ребра), x (расстояние нового узла от точки присоединения) и r (симметрично l.)

Очевидно, для каждого узла y в наборе L (левая часть дерева)расстояние до A должно отличаться от расстояния до n тем же номером (назовем его dl, который должен быть равен l + x).Если это не так, то для этого конкретного ребра нет решения.То же самое касается узлов в R, с dr и r + x соответственно.

Если вышеизложенное выполняется, то у вас есть три уравнения:

l + x = dl

r + x = dr

r+l = dist(A,B)

Три уравнения, три числа.Если у этого есть решение, то вы нашли правильный край.

В худшем случае вам нужно повторить вышеупомянутое для каждого края, но я думаю, что это можно оптимизировать - проверка расстояния на L и Rможет исключить одну из частей дерева из дальнейшего поиска.Также может быть возможным получить количество узлов, даже не создавая дерево.

Answer 2

если ваше двоичное дерево имеет L листьев, то оно имеет внутренние вершины L-1 независимо от формы дерева.

Вы можете легко доказать это: начните с дерева только с одним узлом (корневым) узлом,Затем возьмите любой лист и добавьте к нему двух потомков, превратив лист во внутреннюю вершину и добавив к листам.Это удаляет один лист (старый узел) и добавляет один внутренний узел и два листа, то есть сеть равна +1 внутреннему узлу и +1 листу.Поскольку вы начинаете с одного листа и 0 внутренних узлов, у вас всегда есть | листья |= | внутренние узлы | +1 --- этим процессом может быть получена любая форма дерева.

Здесь приведены примеры всех двух форм деревьев с 4 листьями (за исключением тривиальных симметрий слева-справа):

    o        o
   o L      o o
  o L     L L L L
 L L

Количество внутренних вершин всегда равно 3.