방송대 자료구조 13강 : 2-3-4 트리와 레드 블랙 트리

방송대 자료구조 13강: 2-3-4 트리와 레드 블랙 트리

한 노드가 키를 하나만 담는다면 삽입 위치는 단순하지만 트리가 쉽게 길어집니다. 반대로 여러 키를 담게 하면 높이는 낮아지지만, 노드가 가득 차거나 비었을 때 키를 올리고 내리고 합치는 복구가 필요합니다. 이 글은 2-3 트리의 탐색·삽입·삭제를 직접 추적한 뒤, 2-3-4 트리의 선제 분리와 레드 블랙 트리의 간선 표현까지 같은 상태 변화로 읽도록 돕습니다.

문제는 키 자체보다 노드 용량의 경계에서 생긴다

멀티웨이 탐색 트리에서 키는 정렬된 경계이고 자식 포인터는 그 사이 구간을 담당합니다. 탐색할 때는 키와 비교해 한 구간만 선택하면 되지만, 삽입으로 노드 용량을 넘거나 삭제로 최소 키 수보다 적어지면 탐색 규칙과 모든 잎의 레벨을 함께 보존하도록 구조를 고쳐야 합니다.

2-3 트리는 내부 노드를 2-노드 또는 3-노드로 제한합니다. 2-3-4 트리는 여기에 키 세 개와 자식 네 개를 가진 4-노드를 허용합니다. 레드 블랙 트리는 이 2-3-4 트리의 한 노드에 함께 있던 키를 이진 노드로 풀어 표현합니다.

상태 변화의 공통 질문: 지금 노드는 정상 용량인가, 가득 찼는가, 삭제 뒤 비었는가를 먼저 판정합니다. 그다음 키의 정렬 순서와 자식 구간, 잎 레벨이 모두 유지되는지 검산합니다.

키 수가 자식 구간의 수를 결정한다

2-노드는 키 하나와 자식 두 개를, 3-노드는 정렬된 키 두 개와 자식 세 개를 가집니다. 2-3-4 트리의 4-노드는 정렬된 키 세 개와 자식 네 개를 가집니다. 이 명칭의 숫자는 키 수가 아니라 자식 수, 즉 차수를 가리킵니다.

노드 종류	키 수	자식 수	자식이 담당하는 구간
2-노드	1	2	키보다 작은 구간 / 큰 구간
3-노드	2	3	왼쪽 키 미만 / 두 키 사이 / 오른쪽 키 초과
4-노드	3	4	세 키가 만드는 네 개의 연속 구간

예를 들어 3-노드의 키가 18과 41이라면 왼쪽 자식에는 18보다 작은 키, 가운데 자식에는 18보다 크고 41보다 작은 키, 오른쪽 자식에는 41보다 큰 키가 들어갑니다. 4-노드의 키가 12, 27, 46이라면 자식 구간은 12 미만, 12~27 사이, 27~46 사이, 46 초과로 구분됩니다.

두 트리 모두 모든 잎 노드가 같은 레벨에 있어야 합니다. 따라서 2-노드와 3-노드라는 제한은 내부 노드에 적용되지만, 트리 전체의 균형을 보장하는 조건은 잎의 동일 레벨입니다.

오개념 교정: 3-노드를 키 세 개짜리 노드로 해석하면 자식 구간이 하나씩 밀립니다. 3-노드는 자식이 셋이고 키는 둘이며, 4-노드는 자식이 넷이고 키는 셋입니다.

탐색은 현재 노드 안의 구간을 하나만 고른다

2-3 트리의 탐색은 먼저 현재 노드의 키와 같은지 확인합니다. 같으면 성공이고, 아니라면 왼쪽 키보다 작은지, 두 키 사이인지, 오른쪽 키보다 큰지를 판정해 자식 하나로 내려갑니다. 2-노드에서는 오른쪽 키 칸을 사용하지 않으므로 왼쪽 키보다 큰 모든 값이 가운데 포인터 쪽으로 갑니다.

다음 C 코드는 강의자료의 lkey, rkey, lchild, mchild, rchild 구조와 탐색 흐름을 학습용으로 정리한 것입니다. 사용하지 않는 rkey에는 INT_MAX가 들어 있다는 전제입니다.

#include <limits.h>
#include <stddef.h>

typedef struct two_three *two_three_ptr;

typedef struct two_three {
    int lkey;
    int rkey;
    two_three_ptr lchild;
    two_three_ptr mchild;
    two_three_ptr rchild;
} two_three;

two_three_ptr search23(two_three_ptr t, int x) {
    while (t != NULL) {
        if (x == t->lkey ||
            (t->rkey != INT_MAX && x == t->rkey)) {
            return t;
        }

        if (x < t->lkey) {
            t = t->lchild;
        } else if (t->rkey == INT_MAX || x < t->rkey) {
            t = t->mchild;
        } else {
            t = t->rchild;
        }
    }
    return NULL;
}

키 35를 [18, 41] 노드에서 찾으면 18<35<41이므로 가운데 자식으로 갑니다. 키 52라면 오른쪽 자식으로 갑니다. 한 노드에서 두 키를 확인해도 다음 단계에서는 자식 하나만 선택하므로, 같은 레벨의 다른 서브트리를 함께 뒤지지 않습니다.

2-3 트리 삽입은 잎에서 넘친 가운데 키를 올린다

삽입은 탐색 경로를 따라 잎까지 내려간 뒤 새 키를 정렬된 위치에 넣습니다. 2-노드에 삽입하면 키 두 개의 3-노드가 되어 바로 끝납니다. 이미 키 두 개가 있는 3-노드에 삽입하면 임시로 키가 세 개가 되므로 가운데 키를 부모로 올리고 양쪽 키를 서로 다른 노드로 분리합니다.

직접 구성한 예로 루트 [20], 왼쪽 잎 [8, 14], 오른쪽 잎 [32]인 2-3 트리를 가정하겠습니다.

삽입	도착한 잎의 상태	복구	결과
26	[32]는 2-노드	키를 정렬해 [26, 32]로 확장	부모 변화 없음
11	[8, 14]는 이미 3-노드	[8, 11, 14]에서 11을 부모로 올리고 [8], [14]로 분리	루트 [11, 20], 잎 [8]·[14]·[26, 32]

첫 삽입은 여유 칸을 채우는 동작이고, 둘째 삽입은 넘침을 부모 방향으로 전달하는 동작입니다. 부모도 가득 차 있다면 같은 분리가 위로 연쇄됩니다. 루트가 분리되면 새 루트가 생겨 트리 높이가 한 레벨 증가합니다.

삽입 검산: 분리 전 세 키를 작은 값·가운데 값·큰 값으로 정렬하고, 가운데 값만 위로 보냅니다. 작은 값과 큰 값은 같은 노드에 남지 않으며, 분리 뒤에도 모든 잎의 레벨이 같아야 합니다.

2-3 트리 삭제는 빌릴 수 있으면 회전하고 아니면 결합한다

잎이 아닌 내부 키를 삭제할 때는 왼쪽 서브트리의 최댓값이나 오른쪽 서브트리의 최솟값으로 먼저 대체한 뒤 잎에서 삭제합니다. 실제 복구 문제는 잎의 마지막 키가 사라져 빈 노드가 될 때 발생합니다.

강의자료의 루트 [5, 8], 잎 [1, 2]·[7]·[9, 10] 예를 순서대로 추적하면 회전과 결합의 차이가 분명해집니다.

9 삭제: [9, 10]은 키가 두 개이므로 9만 지우고 [10]으로 남습니다. 부족이 없어 재구성이 필요 없습니다.
7 삭제: 가운데 잎 [7]이 비지만 왼쪽 형제 [1, 2]에는 여분 키가 있습니다. 형제의 2를 부모로 올리고 부모의 5를 빈 가운데 노드로 내립니다. 결과는 루트 [2, 8], 잎 [1]·[5]·[10]입니다.
10 삭제: 오른쪽 잎이 비고 이웃 [5]에도 빌려줄 여분이 없습니다. 부모의 경계 키 8을 내려 [5]와 합치면 루트 [2], 잎 [1]·[5, 8]이 됩니다.

삭제 뒤 상태	선택할 복구	키 이동	높이 영향
노드에 키가 하나 이상 남음	단순 삭제	추가 이동 없음	없음
빈 노드, 형제가 3-노드	회전 또는 재분배	형제 키는 부모로, 부모 경계 키는 빈 노드로	없음
빈 노드, 인접 형제도 2-노드	결합	부모 경계 키를 내려 형제와 한 노드로 합침	루트까지 비면 감소 가능

회전은 형제의 키를 빈 노드로 곧바로 옮기는 동작이 아닙니다. 부모의 경계 키를 사이에 두고 두 키가 한 단계씩 이동해야 각 서브트리의 값 범위가 보존됩니다.

2-3-4 트리는 가득 찬 노드를 내려가기 전에 분리한다

2-3-4 트리는 4-노드를 허용하므로 2-3 트리보다 삽입·삭제 과정에서 즉시 재구성해야 하는 경우가 줄어듭니다. 그러나 4-노드는 키 세 개로 이미 가득 찼기 때문에 새 키를 받을 수 없습니다. 삽입 경로에서 4-노드를 만나면 가운데 키를 부모로 올리고 양쪽 키를 2-노드로 분리한 뒤 계속 내려갑니다.

4-노드 [20, 35, 50]의 분리는 항상 같은 핵심을 가집니다. 35가 부모로 올라가고 [20]과 [50]이 양쪽 자식으로 분리됩니다. 달라지는 것은 분리 대상의 위치와 부모의 남은 수용 공간입니다.

분리 대상의 위치	가운데 키의 목적지	구조 변화
4-노드가 루트	새 루트	높이가 한 레벨 증가
부모가 2-노드	부모의 둘째 키	부모가 3-노드가 되고 자식이 하나 증가
부모가 3-노드	부모의 셋째 키	부모가 4-노드가 되고 자식이 하나 증가

학습용 예로 부모 [70]의 왼쪽 자식이 [20, 35, 50]이라면 35를 올려 부모를 [35, 70]으로 만들고, 분리된 [20]과 [50]을 첫째·둘째 자식으로 둡니다. 이후 삽입 키가 28이라면 [20] 쪽, 44라면 [50] 쪽으로 내려갑니다.

왜 선제 분리하는가: 가득 찬 노드에 도착한 뒤 넘침을 아래에서 위로 연쇄 처리하는 대신, 내려가는 길에 공간을 확보하면 삽입 대상 잎은 가득 차 있지 않은 상태가 됩니다.

삭제 도식에서도 가운데 키 승격 규칙은 변하지 않는다

강의자료는 2-3-4 트리의 삭제에서 잎 노드의 키는 단순히 제거할 수 있다고 설명한 뒤, 삭제를 위한 4-노드 분리도 루트·2-노드 부모·3-노드 부모의 세 경우로 제시합니다. 도식에서 확인할 핵심은 삽입 때와 마찬가지로 4-노드의 가운데 키가 위로 올라가고 양 끝 키가 분리된다는 점입니다.

예를 들어 부모 [5]의 왼쪽 4-노드 [1, 2, 3]을 분리하면 2가 올라가 부모는 [2, 5]가 되고 자식은 [1]과 [3]으로 갈립니다. 부모 [9, 27] 아래의 같은 4-노드를 분리하면 부모는 [2, 9, 27]이 됩니다. 분리만 보고 삭제가 끝났다고 판단하지 말고, 실제 삭제할 키의 위치와 분리 뒤 내려갈 구간을 다시 확인해야 합니다.

경계 구분: ‘잎에서 키 하나를 지울 수 있다’는 말은 삭제 뒤에도 노드가 허용 범위에 남는 경우입니다. 최소 용량을 어기는 경우에는 주변 노드와 부모 경계 키를 포함한 재구성이 필요합니다.

레드 간선은 한 멀티웨이 노드 안의 결합을 표시한다

레드 블랙 트리는 2-3-4 트리를 이진 트리 형태로 나타낸 탐색 트리입니다. 강의자료에서는 레드 간선을 2-3-4 트리의 한 노드 안에 함께 있던 키의 관계로, 블랙 간선을 서로 다른 멀티웨이 노드 사이의 부모·자식 관계로 해석합니다. 탐색 자체는 일반 이진 탐색 트리와 같은 대소 비교를 사용합니다.

2-3-4 트리 노드	레드 블랙 표현	읽는 방법
2-노드 [18]	블랙 노드 18 하나	한 키가 독립된 멀티웨이 노드
3-노드 [12, 18]	블랙 노드와 레드 자식 하나	두 이진 노드가 원래 한 노드였음
4-노드 [12, 18, 27]	블랙 18과 레드 자식 12·27	세 키를 가운데 키 중심으로 묶음

3-노드는 큰 키 18을 블랙 부모로 두고 작은 키 12를 레드 왼쪽 자식으로 표현할 수도 있고, 작은 키 12를 블랙 부모로 두고 큰 키 18을 레드 오른쪽 자식으로 표현할 수도 있습니다. 두 모양 모두 레드 간선으로 연결된 두 키를 하나의 3-노드로 접어 읽습니다.

4-노드 [12, 18, 27]은 가운데 키 18을 블랙 노드로 두고 12와 27을 레드 자식으로 연결합니다. 레드 간선을 끊어 각각을 독립된 멀티웨이 노드로 읽으면 안 됩니다.

4-노드 분리는 레드 간선을 블랙 간선으로 바꾸어 읽는다

4-노드가 루트인 2-3-4 트리에서 가운데 키를 새 루트로 올리고 양 끝 키를 두 자식으로 나누는 동작은 레드 블랙 표현에서 색 변환으로 나타납니다. 가운데 블랙 노드와 양쪽 레드 자식을 묶던 레드 간선을 블랙 간선으로 바꾸면 세 키가 서로 다른 멀티웨이 노드가 됩니다.

이 대응을 기억하면 레드 블랙 트리의 색을 장식으로 보지 않게 됩니다. 색은 이진 링크가 원래 같은 2-3-4 노드 안의 결합인지, 서로 다른 노드 사이의 계층 연결인지 표시합니다. 강의자료의 전체 변환 예에서도 3-노드와 4-노드가 있던 자리만 레드 간선이 나타나고, 멀티웨이 노드 사이의 연결은 블랙 간선으로 유지됩니다.

잘못된 접근: 레드 노드를 ‘값이 작은 노드’, 블랙 노드를 ‘값이 큰 노드’로 해석하면 탐색 순서와 색 의미를 혼동합니다. 값의 대소는 이진 탐색 트리의 왼쪽·오른쪽 위치가 정하고, 색은 2-3-4 노드의 묶음 관계를 표시합니다.

새 연산은 구간 선택과 용량 복구를 분리해 추적한다

2-3, 2-3-4, 레드 블랙 트리 문제는 다음 순서로 풀면 키 이동과 포인터 이동을 뒤섞지 않을 수 있습니다.

구간을 고릅니다. 현재 노드의 키를 오름차순으로 읽고 목표 키가 들어갈 자식 하나를 정합니다.
노드 상태를 표시합니다. 2-노드·3-노드·4-노드 중 무엇인지, 삽입 공간이나 삭제 후 남을 키가 있는지 적습니다.
복구 규칙을 선택합니다. 삽입 넘침이면 가운데 키를 승격하고, 삭제 부족이면 형제에게 빌릴 수 있는지 본 뒤 회전 또는 결합을 선택합니다.
포인터 구간을 다시 붙입니다. 키만 옮기지 말고 각 키 사이 범위에 맞게 자식 서브트리도 이동합니다.
불변식을 검산합니다. 노드 안의 키 순서, 서브트리 범위, 허용 키 수, 모든 잎의 동일 레벨을 확인합니다.
레드 블랙 표현이면 접어 봅니다. 레드 간선으로 연결된 노드를 한 3-노드 또는 4-노드로 접었을 때 유효한 2-3-4 트리가 되는지 확인합니다.

상태별 복구 지도

2-3 트리 삽입에서 가득 찬 3-노드는 가운데 키를 부모로 올리고 두 2-노드로 분리합니다.
2-3 트리 삭제에서 빈 노드가 생기면 여유 있는 형제와는 회전하고, 모두 최소 용량이면 부모 키를 내려 결합합니다.
2-3-4 트리는 삽입 경로의 4-노드를 미리 분리해 내려갈 노드에 공간을 확보합니다.
레드 간선은 한 2-3-4 노드 안의 키 결합, 블랙 간선은 서로 다른 노드 사이의 계층 관계를 뜻합니다.

마지막 점검: 연산 결과만 외우지 말고 ‘현재 키가 어느 구간으로 가는가 → 도착 노드가 용량 경계에 있는가 → 어느 키를 부모와 주고받는가 → 잎 레벨이 유지되는가’의 네 질문을 차례로 답해 보세요. 레드 블랙 트리에서는 마지막에 레드 간선을 접어 원래 2-3-4 노드를 복원하면 색과 구조를 함께 검산할 수 있습니다.

예상문제 10선

1. 2-3 트리의 3-노드에 대한 설명으로 옳은 것은?

① 키 3개와 자식 2개를 가진다. ② 키 3개와 자식 3개를 가진다. ③ 정렬된 키 2개와 자식 3개를 가진다. ④ 키 2개와 자식 4개를 가진다.

정답입니다.

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

정답 및 해설 보기

정답: ③

① 오답: 노드 이름의 숫자를 키 수로 잘못 해석했고 키 수와 자식 수도 뒤바뀌었다.
② 오답: 자식 수는 맞지만 3-노드의 키는 자식보다 하나 적은 2개이다.
③ 정답: 두 키가 왼쪽·가운데·오른쪽의 세 탐색 구간을 만든다.
④ 오답: 자식 4개를 가지려면 키가 3개인 4-노드여야 한다.

2. 키가 [18, 41]인 3-노드에서 키 35를 찾을 때 선택할 자식은?

① 가운데 자식 ② 왼쪽 자식 ③ 오른쪽 자식 ④ 모든 자식을 동시에 탐색

정답입니다.

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

정답 및 해설 보기

정답: ①

① 정답: 18<35<41이므로 두 경계 키 사이를 담당하는 가운데 자식으로 간다.
② 오답: 왼쪽 자식은 18보다 작은 키의 구간이다.
③ 오답: 오른쪽 자식은 41보다 큰 키의 구간이다.
④ 오답: 탐색 트리는 비교 결과로 가능한 구간 하나만 선택한다.

3. 2-3 트리의 가득 찬 잎에 키를 삽입해 임시 키가 [8, 11, 14]가 되었다. 올바른 다음 동작은?

① 8을 부모로 올리고 [11, 14]를 한 노드에 둔다. ② 14를 부모로 올리고 [8, 11]을 한 노드에 둔다. ③ 세 키를 그대로 두고 자식 수만 늘린다. ④ 11을 부모로 올리고 [8]과 [14]로 분리한다.

정답입니다.

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

정답 및 해설 보기

정답: ④

① 오답: 최솟값을 올리면 오른쪽 노드에 두 키가 남아 대칭적인 분리가 되지 않는다.
② 오답: 최댓값을 올리는 것도 가운데 키 승격 규칙에 어긋난다.
③ 오답: 2-3 트리는 키 세 개짜리 내부 노드를 허용하지 않는다.
④ 정답: 가운데 키가 부모의 경계가 되고 양 끝 키가 두 노드로 나뉜다.

4. 2-3 트리 삭제에서 회전과 결합을 구분하는 기준으로 가장 알맞은 것은?

① 삭제한 키가 홀수인지 짝수인지 확인한다. ② 인접 형제가 여분 키를 가진 3-노드인지 확인한다. ③ 루트 키가 삭제 키보다 큰지만 확인한다. ④ 트리의 전체 키 개수가 4의 배수인지 확인한다.

정답입니다.

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

정답 및 해설 보기

정답: ②

① 오답: 키의 홀짝은 노드의 최소 용량 복구와 관계없다.
② 정답: 형제에게 여분 키가 있으면 부모 경계 키를 거쳐 회전하고, 없으면 결합한다.
③ 오답: 값의 대소만으로 형제의 대여 가능 여부를 알 수 없다.
④ 오답: 복구는 전체 개수가 아니라 현재 빈 노드와 인접 형제의 용량으로 결정한다.

5. 본문의 삭제 예에서 7을 삭제하고 왼쪽 형제 [1, 2]와 회전한 직후의 루트와 가운데 잎은?

① 루트 [2, 8], 가운데 잎 [5] ② 루트 [1, 8], 가운데 잎 [2] ③ 루트 [5, 8], 가운데 잎 [2] ④ 루트 [2, 5], 가운데 잎 [8]

정답입니다.

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

정답 및 해설 보기

정답: ①

① 정답: 형제의 2가 부모로 올라가고 부모의 경계 키 5가 빈 가운데 잎으로 내려간다.
② 오답: 형제의 최솟값 1을 올리면 왼쪽 잎과 부모 사이의 구간 관계가 맞지 않는다.
③ 오답: 2를 가운데로 직접 옮기면 부모 경계 키를 거치는 회전이 아니다.
④ 오답: 8은 가운데와 오른쪽 구간의 경계이므로 이 회전에 참여하지 않는다.

6. 2-3-4 트리의 4-노드가 가지는 키와 자식 수는?

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

정답입니다.

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

정답 및 해설 보기

정답: ③

① 오답: 키 수와 자식 수의 관계를 반대로 적용했다.
② 오답: 키가 네 개이면 다섯 구간이 생기므로 4-노드의 정의와 맞지 않는다.
③ 정답: 세 경계 키가 네 개의 자식 구간을 만든다.
④ 오답: 키 두 개는 세 구간을 만드는 3-노드의 구성이다.

7. 삽입 경로에서 4-노드 [20, 35, 50]을 분리할 때 부모로 올라가는 키는?

① 20 ② 35 ③ 50 ④ 세 키 모두

정답입니다.

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

정답 및 해설 보기

정답: ②

① 오답: 20은 분리 뒤 왼쪽 2-노드에 남는다.
② 정답: 가운데 키 35가 두 분리 노드의 경계가 되어 부모로 승격한다.
③ 오답: 50은 분리 뒤 오른쪽 2-노드에 남는다.
④ 오답: 양 끝 키까지 올리면 아래에 분리 노드를 만들 수 없다.

8. 레드 블랙 표현에서 레드 간선과 블랙 간선을 올바르게 구분한 것은?

① 레드는 작은 키, 블랙은 큰 키를 연결한다. ② 레드는 잎만, 블랙은 내부 노드만 연결한다. ③ 레드는 서로 다른 트리, 블랙은 같은 노드의 키를 연결한다. ④ 레드는 한 2-3-4 노드 안의 키 관계, 블랙은 멀티웨이 노드 사이의 부모·자식 관계다.

정답입니다.

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

정답 및 해설 보기

정답: ④

① 오답: 키의 대소는 좌우 위치가 정하고 색은 결합 범위를 표시한다.
② 오답: 간선 색은 노드가 잎인지 내부인지에 따라 정해지지 않는다.
③ 오답: 레드와 블랙의 결합 의미를 서로 뒤바꾸었다.
④ 정답: 레드 간선을 접으면 원래 한 멀티웨이 노드의 키들을 복원할 수 있다.

9. 4-노드 [12, 18, 27]의 레드 블랙 표현으로 적절한 것은?

① 블랙 12의 오른쪽에 블랙 18과 블랙 27을 연속 연결한다. ② 블랙 18의 왼쪽 레드 자식 12와 오른쪽 레드 자식 27을 둔다. ③ 레드 18의 두 블랙 자식으로 12와 27을 둔다. ④ 블랙 27의 왼쪽에 레드 18, 그 왼쪽에 레드 12를 둔다.

정답입니다.

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

정답 및 해설 보기

정답: ②

① 오답: 모든 간선을 블랙으로 두면 세 키가 서로 다른 멀티웨이 노드로 해석된다.
② 정답: 가운데 키를 블랙 중심으로 두고 두 레드 자식을 접으면 한 4-노드가 된다.
③ 오답: 강의의 대응에서는 4-노드 중심 키가 블랙이고 같은 노드의 양 끝 키가 레드 자식이다.
④ 오답: 레드 간선을 연속으로 두는 사슬은 제시된 4-노드 대응과 다르다.

10. 멀티웨이 탐색 트리의 삽입·삭제 결과를 검산하는 순서로 가장 적절한 것은?

① 노드 색만 확인하고 키 순서와 잎 레벨은 생략한다. ② 전체 키 개수만 세고 자식 구간은 확인하지 않는다. ③ 노드 안 키 순서, 자식 값 범위, 허용 용량, 잎의 동일 레벨을 함께 확인한다. ④ 루트가 이전과 같으면 나머지 구조도 옳다고 판단한다.

정답입니다.

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

정답 및 해설 보기

정답: ③

① 오답: 색은 레드 블랙 표현의 한 조건일 뿐 탐색 순서와 전체 균형을 대신하지 않는다.
② 오답: 키 수가 맞아도 잘못된 자식 구간에 연결되면 탐색 트리가 아니다.
③ 정답: 지역 용량과 정렬 규칙, 서브트리 범위, 전역 잎 레벨을 모두 확인해야 한다.
④ 오답: 삽입·삭제 뒤 루트가 같아도 아래 노드의 용량이나 구간 연결이 깨질 수 있다.

참고 자료와 작성 기준

이 글은 한국방송통신대학교 자료구조 13강 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 노드 상태 변화, 직접 구성한 예제와 문제 해설은 학습자가 연산 과정을 재현하도록 구성하고 검토했습니다.

작성·편집: 올에이클래스 학습연구팀
주요 근거: 한국방송통신대학교 자료구조 13강 「멀티웨이 탐색 트리 II」
외부 보충 자료: 사용하지 않았습니다.
편집 원칙: 올에이클래스 편집 정책
최종 내용 검토: 2026-08-23

방송대 자료구조 13강 : 2-3-4 트리와 레드 블랙 트리