차수가 4이고 높이가 4인 m원 탐색 트리가 가질 수 있는 노드의 최대… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지

노드의 최대 수는 85개이다. 차수가 4인 m원 탐색 트리는 각 노드가 최대 4개의 자식을 가지므로 레벨마다 노드 수가 4배씩 늘어난다.
높이 4(루트만 있을 때 높이 1)이면 $1 + 4 + 4^2 + 4^3 = 1 + 4 + 16 + 64 = 85$이다.
21은 높이 3까지만 더한 값(1+4+16)이다.
255는 노드 수 85에 노드당 최대 키 수 3을 곱한 키의 최대 개수로, 노드 수가 아니다.