PQ Tree

                          PQ Tree
                        philipsweng

PQ 트 리 는 서열 을 모두 배열 하여 일부 관건 점 을 한데 배열 하 는 문 제 를 해결 하 는 데이터 구조 입 니 다.
구체 적 인 조작.우 리 는 PQ 트 리 의 점 을 P, Q 두 가지 유형 으로 나 누 었 다. P 유형 은 아들 이 임의로 순서대로 배열 할 수 있다 는 것 을 나타 내 고 Q 유형 은 아들 이 왼쪽 에서 오른쪽으로 배열 하거나 오른쪽 에서 왼쪽으로 배열 할 수 있다 는 것 을 나타 낸다.또한 PQ 나무의 한 잎 은 전체 배열 의 한 요 소 를 나타 낸다.최종 실행 가능 한 방안 은 PQ 트 리 의 우선 순위 입 니 다.
우리 가 새로운 점 집 S 를 받 아들 일 때, 우 리 는 S 중의 점 을 치밀 하 게 배열 해 야 한 다 는 것 을 나타 낸다.우 리 는 각 점 에 대해 하나의 값 Bel 을 유지 합 니 다. 이 점 의 하위 나무의 잎 이 모두 관건 이 라면 Bel = 1, 하위 나무 에 관건 이 없 으 면 0 입 니 다. 그렇지 않 으 면 2 입 니 다.
우 리 는 나무의 형 태 를 어떻게 조정 하여 현재 의 구속 을 합 법 적 으로 할 것 인 가 를 고려 합 니 다.우 리 는 현재 노드 의 상태 분류 에 대해 토론 한다.우리 의 목적 은 노드 트 리 의 관건 적 인 노드 를 함께 배열 하 는 것 이다.만약 에 Q 류 노드 라면 우 리 는 왼쪽 에서 오른쪽으로 Q 의 아들 의 정 보 를 판단 합 니 다. 우 리 는 아들 의 정 보 를 계속 분류 하여 토론 합 니 다. 현재 노드 의 사 이 드 집합 을 E (E 순서 가 있 음) 로 설정 하고 E1 0 으로 배열 합 니 다. 만약 에 우리 가 이전에 아들 이 0 이 아니 었 다 면 예전 의 관건 적 인 부분 은 여기 서 이미 연결 되 었 습 니 다.E1 에 이 노드 1 을 추가 합 니 다. 만약 에 이전에 관건 적 인 노드 배열 이 끝 났 으 면 우 리 는 지금 또 하나의 관건 적 인 노드 가 많 으 면 불법 입 니 다.그렇지 않 으 면 E1 에 이 노드 를 추가 합 니 다.2: 불법 상황 은 1. 주의해 야 할 것 은 만약 에 2 가 나타 나 고 전에 0 점 이 아 닌 것 이 발생 하면 우리 의 관건 적 인 노드 의 배열 도 끝나 야 한 다 는 것 이다.이 동시에 우 리 는 E1 에 이 노드 의 아들 이 왼쪽 (또는 오른쪽) 에 있 는 순서 (이 단 계 는 재 귀적 으로 처리 해 야 합 니 다. 왜냐하면 우 리 는 그 나무 가 모두 왼쪽 (또는 오른쪽) 에 있어 야 하기 때 문 입 니 다)
현재 P 클래스 노드 라면 Q 클래스 노드 T 를 새로 만 들 고 T 의 변 집합 을 L 로 설정 해 야 합 니 다.우 리 는 먼저 첫 번 째 2 번 노드 P 를 찾 았 다. 이 노드 는 모두 오른쪽 에 있어 야 한다.우리 가 L 에 P 를 넣 은 아들 은 모두 오른쪽 뒤에 있 습 니 다.이어서 우 리 는 P 클래스 노드 T1. E 의 1 번 노드 를 모두 T1 의 변 집중 에 연결 합 니 다.우 리 는 T1 을 L 에 추가 합 니 다. (L 은 순서 가 있 습 니 다. 주의) 우 리 는 다음 2 번 노드 P1 을 모두 왼쪽 에 두 어야 합 니 다.우리 가 L 에 P1 을 넣 은 아들 은 모두 왼쪽 뒤에 있 습 니 다.우 리 는 T 를 E1 에 넣 을 것 이다.마지막 으로 E 의 0 번 노드 를 모두 E1 에 추가 합 니 다.
우 리 는 지금 함수 RotateL (X, E) 을 고려 하고 있 습 니 다. 우 리 는 X 의 하위 트 리 의 관건 적 인 노드 가 모두 왼쪽 에 연속 적 으로 기대 어 E 에 가입 하 는 것 을 말 합 니 다.우 리 는 여전히 X 의 상황 을 분류 토론 해 야 한다.X 가 2 번 노드 보다 많 으 면 이 함수 가 불법 임 이 분명 하 다.그렇지 않 으 면 X 가 Q 류 노드 이 고 T 가 X 인 사 이 드 집합 은 Q 류 노드 가 좌우 로 뒤 집 힐 수 있 기 때문에 우리 가 왼쪽 에서 오른쪽으로 안 되면 우 리 는 사 이 드 집합 을 뒤 집 은 후에 다시 할 것 이다.우선 T 중 1 번 노드 가 T 의 맨 왼쪽 에 연속 으로 배열 되 어 있 지 않 으 면 불법이다.그렇지 않 으 면 우 리 는 E 에 T 의 1 번 노드 를 순서대로 추가 합 니 다.이어서 우 리 는 T 중의 2 번 노드 가 모두 1 번 노드 뒤에 있어 야 한다.그리고 우 리 는 모두 왼쪽 이 필요 하 다.그러면 우 리 는 RotateL (P2, E) 을 재 귀적 으로 처리 합 니 다. 그 다음 에 우 리 는 0 번 노드 를 E 에 삽입 하면 됩 니 다.

 X P   。
      P   Y.
 T 1       Y    。
    Y  E 。
          RotateL(P2，E)，  P2 T  2   。
       P   Z
 T 0       Z    。
  Z  E 。

        。

PQ 트 리 의 정 수 는 노드 를 두 가지 로 나 누고 분류 토론 하 는 데 있다.실질 을 알아차리다.연습 문제: CF 243 E