체크 2 경우 트리 노드가 O으로 (상위/하위) 관계 (1)

Question

체크 2 경우 트리 노드는 관련된 사전 처리 (즉, 조상 자손)와

• 은 O에서 해결 (1) 시간과 O (N)의 공간 (노드 N = #)
• 전처리는 그것의

허용된다. 나는 아래의 나의 해결책 (접근)으로 갈 것이다. 먼저 자신을 생각하고 싶다면 그만하십시오. 사전 처리를 위해

---

나는 (재귀 다음, 먼저 루트를 통해 아이들을 이동) 및 각 노드에 라벨을주는 사전 주문을하기로 결정했다.

라벨을 자세히 설명해 드리겠습니다. 각 레이블은 "1,2,1,4,5"와 같이 쉼표로 구분 된 자연 숫자로 구성됩니다.이 시퀀스의 길이는 (노드의 깊이 +1)과 같습니다. 예 : 루트의 레이블은 "1", 루트의 자식은 레이블 "1,1", "1,2", "1,3"등을 가질 것입니다. 다음 레벨 노드는 "1,1,1" ..., "1,2,1", "1,2,2"...

노드의 "주문 번호"은 해당 부모의 자식 목록에서 "이 노드의 1부터 시작하는 인덱스"

공통 규칙 : 노드의 레이블은 노드의 부모 레이블과 쉼표로 구성되며 "주문 번호"노드로 구성됩니다.

O (1)에서 두 노드가 관련이 있다면 (예 : 조상 - 자손), 그 중 하나의 레이블이 다른 레이블의 "접두어"인지 확인합니다. 비록 그러한 레이블이 O (N) 공간을 점유하는 것으로 간주 될 수 있는지 확실하지 않지만.

수정 프로그램이나 대체 접근법이있는 비평가가 필요합니다.

Answer 1

당신은 O (n)의 전처리 시간에 그것을 할 수 있고, O O (1) 질의 시간 (n)이 공간,이 사실을 각 정점에 대한 예약 주문 번호와 postorder 번호를 저장하고 사용하는 경우 :

트리 T의 주어진 노드 x와 y에 대해 x는 y의 조상이고,은 T의 선주문 탐색에서 y보다 먼저 발생하고 후위 순회에서 y 이후에만 발생합니다.

(이 페이지에서 : http://www.cs.arizona.edu/xiss/numbering.htm)은 최악의 경우에 무슨 짓을

가 시타 (D)는 D 너무 높은 노드의 깊이, 그리고 O 아니다 (1). 공간도 O (n)가 아닙니다.

Answer 2

선형 시간 최저 공통 조상 알고리즘 (적어도 오프라인)이있다. 예를 들어 보면 here입니다. tarjan's offline LCA algorithm을 살펴볼 수도 있습니다. 이 기사에서는 사전에 LCA를 수행 할 쌍을 알고 있어야합니다. 온라인 선형 시간 사전 계산 시간 알고리즘이 있다고 생각하지만 매우 복잡합니다. 예를 들어 범위 최소 쿼리 문제에 대한 선형 사전 계산 시간 알고리즘이 있습니다. 지금까지이 솔루션은 LCA 문제를 두 번 통과했습니다.알고리즘의 문제점은 O (n * log (n)) 알고리즘보다 실제로 더 빠른 입력이 필요하다는 큰 상수를 가졌다는 것입니다.

O (n * log (n)) 개의 추가 메모리가 필요하며 일정 시간 내에 다시 응답하는 훨씬 간단한 방법이 있습니다.

희망이 도움이됩니다.

Answer 3

트리의 노드에 n/2 개의 자식 (말)이있는 트리를 고려하면 레이블을 설정하는 실행 시간은 O (n * n)만큼 높습니다. 그래서이 라벨링 체계는 작동하지 않을 것이다. ...