이진 탐색 트리에 관한 다음 설명 중 가장 옳지 않은 것은? | [법원직 9급 전산·사서 컴퓨터일반] 26년 1회차 기출문제 상세 페이지
1[법원직 9급 전산·사서 컴퓨터일반] 26년 1회차
이진 탐색 트리에 관한 다음 설명 중 가장 옳지 않은 것은?
1
모든 노드는 키를 가지며, 그 키는 유일한 값을 가진다.
2
부모 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 부모노드의 키보다 작다.
3
자식 노드가 두 개인 경우, 삭제된 노드의 자식을 삭제된 노드의 자리에 위치시킨다.
4
균형 탐색 트리(balanced search tree)는 최악의 상황에도 탐색 시간 복잡도 을 보장한다.
해설
틀린 설명은 자식이 둘인 노드를 삭제할 때 자식을 그 자리에 올린다는 내용이다.
자식이 둘이면 왼쪽 서브트리의 최댓값이나 오른쪽 서브트리의 최솟값으로 대체해야 한다. 자식을 바로 올리는 것은 자식이 하나일 때의 처리이다.
- 키의 유일성: 이진 탐색 트리의 정의에서 모든 노드는 유일한 키를 가진다.
- 왼쪽 서브트리: 부모보다 작은 키만 모인다는 설명이 맞다.
- 균형 탐색 트리: 높이를 로그 수준으로 유지하므로 최악에도 탐색 시간이 이다.
오류나 개정된 내용이 보이면 알려주세요