수다닷컴

프로그램 작성시 입력은 C:\input.text에서 받고 C:\output.text에서 출력한다

Binary Search Tree의 Insertion 및 Deletion에 대해다음 진행한다.

1. Input은 아래 예제와 같이
Insertion 및 Deletion의 총 개수, Insertion 및 Deletion의 sequence이다.
“Insertion 및 Deletion 순서”에서 양수는 Insertion, 음수는 Deletion은 나타낸다.

Input 예제)
13 // Insertion 및 Deletion의 총 개수
40 20 (60) 30 (10) 70 50 55 -10 45 -27 52 -60 // Insertion 및 Deletion 순서

2. Output은 아래 예제와 같이
최종 Binary Search Tree를 Level order traversal로 방문한 결과를 출력한다.

Output 예제)
40 20 55 30 50 70 45 52

3. 주의사항
- Input 예제의 -27과 같이 Delete하려는 값이 Tree에 없으면 무시한다.
- Insertion은 항상 Leaf node에서 이루어진다.
- Internal node x의 Deletion은
1) Left subtree가 있으면 Internal node x를 Left subtree의 제일 큰 node로 변경
2) Left subtree가 없으면 Internal node x를 Right subtree의 제일 작은 node로 변경

신청하기