PQ 트리

PQ tree

PQ 트리는 켈로그 S에 의해 발견되고 명명된 원소 집합의 순열 집단을 나타내는 트리 기반의 데이터 구조다. 부스와 조지 S. 1976년 [1]루에커뿌리째 뽑은 라벨이 붙은 나무로, 각 원소는 잎 노드 중 하나로 표시되며, 잎이 아닌 노드 각각은 P 또는 Q로 표시된다. P 노드에는 최소 두 개의 자식이 있고, Q 노드 한 개에는 최소 세 개의 자식이 있다.

PQ 트리는 그 노드의 자식들의 허용 가능한 재정렬을 통해 그 순열을 나타낸다.P 노드의 자녀는 어떤 방식으로든 재주문될 수 있다.Q 노드의 자녀는 역순으로 배열할 수 있지만 다른 순서로 순서를 변경할 수는 없다.PQ 트리는 이 두 가지 작업의 모든 시퀀스에 의해 달성될 수 있는 모든 리프 노드 순서를 나타낸다.P와 Q 노드가 많은 PQ 트리는 가능한 모든 주문 집합의 복잡한 하위 집합을 나타낼 수 있다.그러나 모든 순서가 이러한 방식으로 표현되는 것은 아니다. 예를 들어 순서가 PQ 트리로 표현되는 경우 순서의 역순도 동일한 트리로 표현되어야 한다.

PQ 트리는 다양한 제약을 만족시키는 순서를 찾는 것이 목표인 문제를 해결하기 위해 사용된다.이러한 문제에서, 제약조건을 만족시키는 순서만을 나타내는 방식으로 PQ 트리 구조를 수정함으로써, 순서에 대한 제약조건이 한 번에 하나씩 포함된다.PQ 트리의 적용은 DNA 조각으로부터 콘티그 맵 생성,[2] 연속적인 특성에 대한 행렬 테스트, 구간 그래프 인식, 그래프가 평면인지 여부를 결정하는 것이다.[1]

예시 및 표기법

나타내는 PQ 트리
[1 (2 3 4) 5]

PQ 트리의 모든 잎이 루트 P 노드에 직접 연결된 경우 가능한 모든 순서가 허용된다.모든 잎이 루트 Q 노드에 직접 연결되면 하나의 주문과 그 역순만 허용된다.다른 모든 리프 노드가 루트에 직접 연결된 상태에서 루트 P 노드에 연결되는 P 노드에 노드 a,b,c가 연결되는 경우, a,b,c가 연속되는 모든 순서가 허용된다.

그래픽 표시를 사용할 수 없는 경우 중첩된 괄호화 목록을 사용하여 PQ 트리를 종종 기록한다.일치하는 각 쌍의 사각 괄호는 Q 노드를 나타내며, 일치하는 쌍의 둥근 괄호는 P 노드를 나타낸다.잎은 목록의 비 괄호 요소다.왼쪽의 이미지는 [1 (2 3 4) 5]로 이 표기법으로 표현된다.이 PQ 트리는 {1, 2, 3, 4, 5 세트에서 다음과 같은 12개의 순열을 나타낸다.

12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.

PC 트리

위관시와 원리안 슈가 개발한 PC 트리는 PQ 트리를 보다 최근에 일반화한 것이다.PQ 트리와 마찬가지로 나무에서 노드를 재정렬하여 순열을 나타내며, 나무의 잎에 원소가 표시된다.PQ나무와 달리 PC나무는 뿌리가 없다.P 라벨이 부착된 비잎 노드에 인접한 노드는 PQ 트리에서처럼 임의로 재주문할 수 있는 반면, C 라벨이 부착된 비잎 노드 근처의 노드는 고정된 주기적 순서를 가지며 이 순서를 거꾸로 하여만 재주문할 수 있다.따라서 PC 트리는 집합에서 주문의 원형 순열 또는 역순서도 집합에 있는 순서 집합만 나타낼 수 있다.그러나 n개 요소의 PQ 트리는 n+1 요소의 PC 트리에 의해 시뮬레이션될 수 있으며, 여기서 추가 요소는 PC 트리의 루트를 형성하는 역할을 한다.PC 트리에서 평면성 시험 알고리즘을 수행하는 데 필요한 데이터 구조 운영은 PQ 트리의 해당 운영보다 다소 간단하다.[3]

참고 항목

참조

  1. ^ a b Booth, Kellogg S.; Lueker, George S. (1976). "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms". Journal of Computer and System Sciences. 13 (3): 335–379. doi:10.1016/S0022-0000(76)80045-1.
  2. ^ Karp, Richard M. (1993). "Mapping the genome: some combinatorial problems arising in molecular biology". In Kosaraju, S. Rao; Johnson, David S.; Aggarwal, Alok (eds.). Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA. Association for Computing Machinery. pp. 278–285. doi:10.1145/167088.167170.
  3. ^ Shih, Wei-Kuan; Hsu, Wen-Lian (1999). "A new planarity test" (PDF). Theoretical Computer Science. 223 (1–2): 179–191. doi:10.1016/S0304-3975(98)00120-0.

외부 링크