다음 트리는 노드에서 키와 값이 무엇인지 알 수는 없지만 이진 탐색 트… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
다음 트리는 노드에서 키와 값이 무엇인지 알 수는 없지만 이진 탐색 트리라고 가정했을 때, 이에 대한 설명으로 옳지 않은 것은? (단, 루트 노드만 있는 경우에 트리 높이는 0이다)
1
트리의 높이는 4이다.
2
AVL 트리에 해당한다.
3
C 노드의 중위 후속자(inorder successor)는 M 노드이다.
4
높이를 증가시키지 않고 트리에 추가할 수 있는 최대 노드 수는 18개이다.
해설
C의 중위 후속자는 오른쪽 서브트리에서 가장 왼쪽 노드인 K이므로, M이라는 설명이 옳지 않다.
C의 오른쪽 자식 G에서 왼쪽 자식을 끝까지 따라가면 K에 도달한다. M은 L의 오른쪽 자식으로 C 서브트리에서 가장 큰 노드이다.
- 트리의 높이: A-C-G-L-M 경로가 간선 4개로 가장 길어 높이 4가 맞다.
- AVL 여부: 모든 노드에서 좌우 서브트리 높이 차가 1 이하이다(A는 2와 3, C는 1과 2, G는 0과 1).
- 추가 가능 노드 수: 높이 4인 이진 트리의 최대 노드 수는 이고 현재 노드가 13개이므로 18개를 더 넣을 수 있다.
오류나 개정된 내용이 보이면 알려주세요