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

부모를 표시하지 않는 상태로 부모를 표시하는 동안 모든 잎을 먼저 가져 와서 제거한 다음 잎이 남지 않을 때까지 표시된 모든 잎을 제거한 다음 트리가 비어있을 때까지 반복합니다. 나는 이것이 항상 가능한 가장 큰 세트를 생산한다는 증거가 없지만 그것이 가능해야한다고 생각합니다.