[2019 5급 공무원 2차] 자료구조론 제 4문

2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 4문

​

제 4 문. 다음과 같은 순서로 데이터를 탐색 구조에 삽입할 때, 물음에 답하시오. (총 20점)

​

7,5,11,10,2,3,6,8,15,13

 

정답 )

주어진 데이터를 삽입한 각 트리에 대한 결과이다.

​

* 이진 탐색 트리 (Binary Search Tree)

 

 

 

 

 

* 최소 힙

 

 

 

 

 

 

 

* AVL 트리

 

 

 

 

* 레드블랙 트리 (Red-Black Tree)

문제에서는 레드 링크를 이중 실선으로 표시하라 하였지만 편의상 실제 노드의 색으로 표현한 결과 트리이다.

 

 

 

 

2) n개의 원소가 삽입되어 있는 이진 탐색 트리, 최소 힙, AVL 트리, 레드블랙 트리에 새로운 원소를 삽입할 때, 최악의 경우의 시간복잡도를 빅오(Big-Oh)표기법으로 표현하시오.

 

정답 )

 

 

 

참고 자료

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Data Structure Visualization