방송대 자료구조 12강 : 멀티웨이 탐색 트리와 B 트리 계열

방송대 자료구조 12강: 멀티웨이 탐색 트리와 B 트리 계열

트리의 높이를 줄이려고 한 노드에 여러 키를 넣으면, 탐색은 빨라질 수 있지만 삽입·삭제 때 노드를 나누고 빌리고 합치는 규칙이 필요해집니다. 이 글은 m원 탐색 트리의 구간 선택부터 B 트리의 균형 복구, B* 트리의 재분배, B+ 트리의 잎 연결까지 하나의 정보 이동 구조로 연결합니다.

한 노드의 여러 키는 여러 탐색 구간을 만든다

이진 탐색 트리는 한 키를 기준으로 왼쪽과 오른쪽 두 구간을 만듭니다. m원 탐색 트리는 한 노드가 최대 m개의 가지를 가질 수 있도록 이를 확장한 구조입니다. 노드에 정렬된 키가 n개 있으면 포인터는 최대 n+1개이며, 키 사이와 양 끝을 서로 다른 서브트리에 연결합니다.

예를 들어 한 노드의 키가 25, 47, 72라면 네 포인터가 담당하는 범위는 25 미만, 25와 47 사이, 47과 72 사이, 72 초과입니다. 키 61을 찾을 때는 25와 47을 지나고 72보다 작다는 사실로 세 번째 포인터를 선택합니다. 노드 안의 키는 데이터인 동시에 다음 서브트리를 고르는 경계표입니다.

구간 판정: 찾는 키와 같은 키가 노드 안에 있으면 탐색이 끝납니다. 없다면 처음으로 더 큰 키의 왼쪽 포인터를 선택하고, 모든 키보다 크면 맨 오른쪽 포인터를 선택합니다.

포인터와 키가 번갈아 놓여 구간의 경계를 보존한다

강의자료의 m원 노드는 P0, k0, P1, k1, ..., Pn-1, kn-1, Pn 순서로 구성됩니다. 키는 오름차순이고 각 포인터가 가리키는 서브트리에는 해당 구간의 키만 들어갑니다.

포인터	담당 범위	키가 25·47·72인 예
P0	k0보다 작은 키	25 미만
Pi	k(i-1)보다 크고 ki보다 작은 키	P1: 25~47, P2: 47~72
Pn	마지막 키보다 큰 키	72 초과

각 포인터가 가리키는 서브트리도 같은 규칙을 지키는 m원 탐색 트리입니다. 그래서 탐색은 한 노드 안에서 구간을 고르고, 선택한 서브트리에서 같은 판단을 반복하는 재귀 구조가 됩니다.

강의자료의 C 구조는 노드의 키 개수, 각 키와 왼쪽 서브트리 포인터, 실제 레코드 주소, 마지막 오른쪽 포인터를 함께 관리합니다. 핵심 탐색 흐름을 읽기 쉽게 정리하면 다음과 같습니다.

Record *Search(int skey, Mnode *r) {
    int i = 0;

    if (r == NULL) {
        return NULL;
    }
    while (i < r->n && skey > r->keyptrs[i].key) {
        i++;
    }
    if (i < r->n && skey == r->keyptrs[i].key) {
        return r->keyptrs[i].addr;
    }
    if (i < r->n) {
        return Search(skey, r->keyptrs[i].ptr);
    }
    return Search(skey, r->keyptrn);
}

while은 찾는 키보다 작은 노드 키를 건너뜁니다. 반복이 멈춘 위치의 키와 같으면 레코드 주소를 반환하고, 더 작으면 그 키 왼쪽의 포인터로 내려갑니다. 모든 키를 통과했다면 마지막 포인터로 내려갑니다.

가지 수가 늘면 높이는 낮아지지만 노드 내부 판단은 남는다

한 노드가 더 많은 서브트리를 가질수록 같은 키 수를 더 낮은 높이에 배치할 수 있습니다. 강의자료는 255개의 키를 4원 트리로 구성하면 최대 경로 길이가 4가 되는 예를 제시합니다. 한 번 내려갈 때 선택 가능한 구간이 많아지기 때문입니다.

그러나 가지 수만 크게 만든다고 항상 좋은 것은 아닙니다. 한 노드 안에서 여러 키를 비교해야 하고, 삽입과 삭제가 누적되면 특정 서브트리만 깊어질 수 있습니다. 일반 m원 탐색 트리는 서브트리 균형을 강제하지 않으므로 낮은 높이를 안정적으로 유지하려면 별도의 균형 규칙이 필요합니다.

오개념 교정: m원이라는 말은 모든 노드가 정확히 m개의 자식을 가진다는 뜻이 아닙니다. 최대 m개의 가지를 가질 수 있다는 뜻이며, 실제 자식 수는 노드 상태와 트리 규칙에 따라 달라집니다.

B 트리는 점유 하한과 같은 잎 레벨로 균형을 강제한다

B 트리는 m원 탐색 트리에 노드의 최소 점유와 잎 레벨 조건을 추가해 전체 높이를 관리합니다. 차수가 m인 B 트리에서 한 노드는 최대 m개의 서브트리와 m-1개의 키를 가집니다.

대상	B 트리 조건	조건이 필요한 이유
루트	잎이 아니라면 최소 2개의 서브트리	트리가 실제로 아래 레벨로 분기되게 함
루트·잎을 제외한 노드	최소 ceil(m/2)개의 서브트리	지나치게 빈 노드가 높이를 늘리지 않게 함
모든 노드	최대 m개의 서브트리	차수의 상한을 유지함
모든 잎	같은 레벨에 위치	어느 탐색 경로도 비슷한 깊이를 갖게 함

예를 들어 차수 5라면 루트와 잎이 아닌 노드는 최소 ceil(5/2)=3개의 서브트리를 가져야 합니다. 내부 노드가 3개의 서브트리를 가지면 경계 키는 2개입니다. 자식 수와 키 수를 혼동하지 않으려면 항상 ‘포인터 수 = 키 수 + 1’ 관계를 함께 적습니다.

이상적으로 꽉 찬 m원 트리보다 B 트리가 순간적으로 조금 더 깊을 수는 있습니다. 하지만 삽입·삭제 때 모든 노드를 완벽히 채우는 비용을 쓰는 대신 최소 점유와 잎 높이를 유지하는 것이 실제 갱신에는 더 효율적입니다.

삽입은 잎에서 시작하고 넘치면 중간 키를 위로 보낸다

B 트리 삽입은 탐색 규칙으로 들어갈 잎을 찾는 데서 시작합니다. 잎에 빈자리가 있으면 정렬 순서에 맞춰 키를 넣고 끝납니다. 노드가 가득 찼다면 기존 키와 새 키를 합쳐 정렬한 뒤 두 노드로 나누고, 중간 키와 새 노드를 가리킬 포인터를 부모로 올립니다.

1. 삽입할 잎 노드를 찾습니다.
2. 빈자리가 있으면 키를 정렬된 위치에 넣습니다.
3. 가득 찼으면 키와 포인터를 두 노드에 나누고 중간 키를 선택합니다.
4. 중간 키를 부모에 삽입하고 부모의 새 포인터를 연결합니다.
5. 부모도 넘치면 같은 분할을 위쪽으로 반복합니다.
6. 루트가 갈라지면 중간 키가 새 루트가 되어 높이가 1 증가합니다.

직접 구성한 3차 B 트리 삽입

차수 3에서는 노드 하나에 키를 최대 2개 둘 수 있다고 가정합니다. 빈 트리에 40, 20을 넣으면 루트는 [20, 40]입니다. 60을 넣으면 임시로 [20, 40, 60]이 되어 넘치므로 40을 부모로 올리고 잎 [20]과 [60]으로 나눕니다. 새 루트는 [40]입니다.

이어서 10을 넣으면 왼쪽 잎은 [10, 20]이 됩니다. 30을 더 넣으면 [10, 20, 30]에서 중간 키 20을 올려 루트가 [20, 40]이 되고, 잎은 [10], [30], [60]이 됩니다. 모든 잎은 여전히 같은 레벨입니다.

분할 검산: 중간 키보다 작은 키는 왼쪽, 큰 키는 오른쪽에 남아야 합니다. 부모로 올라간 키의 왼쪽·오른쪽 포인터가 새 두 노드를 가리키고 모든 잎 레벨이 같아야 합니다.

삭제는 기준 키를 바꾸고 부족한 노드를 빌리거나 합친다

잎에서 키를 삭제한 뒤에도 최소 키 개수가 유지되면 재배열이 필요 없습니다. 내부 노드의 키를 지우면 그 키가 서브트리 구간의 기준이므로, 왼쪽 서브트리의 가장 큰 키 또는 오른쪽 서브트리의 가장 작은 키로 대체한 뒤 실제 키는 잎에서 삭제합니다.

삭제 결과 노드가 최소 점유보다 작아지면 세 가지 순서로 복구합니다.

1. 오른쪽 형제에게 빌리기: 오른쪽 형제에 여분이 있으면 부모 기준 키를 부족한 노드로 내리고, 오른쪽 형제의 첫 키를 부모로 올립니다.
2. 왼쪽 형제에게 빌리기: 왼쪽 형제에 여분이 있으면 부모 기준 키를 부족한 노드로 내리고, 왼쪽 형제의 마지막 키를 부모로 올립니다.
3. 합치기: 두 형제 모두 최소 상태라면 부모 기준 키와 두 노드를 하나로 합치고 빈 형제를 제거합니다.

합친 뒤 부모가 다시 최소 점유를 밑돌면 같은 복구를 위쪽으로 반복합니다. 루트의 키가 없어졌다면 합쳐진 자식이 새 루트가 되어 높이가 1 줄어듭니다.

앞의 삽입 결과에서 10을 삭제한다면

루트 [20, 40]과 잎 [10], [30], [60]에서 10을 지우면 왼쪽 잎이 비게 됩니다. 오른쪽 형제 [30]도 최소 키만 가져 빌려줄 수 없으므로, 빈 노드와 부모 기준 키 20, 형제의 30을 합쳐 [20, 30]을 만듭니다. 부모는 [40], 잎은 [20, 30]과 [60]이 되어 조건을 회복합니다.

잘못된 접근: 부족한 노드에 형제의 키만 바로 옮기면 부모의 구간 경계가 예전 값으로 남습니다. 빌리기에서는 부모 키가 아래로 내려가고 형제의 경계 키가 부모로 올라오는 회전이 함께 일어나야 합니다.

B* 트리는 먼저 형제와 재분배해 노드 분할을 늦춘다

B* 트리는 노드를 대략 2/3 이상 채우도록 요구해 같은 수의 키를 더 적은 노드에 담고, 삽입 때 발생하는 분할을 줄이려는 B 트리 변형입니다. 노드가 가득 차도 곧바로 둘로 나누지 않고, 인접 형제에 여유가 있으면 부모의 기준 키까지 포함해 키와 포인터를 재분배합니다.

형제도 가득 찼다면 두 형제와 새 키를 세 노드로 재구성하고 경계 키를 부모에 반영합니다. 즉 B 트리는 ‘한 노드가 넘치면 두 노드로 분할’하는 반면, B* 트리는 ‘형제와 먼저 나눠 쓰고, 필요할 때 두 노드를 세 노드로 확장’하는 흐름입니다.

구분	B 트리	B* 트리
일반 최소 점유	약 1/2	약 2/3
가득 찬 노드 삽입	노드를 둘로 분할	형제에 여유가 있으면 먼저 재분배
형제도 가득 참	해당 노드 중심으로 분할·상향 전달	두 노드를 세 노드로 만들고 부모 경계 갱신
설계 목표	균형과 최소 점유 유지	점유율을 높이고 분할 빈도 감소

강의자료의 차수 m인 B* 트리 조건에는 모든 잎의 동일 레벨, 내부 노드의 최소 ceil((2m-1)/3)개 자식, 포인터가 k개인 비잎 노드의 k-1개 키가 포함됩니다. 루트는 예외적인 자식 수 범위를 갖습니다. 핵심은 공식만 외우기보다 B 트리보다 높은 점유 하한이 재분배 우선 정책과 연결된다는 점입니다.

B+ 트리는 탐색용 경계와 실제 레코드 위치를 분리한다

B+ 트리에서는 모든 키가 잎 노드에 있고, 실제 데이터에 대한 주소도 잎 노드만 가집니다. 내부 노드의 키는 어느 자식으로 내려갈지를 정하는 탐색용 경계입니다. 따라서 특정 키의 직접 탐색은 반드시 잎에 도달해야 끝납니다.

잎 노드들은 키 순서대로 연결되는 포인터를 가집니다. 한 키를 찾은 뒤에는 트리 위로 되돌아가 다음 구간을 다시 찾지 않고, 잎의 마지막 포인터를 따라 다음 잎으로 이동할 수 있습니다. 이 때문에 B+ 트리는 직접 탐색뿐 아니라 인덱스된 순차 파일의 차례 처리에도 적합합니다.

삽입으로 잎이 넘치면 키 순서에 따라 두 잎으로 나누고 경계 키를 부모에 올립니다. B+ 트리의 부모 키는 탐색용 복사본이므로 실제 키와 레코드 주소는 잎에 남습니다. 잎에서 첫 키를 삭제해 경계가 바뀌면 내부 노드의 탐색용 키도 새 첫 키에 맞춰 갱신해야 합니다.

키 위치 판정: 내부 키에서 탐색이 끝나고 그 키가 레코드 주소를 직접 가지면 B 트리 관점입니다. 모든 실제 레코드 주소가 잎에 있고 잎이 다음 잎과 연결되면 B+ 트리입니다.

네 구조는 가지 수보다 키의 역할과 복구 전략으로 구분한다

구조	균형·점유 규칙	키와 데이터 위치	갱신·접근의 특징
m원 탐색 트리	일반적으로 균형 강제 없음	각 노드의 키가 구간 분할	가지 수로 높이를 줄일 수 있으나 편향 가능
B 트리	최소 약 1/2 점유, 모든 잎 같은 레벨	내부·잎 키가 탐색과 레코드 접근에 참여	넘치면 분할, 부족하면 회전 또는 합병
B* 트리	최소 약 2/3 점유	B 트리와 같은 검색 트리 계열	분할 전에 형제 재분배를 우선
B+ 트리	B 트리 계열의 균형 유지	실제 레코드 주소는 잎에만 존재	연결된 잎으로 직접 탐색과 순차 처리 지원

B, B*, B+는 서로 무관한 이름이 아닙니다. 모두 여러 키로 탐색 구간을 나누고 높이를 제한하려는 계열이며, B*는 점유율과 분할 전략을, B+는 키와 레코드의 배치 및 잎 연결을 바꿉니다.

멀티웨이 문제는 구간·점유·이동의 세 층으로 푼다

1. 구간: 노드 키를 오름차순으로 놓고 찾는 키가 어느 두 경계 사이인지 판정합니다.
2. 구조: 차수 m에서 최대 자식·키 수와 해당 구조의 최소 점유를 확인합니다.
3. 삽입: 잎의 빈자리 여부를 보고, 넘치면 중간 키 상향 또는 B*의 형제 재분배를 적용합니다.
4. 삭제: 내부 키라면 잎의 선행·후행 키로 대체하고, 부족하면 여분 있는 형제에게 빌린 뒤 합병을 검토합니다.
5. 키의 역할: B+ 트리라면 내부 키는 경계표이고 실제 레코드 주소와 순차 링크는 잎에 있음을 확인합니다.
6. 최종 검산: 키 정렬, 포인터 수, 점유 하한, 잎 레벨, 부모 경계가 모두 맞는지 확인합니다.

이 세 층을 섞지 않으면 문제를 안정적으로 풀 수 있습니다. 먼저 값이 들어갈 구간을 찾고, 다음으로 노드의 점유 조건을 검사한 뒤, 마지막으로 키와 포인터가 부모·형제·잎 사이에서 어디로 이동했는지 추적합니다.

핵심 개념 정리

• m원 탐색: 정렬된 n개 키는 n+1개 구간을 만들며 선택한 포인터에서 탐색을 반복합니다.
• B 트리 균형: 최소 점유와 같은 잎 레벨을 유지하며 삽입은 분할, 삭제는 빌리기·합병으로 복구합니다.
• B* 트리 전략: 더 높은 점유율을 위해 형제 재분배를 분할보다 먼저 시도합니다.
• B+ 트리 배치: 실제 레코드 주소는 잎에만 두고 잎을 순서대로 연결합니다.
• 공통 검산: 키 순서, 포인터 수, 점유 범위, 잎 레벨과 부모 경계의 일치를 함께 확인합니다.

멀티웨이 트리를 만나면 이름부터 외우지 말고 한 노드의 키가 만드는 구간을 먼저 그리세요. 그다음 차수와 최소 점유를 적용해 분할·회전·합병 여부를 정하고, 키가 부모로 올라가거나 형제 사이에서 이동할 때 포인터 구간도 함께 바뀌는지 확인합니다. 마지막으로 B+ 트리라면 실제 데이터와 순차 링크가 잎에 남는지 점검하면 네 구조를 같은 원리로 해석할 수 있습니다.

예상문제 10선

1. m원 탐색 트리의 한 노드에 25, 47, 72가 있을 때 키 61을 찾기 위해 선택할 구간은?

① 25보다 작은 첫 번째 구간 ② 25와 47 사이의 두 번째 구간 ③ 72보다 큰 마지막 구간 ④ 47과 72 사이의 세 번째 구간

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 61은 25보다 크므로 맨 왼쪽 포인터의 범위가 아니다.
• ② 오답: 61은 47보다 커서 25와 47 사이에 포함되지 않는다.
• ③ 오답: 61은 72보다 작으므로 맨 오른쪽 포인터까지 진행하지 않는다.
• ④ 정답: 47<61<72이므로 두 경계 사이의 포인터를 선택한다.

2. 한 노드에 정렬된 키가 n개 있는 m원 탐색 트리에서 필요한 서브트리 포인터 수는?

① n-1개 ② n+1개 ③ 2n개 ④ 키 수와 같은 n개

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: 키 사이 구간만 세고 양 끝의 두 구간을 빠뜨린 수다.
• ② 정답: n개 키는 키 사이 n-1개 구간과 양 끝 2개를 합쳐 n+1개 구간을 만든다.
• ③ 오답: 키마다 좌우 포인터를 따로 두는 이진 노드식 계산을 적용했다.
• ④ 오답: 마지막 키보다 큰 범위를 담당할 추가 포인터가 필요하다.

3. 차수 5인 B 트리의 루트·잎이 아닌 노드가 가져야 할 최소 서브트리 수와 그때의 키 수는?

① 서브트리 2개, 키 2개 ② 서브트리 2개, 키 1개 ③ 서브트리 3개, 키 2개 ④ 서브트리 3개, 키 3개

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 최소 서브트리는 ceil(5/2)=3개이며 포인터와 키 수도 같지 않다.
• ② 오답: 키 수 1개는 포인터 2개와 대응하지만 차수 5 내부 노드의 최소 점유에 못 미친다.
• ③ 정답: 최소 포인터는 3개이고 경계를 나누는 키는 하나 적은 2개다.
• ④ 오답: 포인터가 3개이면 키는 2개여야 구간 수 관계가 맞는다.

4. B 트리의 가득 찬 잎에 새 키를 삽입할 때 이어지는 흐름은?

① 키 정렬 → 두 노드로 분할 → 중간 키와 포인터를 부모에 삽입 ② 부모 삭제 → 잎 합병 → 가장 작은 키를 루트로 이동 ③ 새 키 폐기 → 오른쪽 포인터 제거 → 잎 레벨 변경 ④ 형제의 모든 키 이동 → 부모 경계 유지 → 노드 삭제

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 넘친 키 집합을 양쪽으로 나누고 중간 경계를 부모에 올려 탐색 구간을 다시 연결한다.
• ② 오답: 합병은 삭제 후 점유 부족을 복구하는 흐름이며 삽입 분할과 반대다.
• ③ 오답: 삽입 키를 보존하면서 균형을 유지해야 하며 잎 높이를 임의로 바꾸지 않는다.
• ④ 오답: 형제 재분배는 B* 트리에서 먼저 고려하지만, 부모 경계도 함께 갱신해야 한다.

5. 차수 3 B 트리의 가득 찬 노드 [20, 40]에 60을 넣어 분할할 때 부모로 올라갈 키는?

① 20 ② 60 ③ 40 ④ 20과 60 모두

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 20을 올리면 왼쪽에 배치할 더 작은 키가 없어 분할이 한쪽으로 치우친다.
• ② 오답: 가장 큰 키를 올리면 오른쪽 새 노드에 남길 큰 키가 없다.
• ③ 정답: 정렬된 20, 40, 60의 중간값 40이 경계가 되고 양쪽에 20과 60이 남는다.
• ④ 오답: 부모에는 두 자식 구간을 가르는 중간 키 하나를 올린다.

6. B 트리 삭제 후 부족한 노드가 여분 있는 오른쪽 형제에게 키를 빌릴 때 빠뜨리면 안 되는 변화는?

① 부족한 노드의 모든 키를 삭제한다. ② 두 노드의 잎 레벨을 서로 다르게 만든다. ③ 오른쪽 형제의 마지막 키를 바로 루트로 보낸다. ④ 부모 경계 키를 아래로 내리고 형제의 첫 키로 부모 경계를 갱신한다.

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 목적은 부족한 키 수를 채우는 것이므로 기존 키까지 없애면 결손이 커진다.
• ② 오답: B 트리는 모든 잎이 같은 레벨이어야 하며 회전은 높이를 바꾸지 않는다.
• ③ 오답: 오른쪽에서 빌릴 때는 형제의 첫 키가 경계에 가장 가까우며 루트까지 직접 보낼 필요도 없다.
• ④ 정답: 부모 키와 형제 경계 키가 함께 회전해야 두 서브트리의 범위가 올바르게 유지된다.

7. B* 트리가 B 트리와 구별되는 삽입 전략은?

① 넘친 노드의 모든 키를 잎에서 제거한다. ② 가득 찬 노드를 즉시 나누기 전에 인접 형제와 재분배를 시도한다. ③ 모든 내부 키를 삭제하고 잎 포인터만 연결한다. ④ 점유 하한을 B 트리보다 낮춰 빈 공간을 늘린다.

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: 키를 보존하면서 형제와 나누어 담는 것이 목적이지 데이터를 제거하는 것이 아니다.
• ② 정답: 형제 여유를 먼저 활용하고 둘 다 찼을 때 두 노드를 세 노드로 확장해 분할 빈도를 줄인다.
• ③ 오답: 이는 B+ 트리의 잎 연결을 잘못 단순화한 설명이며 B*의 분할 전략이 아니다.
• ④ 오답: B* 트리는 약 2/3 점유를 요구해 B 트리보다 하한을 높인다.

8. B+ 트리에서 실제 레코드 주소와 순차 접근 포인터가 위치하는 곳은?

① 잎 노드 ② 루트 노드만 ③ 모든 내부 노드만 ④ 부모가 없는 노드만

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 모든 실제 키와 레코드 주소가 잎에 있고 잎의 마지막 포인터가 다음 잎을 연결한다.
• ② 오답: 루트는 탐색 경계를 제공할 수 있지만 실제 레코드 주소를 독점하지 않는다.
• ③ 오답: 내부 노드 키는 내려갈 방향을 정하는 경계이며 실제 주소는 잎에 둔다.
• ④ 오답: 부모가 없는 노드는 루트이며 순차 데이터 연결 위치와 다르다.

9. B+ 트리에서 잎의 첫 키를 삭제해 그 잎의 최솟값이 달라졌다면 추가로 확인할 것은?

① 모든 잎의 레코드 주소를 내부 노드로 이동한다. ② 이전 잎과 다음 잎의 키를 역순으로 배치한다. ③ 부모의 탐색용 경계 키를 새 첫 키에 맞게 갱신한다. ④ 내부 노드에서 같은 키의 실제 레코드를 삭제한다.

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: B+ 트리의 실제 레코드 주소는 계속 잎에 남아야 한다.
• ② 오답: 잎 연결은 키의 오름차순 처리를 위한 것이므로 역순 재배치는 목적과 맞지 않는다.
• ③ 정답: 내부 키는 자식 범위를 안내하므로 잎의 경계가 바뀌면 탐색 경계도 일치시켜야 한다.
• ④ 오답: 내부의 같은 값은 실제 레코드가 아니라 탐색용 경계이므로 레코드 삭제 대상으로 해석하지 않는다.

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

① 잎 레벨 변경 → 키 역순 정렬 → 차수 추정 → 포인터 제거 ② 데이터 주소 이동 → 모든 노드 합병 → 루트 삭제 → 구간 확인 ③ 형제 선택 → 키 값 폐기 → 부모 경계 유지 → 점유 조건 생략 ④ 탐색 구간 판정 → 차수·점유 확인 → 분할·회전·합병 추적 → 키·포인터·잎 레벨 검산

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 잎 레벨은 유지할 조건이며 키를 역순으로 바꾸거나 차수를 결과에서 추정하지 않는다.
• ② 오답: 삭제·합병부터 시작하면 찾을 위치와 최소 점유를 판단할 근거가 없다.
• ③ 오답: 키를 보존하고 부모 경계를 함께 갱신해야 하며 점유 조건은 복구 여부의 핵심이다.
• ④ 정답: 위치를 찾고 구조 규칙을 적용한 뒤 이동 결과의 정렬·연결·균형을 검증하는 순서다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 m원 탐색 트리와 B 트리 계열의 구조·갱신 관계를 학습 목적에 맞게 재구성한 비공식 학습자료입니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 자료구조 12강 「멀티웨이 탐색 트리 Ⅰ」 강의록(2023)
• 보충 자료: 외부 자료는 사용하지 않았으며 수치·삽입·삭제 예제는 강의 범위 안에서 학습용으로 직접 구성했습니다.
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-08-18