0-2 이진트리(binary tree)는 다음과 같이 정의된다.

(1) 항상 루트노드(root node)가 지정되어 있다. (2) 모든 내부노드(internal node)는 반드시 두 개의 자식노드(child node)를 가지며, 왼쪽 자식노드와 오른쪽 자식노드를 구분한다.

이러한 0-2 이진트리의 루트노드 혹은 루트노드의 오른쪽 자식노드에서 좌회전 연산과 우회전 연산 은 아래 <그림 1>과 같이 표현된다.

<그림 1-(a)> 이진트리의 노드 'a'에서 좌회전 연산은 (1) 노드 'a'의 자리에 노드 'b'를 위치하게 하고, (2) 노드 'a'를 노드 'b'의 왼쪽 자식노드로 만들며, (3) 노드 'b'의 왼쪽 부트리(subtree) T2를 노드 'a'의 오른쪽 부트리로 만든다.

<그림 1-(a)> 트리의 노드 'a'에 좌회전 연산을 적용하면 <그림 1-(b)> 이진트리로 변환된다.

이와 유사하게 우회전 연산을 정의할 수 있다. 위 <그림 1-(b)> 이진트리의 노드 'b'에서 우회전 연 산은 (1) 노드 'b'의 자리에 노드 'a'를 위치하게 하고, (2) 노드 'b'를 노드 'a'의 오른쪽 자식노드로 만들며, (3) 노드 'a'의 오른쪽 부트리 T2를 노드 'b'의 왼쪽 부트리로 만든다.

<그림 1-(b)> 트리의 노드 'b'에 우회전 연산을 적용하면 <그림 1-(a)> 이진트리로 변환된다.

같은 개수의 노드를 가지는 두 개의 0-2 이진트리가 있을 때, 이 두 이진트리의 회전거리는 한 트리 의 루트노드 혹은 루트노드의 오른쪽 자식노드에 좌회전 혹은 우회전 연산을 적용하여 다른 트리로 만 드는 회전연산의 최소 회수를 나타낸다.

예를 들면, 다음 쪽의 <그림 2-(a)> 트리를 <그림 2-(g)> 트리로 변환하기 위해서는 <그림 2>에서 와 같이 6번의 좌/우회전 연산을 적용하면 된다. 또한 6번 이하 회수의 회전 연산을 사용하여서는 변환 할 수 없으므로, 두 트리 사이의 회전거리는 6이다.

두 개의 0-2 이진트리가 주어졌을 때, 두 트리 사이의 회전거리를 계산하는 프로그램을 작성하시오.

#1609 upload 6 done - how_to_reg -

트리회전 timer 1s memory 128MB

#1609

트리회전 1s 128MB