Java-алгоритм для нахождения самого большого набора независимых узлов в двоичном дереве

Question

Под независимыми узлами я имею в виду, что возвращенный набор не может содержать узлы, которые находятся в непосредственных отношениях, родительский и дочерний не могут быть включены. Я пытался использовать Google без успеха. Я не думаю, что у меня есть правильные поисковые слова.

Ссылка, любая помощь будет очень признательна. Просто начал это сейчас.

Мне нужно вернуть фактический набор независимых узлов, а не только сумму.

Answer 1

Вы можете вычислить эту рекурсивную функцию с динамическим программированием (запоминанием):

MaxSet(node) = 1 if "node" is a leaf 
MaxSet(node) = Max(1 + Sum{ i=0..3: MaxSet(node.Grandchildren[i]) }, 
         Sum{ i=0..1: MaxSet(node.Children[i])  }) 

Идея заключается в том, вы можете выбрать узел или выбрать, чтобы не забрать его. Если вы его выберете, вы не сможете выбрать своих прямых детей, но вы можете выбрать максимальный набор от своих внуков. Если вы его не выбрали, вы можете выбрать максимальный набор из прямых детей.

Если вам нужен сам набор, вам просто нужно сохранить, как вы выбрали «Макс» для каждого узла. Он похож на LCS algorithm.

Этот алгоритм O (n). Он работает на деревьях вообще, а не только на двоичных деревьях.

Answer 2

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