정확히 K 잎이 들어있는 하위 트리를 선택하십시오.

Question

T은 n 개의 노드와 l 잎이있는 나무가 있습니다.

정확히 k (<=l) 잎이 들어있는 일부 하위 트리를 선택해야합니다. 노드 t의 조상의 하위 트리를 선택하면 t의 하위 트리를 선택할 수 없습니다. 예를 들어

는 :

이 13 개 노드 (7 잎)가 트리 T입니다.

k = 4 잎을 선택하려면 노드 4와 6 (또는 노드 2와 5)을 선택할 수 있습니다. 이것은 선택의 최소 수입니다. (노드 6, 7, 8, 9 중 하나를 선택할 수 있지만 최소는 아닙니다).

k = 5 잎을 선택하려면 노드 3을 선택할 수 있으며 최소 선택 개수입니다.

하위 트리의 최소 수를 선택하고 싶습니다. 나는 BFS와 동적 프로그래밍을 사용하는 O(nk^2)과 O(nk) 알고리즘 만 찾을 수 있습니다. 이것을 선택하면 더 좋은 해결책이 있습니까?

감사합니다 :)

Answer 1

사실,하면 너무 복잡 m 각 노드의 아이의 평균 숫자가 O(nm)해야 당신은 단지 각 노드 을 통과해야하는 각 서브 트리의 잎의 수를 알 수있는, m이 단지 상수이기 때문에 대부분의 경우 O(n)으로 평가됩니다. 이 작업을 수행하려면 다음을 수행해야합니다 당신의 트리 노드가 잎

는

당신은이 작업을 수행 할 수있는 하위 트리의 각 노드에 대해 잎의 수를 절약 트리를 이동하다

• 찾기 나뭇잎으로 시작하고 부모를 대기열에 넣어. 노드 n_i을 큐에서 팝하면 n_i의 하위 노드에서 시작하여 각 하위 트리에 포함 된 리프 수를 합산합니다. 작업이 완료되면 방문으로
  이

  이 이런 식으로 뭔가를 제공합니다 (이 아이 당 한 번만 추가 할 수 있기 때문에 그래서 당신은 여러 번을 방문하지 않음) n_i 표시 :

  ^ 
  |    f (3)    This node last 
  |   /\ 
  |   / \ 
  |  /  \ 
  |  /   \ 
  |  d (2)   e (1)  These nodes second 
  | /\   /
  | / \  /
  | a (1) b (1) c (1)   These nodes first 
  

  단계는 것 be :

  Find leaves `a`, `b` and `c`. 
  For each leave, add parent to queue # queue q = (d, d, e) 
  
  Pop d         # queue q = (d, e) 
  Count leaves in subtree: d.leaves = a.leaves + b.leaves 
  Mark d as visited 
  Add parent to queue     # queue q = (d, e, f) 
  
  Pop d         # queue q = (e, f) 
  d is visited, do nothing 
  
  Pop e         # queue q = (f) 
  Count leaves in subtree: e.leaves = c.leaves 
  Mark d as visited 
  Add parent to tree     # queue q = (f, f) 
  
  Pop f         # queue q = (f) 
  Count leaves in subtree: f.leaves = d.leaves + e.leaves 
  Mark d as visited 
  Add parent to tree (none) 
  
  Pop f         # queue q =() 
  f is visited, do nothing 
  

  두 번 추가 된 노드를 무시하는 스마트 데이터 구조를 사용할 수도 있습니다. "더 높은"노드 전에 "더 낮은"노드를 탐색하는 것이 매우 중요하기 때문에 정렬 된 집합을 사용할 수 없습니다.

  k 잎 이상이있는 경우 큐에있는 노드를 제거하고 찾을 수있는 각 노드를 k 잎 반환하면보다 빠른 알고리즘을 제공 할 수 있습니다.