방송대 방통대 자료구조 13강 - 멀티웨이 탐색 트리 II - 요약 노트 시험족보 예상문제 - 올에이클래스

자료구조 13강 - 멀티웨이 탐색 트리

2-3 트리와 2-3-4 트리는 한 노드에 여러 키와 여러 자식을 두면서 모든 잎을 같은 레벨에 유지하는 균형 탐색 트리이다. 이 글에서는 각 노드의 탐색 범위, 삽입 시 분리, 삭제 시 회전과 결합, 그리고 2-3-4 트리를 이진 트리로 나타내는 레드-블랙 트리의 원리를 학습한다.

제1장 2-3 트리의 구조

1. 멀티웨이 탐색 트리와 2-3 트리

2-3 트리는 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리이다. 2-노드와 3-노드만으로 구성되는 특수한 형태의 B 트리이며, 모든 잎 노드가 같은 레벨에 있어 항상 균형을 유지한다.

이진 탐색 트리는 한 노드에 하나의 키를 두고 두 방향으로 분기하지만, 2-3 트리는 한 노드에 하나 또는 두 개의 키를 저장하고 두 개 또는 세 개의 서브트리로 분기한다. 따라서 한 번의 노드 방문에서 여러 키와 비교하여 탐색 방향을 결정할 수 있다.

2. 2-노드와 3-노드

노드 종류	키 개수	자식 수	키 이름
2-노드	1개	2개	lkey
3-노드	2개	3개	lkey, rkey

2-노드의 왼쪽 자식 lchild에는 lkey보다 작은 키들이 있고, 가운데 자식 mchild에는 lkey보다 큰 키들이 있다. 3-노드에서는 lkey < rkey이며 왼쪽 서브트리는 lkey보다 작고, 가운데 서브트리는 두 키 사이, 오른쪽 서브트리는 rkey보다 큰 키를 저장한다.

2-3 트리의 필수 조건: 내부 노드는 2-노드 또는 3-노드이고, 키가 서브트리의 값 범위를 나누며, 모든 잎 노드는 같은 레벨에 있다.

3. 노드 표현

강의록의 구조체는 두 키 lkey, rkey와 세 자식 포인터 lchild, mchild, rchild를 둔다. 2-노드는 한 키와 두 자식만 사용하고, 3-노드는 두 키와 세 자식을 모두 사용한다.

제2장 2-3 트리의 탐색과 삽입

1. 탐색 방향 결정

탐색은 현재 노드의 키와 목표키 x를 비교하여 진행한다. x가 lkey보다 작으면 왼쪽 자식으로, x가 두 키 사이이면 가운데 자식으로, x가 rkey보다 크면 오른쪽 자식으로 이동한다. x가 현재 노드의 어느 키와 같으면 그 노드를 반환한다.

비교 결과	다음 탐색 위치
x < lkey	lchild
lkey < x < rkey	mchild
x > rkey	rchild
x = lkey 또는 x = rkey	현재 노드에서 탐색 성공

2. 여유가 있는 잎에 삽입

삽입은 먼저 같은 키가 이미 존재하는지 검사하고, 없다면 키가 들어갈 잎 노드를 찾는다. 잎이 2-노드라면 새 키를 정렬된 위치에 넣어 3-노드로 바꿀 수 있다. 예를 들어 키 8만 가진 잎에 7을 넣으면 키가 7, 8인 3-노드가 된다.

3. 가득 찬 잎의 분리

이미 두 키를 가진 3-노드에 새 키를 넣으면 임시로 세 키가 된다. 2-3 트리는 4-노드를 허용하지 않으므로 가운데 키를 부모로 올리고, 작은 키와 큰 키를 각각 별도의 2-노드로 분리해야 한다.

강의록의 예에서 1, 2를 가진 잎에 3을 삽입하면 가운데 키 2가 부모로 올라간다. 원래 부모가 키 4를 갖고 있었다면 부모는 키 2, 4를 가진 3-노드가 되고, 분리된 잎은 1과 3을 각각 저장한다.

부모도 이미 3-노드라면 새 키를 받을 수 없어 분리가 위쪽으로 전파될 수 있다. 루트까지 분리가 전파되면 새 루트가 만들어지고 트리의 높이가 1 증가한다.

삽입 원칙: 잎에 키를 정렬 삽입하고, 세 키가 생기면 가운데 키를 부모로 올려 좌우 두 노드로 분리한다.

제3장 2-3 트리의 삭제

1. 내부 키를 삭제하는 경우

잎이 아닌 내부 노드의 키를 바로 없애면 서브트리 범위를 나누는 기준이 사라진다. 따라서 삭제할 키를 왼쪽 서브트리의 가장 큰 키 또는 오른쪽 서브트리의 가장 작은 키로 대체한 뒤, 실제 삭제는 잎에서 수행한다.

2. 잎에 키가 남는 경우

두 키를 가진 3-노드 잎에서 한 키를 삭제하면 하나의 키가 남아 정상적인 2-노드가 된다. 예를 들어 잎 9, 10에서 9를 삭제하면 10만 남으며 트리 구조를 추가로 바꿀 필요가 없다.

3. 회전으로 빈 노드 채우기

하나의 키만 가진 2-노드 잎에서 그 키를 삭제하면 빈 노드가 생긴다. 인접 형제가 3-노드라 여분 키를 가지고 있다면 회전(rotation)을 사용한다. 형제의 경계 키 하나를 부모로 올리고, 부모의 분리 키 하나를 빈 노드로 내려 보내어 모든 노드가 최소 한 키를 갖게 한다.

강의록의 예에서 가운데 잎의 7을 삭제해 빈 노드가 생겼을 때 왼쪽 형제 1, 2의 큰 키 2를 부모로 올리고, 부모의 키 5를 빈 노드로 내린다. 그 결과 부모 키와 자식의 값 범위가 다시 올바르게 정리된다.

4. 결합으로 빈 노드 제거하기

인접 형제도 2-노드라 빌려줄 여분 키가 없다면 결합(merge)을 수행한다. 빈 노드, 부모의 분리 키, 인접 형제의 키를 하나의 노드로 합치고 부모에서는 내려 보낸 키를 제거한다. 부모가 비게 되면 같은 문제가 상위 레벨로 전파될 수 있다.

삭제 후 상태	처리
3-노드 잎에 키 하나가 남음	단순 삭제로 종료
빈 노드가 생기고 형제에 여분 키가 있음	회전으로 형제 키를 부모에 올리고 부모 키를 내려 보냄
빈 노드가 생기고 형제에 여분 키가 없음	부모 키와 형제 노드를 결합

삭제 판단 순서: 잎에서 단순 삭제가 가능한지 확인하고, 빈 노드가 생기면 먼저 형제에게 빌릴 수 있는지 살핀 뒤 불가능하면 결합한다.

제4장 2-3-4 트리의 구조

1. 2-3-4 트리의 정의

2-3-4 트리는 2-3 트리를 확장하여 네 개의 자식을 가진 4-노드를 허용하는 탐색 트리이다. 내부 노드는 2-노드, 3-노드 또는 4-노드이며, 모든 잎 노드는 같은 레벨에 있다.

4-노드는 정렬된 세 키 lkey < mkey < rkey와 네 자식 lchild, mchild, rchild, 그리고 최우측 자식을 갖는다. 각 키가 경계가 되어 네 서브트리의 값 범위를 나눈다.

노드 종류	키 개수	자식 수
2-노드	1개	2개
3-노드	2개	3개
4-노드	3개	4개

2. 4-노드의 서브트리 범위

• 첫 번째 서브트리의 모든 키는 lkey보다 작다.
• 두 번째 서브트리는 lkey보다 크고 mkey보다 작다.
• 세 번째 서브트리는 mkey보다 크고 rkey보다 작다.
• 네 번째 서브트리의 모든 키는 rkey보다 크다.

2-3-4 트리도 다원 탐색 트리이므로 한 노드 안의 키를 비교해 적절한 서브트리 하나를 선택한다. 모든 잎의 깊이가 같기 때문에 편향되지 않은 탐색 경로를 유지한다.

3. 2-3 트리와의 관계

2-3-4 트리는 4-노드를 허용하므로 2-3 트리보다 삽입과 삭제 과정에서 즉시 재구성해야 할 확률이 낮다. 강의록은 이러한 여유 덕분에 삽입 및 삭제 연산을 더 효율적으로 수행할 수 있다고 설명한다.

제5장 2-3-4 트리의 노드 분리

1. 4-노드 분리의 원리

4-노드의 세 키를 a < b < c라고 하면 가운데 키 b를 부모로 올리고, a와 c를 각각 2-노드로 분리한다. 삽입 대상 4-노드가 어디에 있는지에 따라 부모가 새 키를 받아들이는 방법이 달라진다.

2. 삽입을 위한 세 가지 분리 경우

1. 4-노드가 루트인 경우: 가운데 키가 새로운 루트가 되고 작은 키와 큰 키가 두 자식이 된다.
2. 4-노드의 부모가 2-노드인 경우: 가운데 키를 부모에 올리면 부모는 3-노드가 되고, 분리된 두 노드가 올바른 자식 위치에 연결된다.
3. 4-노드의 부모가 3-노드인 경우: 가운데 키를 부모에 올리면 부모는 4-노드가 되며, 분리된 자식들의 순서를 다시 연결한다.

분리된 노드와 부모의 키는 항상 정렬 순서를 유지해야 한다. 단순히 가운데 키를 위로 올리는 것뿐 아니라, 원래 4-노드의 네 서브트리를 새로 생긴 두 노드에 값 범위에 맞게 배분해야 한다.

3. 삭제를 위한 분리

2-3-4 트리에서 잎 노드의 키는 조건을 해치지 않는다면 단순히 삭제할 수 있다. 강의록은 삭제 과정에서 4-노드를 2-3 트리의 구조로 분리하는 세 경우도 제시한다. 루트 4-노드, 부모가 2-노드인 4-노드, 부모가 3-노드인 4-노드를 각각 가운데 키 승격 방식으로 분리한 뒤 삭제를 수행한다.

4-노드 분리: 가운데 키는 부모로 승격하고 양쪽 키는 두 개의 2-노드가 된다. 부모의 종류에 따라 부모가 3-노드 또는 4-노드로 확장될 수 있다.

제6장 레드-블랙 트리

1. 레드-블랙 트리의 정의

레드-블랙 트리는 2-3-4 트리를 이진 트리로 나타낸 탐색 트리이다. 2-3-4 트리의 다중 키 노드를 이진 노드들의 관계로 풀어 표현하므로, 이진 탐색 트리의 형태와 탐색 알고리즘을 사용하면서도 균형 구조를 나타낼 수 있다.

레드-블랙 트리의 탐색은 보통의 이진 탐색 트리와 동일하게 목표키가 현재 키보다 작으면 왼쪽, 크면 오른쪽으로 이동한다.

2. 레드 간선과 블랙 간선

강의록에서는 레드 간선을 점선, 블랙 간선을 실선으로 나타낸다. 레드 간선은 원래 2-3-4 트리에서 하나의 같은 노드 안에 있던 키들의 관계를 표현하고, 블랙 간선은 2-3-4 트리에서 부모 노드와 자식 노드 사이의 관계를 표현한다.

2-3-4 트리 노드	레드-블랙 트리 표현
2-노드	하나의 이진 노드
3-노드	두 이진 노드를 하나의 레드 간선으로 연결
4-노드	가운데 키를 중심으로 양쪽 키를 레드 간선으로 연결
서로 다른 노드의 부모·자식 관계	블랙 간선으로 연결

3. 3-노드와 4-노드의 변환

키 1, 2를 가진 3-노드는 큰 키 2가 부모이고 작은 키 1이 레드 왼쪽 자식인 모습이나, 작은 키 1이 부모이고 큰 키 2가 레드 오른쪽 자식인 모습으로 나타낼 수 있다. 세 키 1, 2, 3을 가진 4-노드는 가운데 키 2를 부모로 두고 1과 3을 각각 레드 간선으로 연결한다.

4. 삽입 과정의 노드 분리

레드-블랙 트리에서 4-노드에 대응하는 구조를 분리할 때는 같은 노드 내부 관계를 나타내던 레드 간선을 블랙 간선으로 바꾸는 색상 변환을 사용한다. 이 변환은 2-3-4 트리에서 가운데 키가 부모 쪽으로 승격되고 양쪽 키가 분리되는 효과를 이진 트리의 간선 색으로 표현한 것이다.

레드-블랙 트리를 볼 때 레드 간선으로 묶인 이진 노드들을 하나의 다중 키 노드로 합쳐 생각하면 원래 2-3-4 트리의 구조를 이해하기 쉽다.

핵심 개념 정리

멀티웨이 탐색 트리 II 핵심 요약

• 2-3 트리는 2-노드와 3-노드로 구성되며 모든 잎이 같은 레벨에 있다.
• 2-노드는 키 1개와 자식 2개, 3-노드는 키 2개와 자식 3개를 갖는다.
• 탐색은 노드의 키들이 나누는 값 범위에 따라 왼쪽·가운데·오른쪽 서브트리로 진행한다.
• 2-3 트리 삽입에서 세 키가 생기면 가운데 키를 부모로 올리고 두 노드로 분리한다.
• 삭제로 빈 노드가 생기면 여분 키가 있는 형제에게서 회전으로 빌리고, 불가능하면 결합한다.
• 2-3-4 트리는 4-노드를 허용하며 4-노드는 키 3개와 자식 4개를 갖는다.
• 4-노드 분리는 가운데 키를 부모로 올리고 양쪽 키를 각각 2-노드로 만든다.
• 레드-블랙 트리는 2-3-4 트리를 이진 트리로 표현해 기억 장소를 효율적으로 사용할 수 있게 한다.
• 레드 간선은 같은 2-3-4 노드 내부 관계, 블랙 간선은 서로 다른 노드의 부모·자식 관계를 나타낸다.

이 단원의 중심은 한 노드의 키들이 서브트리의 값 범위를 나눈다는 탐색 원리와 모든 잎의 레벨을 같게 유지한다는 균형 조건이다. 삽입에서는 가운데 키를 승격해 분리하고, 삭제에서는 회전 또는 결합으로 최소 키 수를 회복하며, 레드-블랙 트리는 이 다중 키 관계를 간선 색으로 바꾸어 표현한다.

예상문제 20선

1. 2-3 트리의 내부 노드로 허용되는 것은?

① 1-노드와 4-노드 ② 2-노드와 3-노드 ③ 3-노드와 5-노드 ④ 4-노드만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
2-3 트리는 자식이 2개인 2-노드와 자식이 3개인 3-노드로 구성되는 균형 탐색 트리이다.

2. 2-3 트리의 균형 조건으로 옳은 것은?

① 왼쪽 서브트리만 잎을 가질 수 있다. ② 루트의 자식 수가 항상 3이어야 한다. ③ 모든 내부 노드가 같은 키를 가져야 한다. ④ 모든 잎 노드가 같은 레벨에 있다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
2-3 트리는 모든 잎의 깊이가 같도록 삽입과 삭제 때 노드를 분리·회전·결합한다.

3. 3-노드가 갖는 키와 자식의 수는?

① 키 2개, 자식 3개 ② 키 1개, 자식 3개 ③ 키 3개, 자식 2개 ④ 키 3개, 자식 4개

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
3-노드는 두 키가 세 개의 값 범위를 만들기 때문에 왼쪽·가운데·오른쪽의 세 자식을 갖는다.

4. 키가 lkey < rkey인 3-노드에서 lkey < x < rkey라면 탐색할 곳은?

① 왼쪽 자식 ② 오른쪽 자식 ③ 가운데 자식 ④ 부모 노드

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
가운데 서브트리는 두 키 사이의 값들을 저장하므로 해당 범위의 목표키는 mchild로 탐색한다.

5. 2-3 트리의 2-노드 잎에 새 키를 삽입했을 때의 일반적인 결과는?

① 키를 저장하지 않고 삭제한다. ② 무조건 새 루트를 만든다. ③ 두 개의 2-노드로 즉시 분리한다. ④ 두 키를 정렬해 3-노드로 만든다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
2-노드는 키를 하나 더 받을 여유가 있으므로 새 키를 정렬된 위치에 넣어 3-노드가 된다.

6. 3-노드에 새 키를 삽입해 세 키가 되었을 때 올바른 처리는?

① 가장 작은 키를 삭제한다. ② 가운데 키를 부모로 올리고 양쪽 키를 별도 노드로 분리한다. ③ 세 키를 그대로 3-노드에 둔다. ④ 모든 키를 루트로 이동한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
2-3 트리는 세 키를 가진 노드를 허용하지 않으므로 중앙값을 승격하고 작은 키와 큰 키를 나눈다.

7. 2-3 트리에서 내부 노드의 키를 삭제할 때 사용하는 대체키는?

① 왼쪽 서브트리의 최댓값 또는 오른쪽 서브트리의 최솟값 ② 트리 전체의 임의 키 ③ 반드시 루트의 키 ④ 삭제할 키와 같은 값만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
인접 순서의 선행자나 후계자로 내부 키를 바꾸면 탐색 순서를 유지하면서 실제 삭제를 잎으로 옮길 수 있다.

8. 삭제 후 빈 노드가 생겼고 인접 형제가 여분 키를 가진 3-노드라면?

① 트리 전체를 삭제한다. ② 빈 노드를 그대로 둔다. ③ 회전으로 형제의 키를 부모에 올리고 부모 키를 빈 노드로 내린다. ④ 무조건 새 루트를 만든다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
형제에게 빌릴 키가 있으면 부모의 경계 키를 매개로 회전하여 각 노드의 최소 키 수를 회복한다.

9. 삭제 후 빈 노드가 생겼지만 형제도 2-노드라 키를 빌릴 수 없다면?

① 빈 노드에 임의의 값을 만든다. ② 부모의 분리 키와 인접 형제를 결합한다. ③ 모든 잎을 다른 레벨로 이동한다. ④ 형제 노드의 키를 복사만 하고 유지한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
빌릴 여분 키가 없으면 부모 키를 내려 인접 노드와 합쳐 정상 노드를 만들며, 변화가 위로 전파될 수 있다.

10. 2-3-4 트리가 2-3 트리와 다른 점은?

① 키 3개와 자식 4개를 갖는 4-노드를 허용한다. ② 잎 노드가 서로 다른 레벨에 있어야 한다. ③ 한 노드에는 키를 저장하지 않는다. ④ 탐색 순서 조건을 사용하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
2-3-4 트리는 2-노드와 3-노드에 더해 세 키를 가진 4-노드를 허용한다.

11. 키가 lkey < mkey < rkey인 4-노드에서 mkey < x < rkey인 키를 탐색할 서브트리는?

① 첫 번째 서브트리 ② 두 번째 서브트리 ③ 네 번째 서브트리 ④ 세 번째 서브트리

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
세 번째 서브트리는 가운데 키보다 크고 오른쪽 키보다 작은 값의 범위를 담당한다.

12. 키가 1, 2, 3인 루트 4-노드를 분리한 결과는?

① 키 1이 루트이고 2, 3이 한 자식에 남는다. ② 키 3이 루트이고 1, 2가 삭제된다. ③ 키 2가 새 루트가 되고 키 1과 3이 각각 자식 노드가 된다. ④ 세 키를 모두 별도의 루트로 만든다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
4-노드 분리는 중앙값을 승격하고 작은 값과 큰 값을 두 자식으로 나누는 방식이다.

13. 4-노드의 부모가 2-노드일 때 가운데 키를 승격하면 부모는?

① 키가 2개인 3-노드가 된다. ② 키가 없는 노드가 된다. ③ 즉시 삭제된다. ④ 자식이 하나인 1-노드가 된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
키 하나를 가진 2-노드 부모가 승격된 키 하나를 더 받으면 키 두 개의 3-노드가 된다.

14. 2-3-4 트리의 장점에 대한 강의록의 설명으로 옳은 것은?

① 탐색 시 키 비교가 전혀 필요 없다. ② 모든 노드를 항상 4-노드로 유지한다. ③ 잎의 레벨을 자유롭게 다르게 둘 수 있다. ④ 4-노드를 허용해 2-3 트리보다 삽입·삭제 때 재구성할 확률이 낮다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
노드가 키를 하나 더 수용할 수 있어 구조 변경이 즉시 필요하지 않은 경우가 늘어난다.

15. 레드-블랙 트리와 2-3-4 트리의 관계로 옳은 것은?

① 레드-블랙 트리는 힙을 연결 리스트로 표현한 것이다. ② 레드-블랙 트리는 2-3-4 트리를 이진 트리로 표현한 것이다. ③ 두 트리는 키의 순서를 사용하지 않는다. ④ 2-3-4 트리는 레드-블랙 트리의 색을 저장하는 배열이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
다중 키 노드를 레드 간선으로 연결된 이진 노드들로 풀어 표현한 것이 레드-블랙 트리이다.

16. 강의록의 레드-블랙 트리에서 레드 간선이 나타내는 것은?

① 서로 다른 트리의 루트 관계 ② 삭제 예정 노드의 표시 ③ 원래 2-3-4 트리의 같은 노드 안에 있던 키들의 관계 ④ 모든 잎이 같은 레벨이라는 표시만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
레드 간선으로 연결된 이진 노드들은 2-3-4 트리에서 하나의 다중 키 노드였다고 해석한다.

17. 레드-블랙 트리의 블랙 간선이 나타내는 관계는?

① 같은 4-노드 안의 세 키 관계 ② 정렬되지 않은 형제 관계 ③ 검색에 실패한 경로 ④ 2-3-4 트리의 서로 다른 부모 노드와 자식 노드 관계

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
블랙 간선은 하나의 다중 키 노드 내부가 아니라 서로 다른 노드 사이의 계층 관계를 나타낸다.

18. 키 1, 2, 3을 가진 4-노드의 레드-블랙 트리 표현으로 적절한 것은?

① 키 1을 루트로 두고 2와 3을 모두 블랙 왼쪽 자식으로 둔다. ② 가운데 키 2를 중심으로 키 1과 3을 레드 간선으로 연결한다. ③ 세 키를 하나의 이진 노드 데이터칸에 그대로 둔다. ④ 키 3을 삭제하고 1과 2만 블랙 간선으로 연결한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
4-노드의 세 키는 중앙값을 부모로, 양쪽 값을 레드 자식으로 두어 같은 다중 키 노드임을 표현한다.

19. 레드-블랙 트리에서 4-노드에 대응하는 구조를 분리할 때 강의록이 제시한 변화는?

① 모든 블랙 간선을 삭제한다. ② 레드 간선을 그대로 두고 키를 제거한다. ③ 같은 노드 관계의 레드 간선을 블랙 간선으로 바꾼다. ④ 모든 키를 하나의 새 레드 노드에 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
레드 간선을 블랙으로 바꾸는 색상 변환은 하나의 4-노드가 여러 2-3-4 노드 관계로 분리되는 효과를 나타낸다.

20. 2-3 트리, 2-3-4 트리, 레드-블랙 트리에 대한 설명으로 옳지 않은 것은?

① 세 트리는 모두 잎의 레벨을 달리하여 편향될수록 바람직하다. ② 2-3 트리와 2-3-4 트리는 모든 잎을 같은 레벨에 둔다. ③ 2-3-4 트리는 4-노드를 허용한다. ④ 레드-블랙 트리는 다중 키 관계를 이진 트리로 표현한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
2-3 계열 트리는 모든 잎의 레벨을 같게 유지하는 균형 탐색 트리이며 레드-블랙 트리는 그 균형 구조를 이진 표현으로 나타낸다.