HW09

문제)

주어진 이진 트리(binary tree)의 순회(traversal) 순서를 깨지 않고, 다음
연산을 차례로 수행합니다.
1. subtree_insert_after : insert L after A
2. subtree_delete : delete G
3. subtree_delete : delete C
• 트리의 노드 위치가 바뀔 때마다 트리의 형태를 그리고, 순회 순서를 표기
합니다.
▪ 트리 형태
▪ 순회 순서

풀이)

1. subtree_insert_after : insert L after A

순회 순서는
B D A G E J H K C F I
이다.

A 다음에 L을 넣고자 하므로 순회 순서는
B D A L G E J H K C F I
이 된다.

A에게는 RIGHT CHILD가 있으므로 C로 노드를 옮긴다.
이제 ITER(C.LEFT)는 G이므로 G의 LEFT CHILD로 L을 추가한다.
이를 트리 형태로 나타내면

이 된다.

2. subtree_delete : delete G

현재 순회 순서는 B D A L G E J H K C F I 이다.
G를 없애고자하면 순회순서를 방해하지 않아야하는데,
이를 위해서 G의 PREDECESSOR자리와 G의 자리를 SWAP한다.
즉, L과 G의 자리를 SWAP한다.

이때의 트리 형태는

이다.

그리고 이제 G는 LEAF NODE가 되었으므로 DELETE를 수행하게 된다.
트리의 형태는

이 되고,

순회 순서는
B D A L E J H K C F I
이 된다.

3. subtree_delete : delete C

현재 순회 순서는 B D A L E J H K C F I 이다.
C에게는 SUBTREE가 두 개 있다.
바로 C를 삭제하게 된다면 순회에 문제가 생기므로 SWAP을 해서 LEAF NODE가 되도록 해야한다.
C의 PREDECESSOR인 K와 SWAP을 하게 된다면,
C는 LEAF NODE가 된다.
이 때의 트리 형태는

이고,

순회 순서는
B D A L E J H C K F I
이 된다.

그렇다면 DELETE를 하더라도 순회 순서에 문제가 생기지 않는다.

DELETE를 한 후의 트리 형태는

이고,

순회 순서는
B D A L E J H K F I
이다.