서로 다른 키 1, 2, 3, 4, 5를 이 순서대로 빈 트리에 삽입한다. 별도의 균형 조정이 없을 때 최악의 검색이 선형 시간까지 늘어날 수 있는 구조는?

1. 1

   일반 이진 탐색 트리

   정답 근거일반 이진 탐색 트리는 삽입 순서에 따라 연결 리스트처럼 편향되어 최악 검색이 O(n)이 된다.
2. 2

   AVL 트리

   오답 이유AVL 트리는 회전으로 각 노드의 높이 차를 제한해 검색 높이를 O(log n)으로 유지한다.
3. 3

   2-3 트리

   오답 이유2-3 트리는 모든 리프의 깊이가 같도록 분할·병합하는 균형 다진 탐색 트리다.
4. 4

   레드-블랙 트리

   오답 이유레드-블랙 트리는 색 규칙과 회전으로 루트-리프 경로 길이를 제한해 O(log n) 검색을 보장한다.