다음의 D1 ~ D4에서 제시된 키(key) 값의 순서대로 공백(emp… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 20년 1회차
다음의 D1 ~ D4에서 제시된 키(key) 값의 순서대로 공백(empty) 이진 탐색 트리(binary search tree)에 데이터를 삽입하여 T1 ~ T4를 만들었을 때, 모양이 다른 트리는? (단, 모양은 노드의 키 값과 간선의 연결 구조를 포함한다)D1: 4, 2, 3, 6, 8, 5, 7 → 이진 탐색 트리 T1
D2: 4, 2, 6, 8, 5, 3, 7 → 이진 탐색 트리 T2
D3: 4, 6, 3, 8, 2, 5, 7 → 이진 탐색 트리 T3
D4: 4, 6, 8, 5, 7, 2, 3 → 이진 탐색 트리 T4
1
T1
2
T2
3
T3
4
T4
해설
모양이 다른 트리는 T3이다.
이진 탐색 트리의 모양은 각 키가 들어갈 때 이미 있는 조상 노드와의 대소 관계로 정해진다. 루트 4의 왼쪽 부분에서 T1·T2·T4는 2가 먼저 들어가 2의 오른쪽 자식이 3이 되지만, T3는 3이 먼저 들어가 3의 왼쪽 자식이 2가 된다.
- T1(D1): 루트 4, 왼쪽 2(오른쪽 자식 3), 오른쪽 6(왼쪽 5, 오른쪽 8), 8의 왼쪽 자식 7인 구조이다.
- T2(D2): 삽입 순서만 다를 뿐 모든 키의 부모가 T1과 같아 같은 모양이다.
- T4(D4): 오른쪽 키(6, 8, 5, 7)를 먼저 넣고 2, 3을 나중에 넣어도 부모 관계가 T1과 같아 같은 모양이다.
오류나 개정된 내용이 보이면 알려주세요