<보기>에서 이진 트리(binary tree)의 성질에 대한… | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
<보기>에서 이진 트리(binary tree)의 성질에 대한 설명으로 옳은 것을 모두 고른 것은? (단, 트리의 높이는 루트 노드의 레벨을 1로 하여 계산한다.)ㄱ. 총 개의 노드를 가진 이진 트리의 높이()는 적어도 이다.
ㄴ. 완전 이진 트리(complete binary tree)에서 모든 단말 노드는 항상 같은 레벨에 존재한다.
ㄷ. 이진 탐색 트리(binary search tree)의 삽입에 드는 점근적 시간은 검색에 드는 시간과 동일하다.
ㄹ. 개의 노드를 가진 이진 탐색 트리의 점근적 평균 검색 시간은 이다.
1
ㄱ
2
ㄱ, ㄷ
3
ㄴ, ㄹ
4
ㄱ, ㄷ, ㄹ
해설
옳은 것은 ㄱ, ㄷ이다.
높이 인 이진 트리의 최대 노드 수는 이므로 , 즉 이다. 이진 탐색 트리의 삽입은 탐색으로 자리를 찾은 뒤 상수 시간에 연결하므로 검색과 점근적 시간이 같다.
- ㄴ: 완전 이진 트리는 마지막 레벨을 왼쪽부터 채우므로 단말 노드가 마지막 두 레벨에 걸쳐 있을 수 있다.
- ㄹ: 이진 탐색 트리의 평균 검색 시간은 이며, 은 한쪽으로 치우친 최악의 경우이다.
오류나 개정된 내용이 보이면 알려주세요