데카르트(카테시안) 트리 timer 1s memory 256MB

이번에 소개 하는 트리는 이진 탐색트리 중에서 특이한 특성을 가지는 트리이다.

이진탐색트리의 경우 임의의 노드 x에 대해, 

x의 왼쪽 부트리(자신의 노드에 바로 달려 있는 하나의 자식 노드와 이에 달려 있는 모든 노드들의 집합)의 키 값은 x 의 키값보다 작으며, 

x의 오른쪽 부트리의 값은 x 의 키값보다 크다.

다시 말해서 L(x)를 노드 x의 왼쪽 부트리라고 하고, R(x)를 노드 x의 오른쪽 부트리라고 하고, k_x는 노드 x의 키값이라고 하면 다음과 같은 관계가 성립되어야 이진 탐색 트리라는 것이다.

• 만약 노드 y 가 L(x) 에 속해 있으면 k_y < k_x 여야 한다.

• 만약 노드 z 가 R(x) 에 속해 있으면 k_z > k_x 여야 한다.

이러한 이진 탐색 트리에서의 모든 노드 x가 기본키 k_x 를 가지고 이와 함께 보조키 a_x 를 가지고 있을 때 보조키 a_x 들이 다음과 같은 조건을 만족시키면 이를 데카르트 트리라고 한다.

• y 가 x 의 부모 노드일 경우 a_y < a_x 이다.

따라서 데카르트 트리는 각 노드 x에 대해가 2개의 키(k_x,\ a_x)의 쌍으로 이뤄지고, 위의 모든 조건을 만족 시키는 방향성과 순서적인 특징을 가진 트리라고 할 수 있다.

임의의 노드 x에 대한 (k_x,\ a_x)의 쌍이 여러 개 주어졌을 때, 이를 통해 데카르트 트리를 만들 수 있는지 없는지 판단하는 프로그램을 작성하라.