BJ.54-2 B tree 데이터 삭제 동작 방식을 설명합니다 (DB 인덱스과 관련있는 자료 구조) - ko

네 반갑습니다 오늘이 영상을 끝까지 보신 후에

피트리에서 데이터가 어떻게 삭제되는지 그 삭제

방식을 알게 됩니다 자 그러면 오늘도 고고싱 자 우리가 지난 시간에 배웠던

내용부터 다시 한번 복습을 해 보도록 하겠습니다이 비트리는 이진 탐색 트리

영어로는 바이너리 서치트리라고도 하는데요이 이진 탐색 트리를 일반화한

트리입니다 그래서 보시면 바이너리 서치트리처럼이 빅트리에서도

키를 기준으로 왼쪽에 서브 트리는 그 키보다 작은

값들을 가지고요 오른쪽 서브 트리는 그 키보다 큰 값을 가집니다 그리고

이런 특징이 모든 데이터에서 동일하게 적용이 된다는 거죠 그래서이 3의

경우에도 3의 왼쪽 서브 트리는 3보다 작은 값을 가지고 3의 오른쪽

서버트리는 3보다 큰 값을 가집니다 30도 한번 살펴보면

30의 왼쪽 서브트리는 30보다 작은 값을 가지고

30의 오른쪽 서브트리는 30보다 큰 값을 가지죠 그래서

피트리도 이진 탐색 트리처럼 이런 특징을 가지고요

그러면 이 비트리를 이진 탐색 트리를 1번

화환 형태라고 말을 하는 거냐 그것은 바이너리서치 트리 같은 경우에는

부모노드가 가질 수 있는 잔여 노드의 최대 수는 2개였어요

그렇기 때문에 바이너리라고 하는 거죠 그런데이 빅트리에서는 부모노드는

잔여 노드를 두 개 이상 가질 수가 있습니다 그래서 오른쪽에 보시면

얘 같은 경우에는 잔여 노드를 3개를 가지고 있다라는

것을 확인하실 수 있습니다 그리고 또 피트리는 어떤 특징이 있냐면

얘는 만약에 어떤 노드가 잔여 노드를 x계를 가졌다면 그

노드의 키의 수는 x - 한 개를 가진다는 그런 특징이 있습니다 그래서

지금도 보시면이 노드 같은 경우에는 자녀가 총 3개잖아요

그러면 이때의이 노드의 키의 수는 두 개가 되는 거고요 마찬가지로 얘 같은

경우에는 잔여 노드의 수가 두 개인 거잖아요

그러면 그때이 노드의 키의 수는 한계가 되는 겁니다 자 그러면 여기서

우리가 추론해 볼 수 있는 것은이 빅토리에서는 각 노드에서 한 개

이상의 키를가 있다라는 겁니다 그러면 이때이 키들이 어떻게 저장이 돼야

되냐면 오름차순으로 저장이 되어야 됩니다

그러니까 각 노드에서 그 노드에 있는 키들이 한 개 이상이 있을 수가

있으니까 그러면 이때이 키들을 저장하는 방식은

오름차순으로 정렬을 해서 저장을 한다는 거죠 그리고 또 피트리는 어떤

특징이 있냐 지금이 그림에서도 보시는 것처럼

얘네들이 다 리프 노드잖아요이 리프 노드들은 모두가 다 같은 레벨에

있습니다 이게 우리가 일부 영상에서 데이터를 삽입할 때도 얘를 살펴봤고

오늘 또 삭제를 할 때도 보시면은 모든 리프 노드들은 같은 레벨에

있다는 것을 확인할 수 있을 거예요 그 다음에 우리가 일부 영상에서

비트리와 관련 있는 4개의 파라미터를 살펴봤습니다 그것을

다시 한번 요약을 해서 보면 일단 가장 근본이 되는 파라미터는이

파라미터라고 했어요 비트리에서 각 노드가 가질 수 있는 최대 잔여

노드 수를 몇 개로 할 것인가 이게 가장 중요한 파라미터가 되고요

얘를 m으로 표기한다고 했습니다 그러면 비트리를 사용하기 위해서

얘만 결정 지어주면 아버지 세계에 파라미터는 자연스럽게 자동적으로

결정이 된다고 했어요 그래서 그 나머지 3개의 파라미터를 살펴보면

먼저 각 노드의 최대 키수는 m-1입니다 여기서 정해진 값에서

하나를 빼준 거예요 이때 왜 1을 빼주는지는 이제는 다 이해를 하시죠

자 그 다음에 또 다른 파라미터는 각 노드의 최소 잔여 노드 수입니다

얘는 m으로 정한 값을 2로 나눠서 그렇게 나온 값을 올림 한 값 바로

그 값이 각 로드가 최소로 가져야 되는

잔여 노드의 수가 되는 겁니다 그 다음에 마지막 파라미터는

각 노드의 최소 키였습니다 얘는 바로 앞에서 구한 e 값에서

1을 빼면 바로이 값이 되겠죠 그리고 오늘 영상에서는 바로이 조건이 조건이

매우 중요한 역할을 하기 때문에 얘를 잘 기억을 해주시면 좋을 것

같습니다 자 그러면 본격적으로 비트리에서 데이터를 삭제하는 방법을

배워보도록 하겠습니다 일단 이해하기 쉽게 나름대로 요약해서 몇 개의

간단한 문장으로 설명을 드리면 우선 데이터 삽입할 마찬가지로

비트리에서 데이터를 삭제하는 경우에도 항상 리프 노드에서 발생을 합니다

그런데 제가 이렇게 말씀을 드리면 좀 의아해 하실 분들도 계실 것 같아요

왜냐하면 데이터 삭제는 리프 노드뿐만 아니라 이렇게 인터널 노드에서도

발생할 수 있는데 그런데 어떻게 삭제는 항상

리프 노드에서 발생한다고 얘기를 하는 걸까

그렇게 의아해하실 수가 있는데요 이것과 관련되서 자세한 설명은 나중에

할 거니깐요 일단 지금은 이렇게 기억을 해주시면 좋을 것 같습니다 자

그래서 일단 피트리의 데이터 삭제는 리프 노드에서 발생을 하고요 그러면

그렇게 데이터를 삭제를 했는데 만약에 데이터를 삭제한 후에 그 노드에 있는

데이터의 수가 혹은 그 노드에 있는 키의 수가 최소한의 키스보다

적어졌다면 그때는 그 트리를 재조정을 해줘야 됩니다 그래서

간단하게 다시 말씀을 드리면 비트리의 데이터 삭제는 리프 노드에서 발생을

하고 그렇게 데이터를 삭제를 했는데

삭제한 후에 그 노드에 있는 데이터의 수가 최소 키수보다 적어졌다면 그때는

그 트리를 재조정을 한다 그렇게 기억을 해 주시면 좋을 것 같습니다

자 그리고 참고로 지금 제가 데이터라는 용어와 키라는 용어를

섞어서 사용을 하고 있는데요 좀 더 정확하게 얘기하면

피트리에 저장되는 데이터들이 있으면 그 데이터 각각은 키가 있을 거예요

그러면 실제로이 비트리가 동작하는 방식은 그 각각의 데이터에 있는 키를

기준으로 동작을 하게 됩니다 그런데 지금은이 데이터 각각이 키의

역할까지도 하고 있기 때문에 설명을 편하게 하기 위해서

데이터라는 단어와 키라는 단어를 섞어가면서 그렇게 설명을 하고 있는

거거든요 그래서이 부분을 참고를 해주시면 좋을 것 같아요 자 그러면

다시 돌아와서 빅트리에서 데이터를 삭제를 할 때는이

두 문장을 잘 기억을 해주시면 좋을 것 같고요

그러면 최소 치수라는이 조건이 중요한 조건이 되는 거잖아요 그래서 얘를 좀

더 살펴보면 이런 조건이었던 거죠 그래서 비트리에서 각 노드의 최소

키수는이 m을 기준으로 m을 2로 나눠서 나눈 값을 올림 한 뒤에

거기서 1을 뺀 값 극값이 바로이 빅토리에서 각 노드의 최소 치수다이

조건을 비트리는 만족을 해야 된다 이렇게 우리가

앞에서 배웠었습니다 자 여기서이 m이 무엇을 의미하는지는 기억나시죠이

픽트리에서 최대 몇 개의 잔여 노드를 가질 수 있도록 할 것인가 이것을

결정하는 파라미터라고 했고 가장 중요하고 근본이 되는 파라미터라고

했습니다 자 그러면 이제이 데이터 삭제를 예를 통해서 실제로 살펴보도록

할게요 지금 오른쪽에 보시는이 트리를 기준으로 설명을 드릴 거라서 이틀이는

지금 3차 픽트리거든요 즉 m이 3이라는 겁니다

그러면 이제이 3차 비트리에서이 값이 어떻게 되는지를 계산을 해보면 3을

2로 나눈 값은 1.5인데 1.5를 올림을 하면은 얘는 2가 되는 거고이

2에서 1을 빼면 1이 되는 거잖아요 그 말은 결국 3차 비트리에서

각 노드가 가져야 되는 최소한의 키의 수는 한 개다 그런 조건이 이제

존재하게 되는 겁니다 자 그러면 이제이 조건을 바탕으로 데이터 삭제를

해 볼 건데요 그런데 일단 보기 편하게이 조건을 이쪽 아래로 이렇게

옮겨 보도록 하겠습니다 자 그리고 나서 이제

본격적으로 삭제를 시작할 건데요 6을 삭제해 보도록 하겠습니다

그러면 6을 삭제를 하려면 일단 6을 찾아야

되잖아요 그래서이 루트 노드에서부터 조회를 시작해 보도록 하겠습니다

그런데이 루트 노드에서는 6은 없어요 대신에 15가 있습니다

그러면 6과 15를 비교를 하면

6은 15보다 작기 때문에 15의 왼쪽 서브 트리로 내려가서 6을 또

찾아야 됩니다 그래서 첫 번째로 확인을 해봤더니 얘는 3이에요

그러면은 6은 3보다 크잖아요 그래서이어서

얘를 또 확인을 해봅니다 그런데 이번에는

실은 6보다 큽니다 그래서 여기서도 찾으려는 6은 없었기 때문에 다시

한번 또 서브 트리로 가야 되는데이 서버트리로 가면 되겠죠 6은 3과 7

사이에 있는 값이니까요 그래서 이쪽으로 내려와서 같은 방식으로

찾았더니 결국 여기서 6을 찾았어요

그러면은 얘는 이제 리프 노드에 있으니까

리프 노드에 있는 얘를 바로 삭제를 해주면 됩니다 그래서 이렇게 6을

삭제를 해줬는데 삭제하고 나서이 노드에 있는 키의

수가 한 개가 됐잖아요 그러면은이 한 개라는 값은 3차

비트리에서 다운로드가 최소로 가져야 되는 키의 수와 동일하기 때문에

얘는 여전히 피트리에 속성을 만족하고 있다라고 볼 수 있고

그러면 이대로 6에 대한 삭제는 완료가 되는 겁니다

그러면이어서 5를 삭제를 해보도록 하겠습니다

그러면 루트 노드에서 5가 있는지를 확인을 하는데 지금 5는 없고 15만

있잖아요 그래서 5와 15를 비교를 하는데 5가 더

작기 때문에 이쪽 서브 트리로 빠져서이 노드에서 다시 한번 똑같은

과정을 반복을 해요 첫 번째 값을 확인을 하는데

5와 비교를 해봤더니 5가 3보다 더 큽니다 그래서이어서 얘를 또 확인을

해봅니다 이번에도 얘는 5는 아니에요 대신에 5는 7보다

작기 때문에 그러면은 이번에는 이쪽 서버트리로 또

찾으러 가야 되는 겁니다 그렇게 해서 여기서 5를 찾게 됐어요

그러면 이제 얘를 삭제를 해주면 되잖아요 그래서 이렇게 삭제를

해줬는데 삭제를 해주고 나서 보니까

어떤 문제가 생겼냐면이 노드에는 아무런 키가 없게 된 겁니다

그러니까이 노드의 키의 수가 0개가 된 거예요 그러면 얘는 3차 B

트리의이 조건이 조건 위반을 하게 된 거잖아요

그러면 이제이 부분을 해결을 해 줘야 되는 거거든요

즉 이제이 부분을 재조정을 해줘야 되는 겁니다

그러면 이제부터 어떻게 재조정을 해줄 수 있는지 그것을 좀

살펴볼게요 총 3가지의 과정이 있거든요

첫 번째 과정은 문제가 생긴 노드를 기준으로 그 노드의

좌우 형제에 대해서 그 형제 중에 키의 수가 여유가 있는 형제의 지원을

받습니다 그래서 지금 같은 경우에는 왼쪽 오른쪽 모두 이렇게 두 개씩

가지고 있기 때문에 최소한의 키스보다 많이 가지고 있으니까 여유가 있는

거잖아요 그러면은이 키를 형제로부터 빌려 오는 거예요 그러면이 문제는

자연스럽게 해결할 수가 있습니다 하지만 만약에

양쪽에 있는 형제가 모두 여유가 없다면 그래서 이렇게 1번이

불가능하면 그때는 부모의 지원을 받고요 그래서 이렇게 부모로부터

도움을 받습니다 그렇게 도움을 받으면서 또 동시에

형제와 합쳐야 돼요 그렇게 했을 때 완전히 해결이 되면 다행인데 그게

아니라 2번을 이렇게 수행한 뒤에 부모에서도 문제가 생겼다면 그러니까

부모에서 만약에이 조건을 위반을 하게 됐다면 그때는이 위치에서 다시 한번

또 재조정을 시작을 해 줘야 됩니다 자 그러면 지금까지 이렇게 간략하게

설명을 드렸는데요 이렇게 재조정하는 과정을 조금 더 자세히 예제와 함께

살펴보도록 하겠습니다 그래서 이제부터는

리프 노드에서 삭제한 후에 최소한의 키스보다

노드에 있는 키수가 적어졌다면 이때 어떻게 해결할 수 있는지 그것을

살펴볼 텐데요 그 첫 번째 방법은 t의 수가 여유있는 형제의 도움을

받는 거예요 그러면이 형제라는 것은 같은 부모를

둔게 형제인 건데 바로 옆에 있는 나보다 작은 값을 가지는 형제를

동생이라고 부르고 나보다 값이 큰 값을 가지는 바로 옆에 있는 형제를

형이라고 부른다면 아무래도 형한테 도움을 바로 요청하는 것보다는

동생한테 도움을 먼저 요청하는게 잔소리도 좀 더 적게 듣고

신적인 부담이 좀 덜 하겠죠 그래서 일단 왼쪽에 있는

동생한테 먼저 도움을 요청을 합니다 그런데 지금 보시면은

동생이 여유가 있어요 최소한의 키의 수는 한 개라고 했는데

동생이 지금 두 개를 들고 있기 때문에

동생이여 있어서 그러면 동생으로부터 힐을 하나 받으면 될 것 같습니다

그런데 동생으로부터 키를 받을 때 예를

들어서 바로 이렇게 옮겨서 여기다가 2를 넣으면 안 되겠죠 왜냐면 이런

식으로 해버리면 3을 기준으로 3의 오른쪽 서브 트리는 3보다 큰 값을

가져야 되는데 3보다 작은 값이 존재하게 되니까 이런 식으로 바로

넘기면 안 되고요 그러면 어떻게 해야 되냐면 일단이 빅토리에 속성을 보면

얘는 어떤 식으로 정렬이 되어 있냐면 그 순서가 이런 식으로이 순서대로

정렬이 되어 있다는 것을 우리가 알 수 있습니다 이게 비트리의 특징인

거죠 그러면이 특징을 깨지 않으면서도 동생으로부터 키를 받고 싶다 그 말은

결국이 정렬된 순서가 그대로 유지가 돼야 되면서 키를 옮겨야 된다는

말이기 때문에 그렇게 하려면 부모로부터 받는 것이

필요합니다 그래서 3을 이쪽으로 내려주고 2를 이쪽으로 올려주면

그러면 얘는이 정렬된 순서가 여전히 유지가 되면서도 여기 비어 있는

노드의 키를 하나 가지고 올 수가 있는 거예요 그래서

이제 이렇게 동생이랑 얘기가 해 가지고 부모님한테 가서 부모님한테

사정을 설명을 하고 그래서 부모님이 그 얘기를 듣고 오케이 그럼 그렇게

하겠다 해가지고 일단 3을 이쪽으로 옮깁니다 그래서 삼이이 자리에

들어오고 이제 동생이 가지고 있던 일을 부모님한테 드리는 거죠 그래서

최종적으로 이런 형태가 됐고 그러면 지금이 세 개의 노드의 변화가

생겼는데 변화가 생기고 나서 보니까이 조건을

만족하게 됐잖아요 그러면 이걸로

5에 대한 삭제는 완료가 되는 겁니다 이번에는 3을

삭제를 해보도록 하겠습니다 그러면 루트 노드에서 시작을 하죠

그런데 루트 노드의 3은 없지만 15가 있어요 그러면 35보다 작기

때문에 또 왼쪽 서브 트리로 빠지겠죠 그 다음에 여기서 또 3을 찾아야

되는데 일단 첫 번째 값을 확인을 해봤더니 얘는 3보다 작아요 그러면은

이번에는 얘 옆에 있는 입각이 값과 또 비교를

했는데 얘는 3보다 큽니다

그러면 결국 3은이 두 개 사이로 가야 되니까 이쪽으로 내려와요 여기서

이제 3을 찾았습니다 그러면 이제 얘를 삭제를 해주면

되는데 문제는 이렇게 삭제를 해주고 나면이

노드에는 아무런 키가 아무런 데이터가 없게 되는 거예요 그러면 결국 또이

조건 위반을 하게 돼서 얘가 이제 문제가 되는 겁니다 그러면

이제 또 같은 방식으로 해결을 해 줘야 되잖아요 그래서 일단 먼저

형제들에게 도움을 요청을 해요 그런데 형제 중에서도 만만한 동생한테 먼저

도움을 요청을 하는데 문제는 지금 동생도 키예수가 한

개라서 그러면 이제는 어쩔 수 없이 이제

형한테 얘기를 해서 형에게 도움을 요청을 해요 그런데 형은 보시면

이렇게 키가 여유가 있잖아요 그래서 이제 형의 도움을 받기로 결정을

했어요 그러면 이제 형이 가지고 있던 키 중에 하나를 내 쪽으로 이렇게

옮겨야 되는데 그러면 결국 얘 같은 경우에도 키를

옮긴 뒤에도이 순서이 정렬된 순서가 그대로 유지될 수 있도록 만들어 주면

되는 거기 때문에 그렇게 해주려면 부모님이 가지고 있는

키 중에 예를 나에게 내리고 그 자리에 형이 가지고 있는 키 중에

바로 익히이 키를 부모님께 드려서이 빈자리를 메꿀 수 있도록 해주면 바꾼

후에도 계속해서 비트리의 특성을 만족시킬 수가 있는 겁니다 그래서

일단 7을 여기로 내리면이 자리에 7이 들어오고 이제 팔을 여기로

올려서 이렇게 자리를 메꿔주고 그 다음에 얘를 이쪽으로 한 칸 땡겨서

이런 형태로 만들어주면 그러면 이제는 변경이 있었던이 세

개의 노드가 모두이 조건을 만족을 하기 때문에 이제 3에 대한 삭제는

완료가 되는 겁니다 그래서 지금까지 이렇게 살펴봤던이 동작 방식을

글로 설명하면 어떻게 되냐면 이렇게 설명할 수 있습니다 그래서 삭제가 된

후에 최소 키보다 노드에 있는 키수가 적어졌다면 1차적으로는 형제들의

지원을 받을 수 있는지를 확인을 하는 거고요

형제 중에서도 동생한테 먼저 확인을 하고

동생이 있으면 동생으로부터 지원을 받아서 내 쪽으로 키를 하나 옮기면

되는데 바로 옮기지는 못하고 왜냐하면 비트리의 특성을 유지를 해야 되니까

바로 옮기지는 못하고 대신에 동생이 가장 큰 키를 부모님께 드리고 그

다음에 부모님이 가지고 있던 그 키를 나의 가장 왼쪽에 두는 거죠 그런데

그게 아니라 동생은 여유가 없었는데 형은 여유가 있었다면 그럼 형한테

빌려서 비슷한 과정을 그렇게 수행을 해주면 되는 겁니다 자 그러면 또

다른 예를 살펴볼게요 이번에는 7을 삭제를 해보겠습니다

그러면 먼저 t를 조회를 해야 되는데 이제는 어떤 식으로 비트리에서 조회가

에너지를 다들 아실 거기 때문에 조회는 빠르게 바로바로 찾아보도록

하겠습니다 그래서 루트 노드부터 시작해서 조회를 주주주 했더니이

위치에 칠이 있다라는 것을 확인했어요 그래서 얘를 삭제를 해줍니다

그런데 삭제를 해주고 나서 보니까 이제 더 이상이 노드에는 아무런

데이터가 없게 됐습니다 그 말인즉슨 이제이 조건을 위반을 하게 된 거죠

그래서 이제이 노드를 문제 해결을 해줘야 되는데요 그런데 여기서 이제

또 다른 문제가 생겼어요 어떤 문제냐면

좌우 형제들을 확인을 해봤는데 동생도 형도 모두 여유가 없는 겁니다

그래서 이렇게 동생으로부터도 형으로부터도 그 어떤

키도 빌릴 수가 없는 상황이에요 그러면 지금이 상황은 1번 방법으로는

더 이상 통하지가 않는 상황인 거잖아요

그러면 이제 2번 방법으로 넘어가야 되는 거예요 이번 방법은 뭐냐면

지금처럼 이렇게 형제의 지원이 불가능한 상황일 때 부모의 지원을

받고 형제와 합치도록 하는 방법입니다

그래서 지금 더 이상 동생으로부터도 형으로부터도 지원을 받지 못하니까

부모님한테 갔어요 부모님한테 가서 죄송하다고 하면서 사정 설명을

했습니다 그러니까 부모님께서 오케이 그러면

일단 내가 지원을 해 줄 건데 너도 지금까지 헤프게 살았으니까 일단

형이던 동생이든 한 명이랑 합쳐라 그렇게 부모님께서 말씀을 하신 겁니다

그러면 얘 입장에서는 누구랑 합치지 고민을

하다가 아무래도 좀 더 만만한 동생이랑 사는게 좋겠다라는 생각이

들어서 아 그러면 나는 동생이랑 합칠게요 이렇게 얘기를 한 겁니다

그러면 이후로는 어떻게 동작을 하냐면 얘와 얘 사이에 있는이 부모의 익히이

키를 일단 동생에게 옮겨줍니다 합치는 경우에는 일단 왼쪽으로 옮긴다고

생각을 하시면 될 거예요 왼쪽으로 옮기고 왼쪽으로 합친다

그렇게 생각을 하시면 됩니다 그래서 일단 부모님이 가지고 있는이 일을

이쪽으로 옮겨요 그래서이가이 자리로 왔습니다 그 다음에

얘가 가지고 있는 값도 이쪽으로 합쳐야 되거든요

그런데 지금 얘는 아무것도 가지고 있는 값이 없으니까 지금은 따로

합칠게 없어요 그래서 어쨌든 이렇게 합친 뒤에

얘는 이제 날려줍니다 그러면 이제 이런 형태가 되는 거죠

그리고 나서 이제 부모 입장에서는요 한 칸에 비웠으니까

팔을 이쪽으로 땡겨 주는게 좋겠죠 얘를 이렇게 땡길 때이 오른팔이

오른쪽 잔여 노드를 가르치는이 포 같이 이쪽으로

옮겨지게 될 겁니다 그래서 이런 식으로 조정이 됐고요 그렇게 하고

나서 보니까이 두 개의 노드가 이제는이 조건을 만족을 하기 때문에

실에 대한 삭제는 이제 완료가 되는 거예요 그래서 이렇게 형제 지원이

불가능하면 부모님의 지원을 받고 또 형제와 합쳐지게 되는데요 이렇게

형제와 합쳐지면서 노드 하나가 사라지게 되는 겁니다

어떻게 보면은 지금이 과정은 일부 영상에서 우리가 봤었던

데이터를 삽입을 할 때 승진을 하는 과정을 거꾸로 한 것과 비슷하다고 볼

수 있겠죠 그러면 또 다른 예를 하나

들어보겠습니다 2를 삭제를 할 거예요 그러면 일단 2를 조회를 해야 되는데

루트 노드부터 시작해서 2를 찾았더니 2가 여기에 있는 것을 확인했어요

얘도 지금 리프 노드에 있습니다 그래서 얘를 삭제를 하면 이렇게

되고요 얘는 지금이 조건을 만족하기 때문에

이에 대한 삭제는 이렇게 완료가 되는 겁니다 그 다음에 1을 삭제를 해

볼게요 다시 루트 노드에서부터 쪼르륵 조회를 해서 여기에 있는 것을

확인했어요 그럼 이제 얘를 삭제를 해줬는데

문제는 이렇게 삭제를 해주고 나서 보니까이 노드에 아무런 데이터가

없어서 이 조건을 다시 위반을 하게 된

거예요 그러면 얘가 일단은 1번부터 수행을 해야

되겠죠 그래서 동생이나 형한테 가서

여유가 있는지를 물어봐야 되는데 얘는 지금 동생은 없어요 동생은

없으니까 형한테 가서 형한테 물어보는 겁니다

그런데 형도 지금 여유가 없어요 그러면

형으로부터도 아무런 도움을 받을 수가 없기 때문에 이제는 부모님한테 가서

솔직하게 얘기를 해야 됩니다 그래서 부모님한테 얘기를 했더니 부모님께서

내가 도와줄게 대신에 너희 둘이 합쳐 또 이렇게 말한 겁니다 그러면 합칠

때는 항상 왼쪽으로 합친다고 했잖아요 그래서 부모님께서도 이제 일단 이렇게

지원을 해 줄 거라서 부모님이 가지고 있는 팔을 왼쪽에 이렇게 옮겨줍니다

참고로 이때 이렇게 옮겨주는 키 있잖아요 부모님이 지원을 해주는이

키는 얘와 얘 사이에 있는 키 그러니까

합치려는 형제 사이에 있는이 키를 지원을 해주는 겁니다

그래야 이제 비트리에 속성을 계속해서 만족할 수가 있는 거죠 그래서 얘를

이쪽으로 옮겨주면 여기에 이제 팔이 들어왔고 그 다음에이 두 개를 합쳐야

되잖아요 합칠 때는 항상 왼쪽으로 합쳐 준다고

했기 때문에 여기에 있는이 구를 이쪽으로 옮겨줍니다 그래서 이제

이렇게 됐고 그러면 얘는 이제 비어있는 노드가 된 거니까

얘를 날려주면 이제 이런 형태가 되는 거죠 자 그러면 이제이 부분은 해결이

됐어요이 조건을 만족을 하기 때문에 이제이 노드는 해결이 된 겁니다

그런데 문제는 여기가 이제 문제가 생긴 거죠 여기에 지금 아무런

데이터가 없기 때문에이 조건을 만족하지 못하게 되면서

얘를 이제 해결해 줘야 되는 그런 문제가 발생을 한 거예요 자 그러면

일단 여기서 멈춰서 지금까지 살펴본 내용을 정리를 해보면 일단 리프

노드에서 삭제한 후에 그 삭제한 노드의 데이터 수가 최소한의 키스보다

적어졌다면 그러면 먼저 형제한테서 도움을 받을 수 있는지 확인을 해보고

그렇게 1번을 확인을 해봤는데 형제들이 모두 여유가 없다 그러면

이제 2번을 수행을 해서 부모의 지원을 받는 대신에 이제 형제와

합쳐야 되는 그런 식으로이 문제를 해결을 하게 되는 겁니다 그래서

지금까지 이렇게 애니메이션을 통해서 설명드린 내용을

글로 설명을 드리면 이런 식으로 설명을 드릴 수가 있고요 이해를 뭐

따로 자세히 설명을 하진 않겠습니다 대신에 이것을 기억을 해주시면

좋겠어요 합칠 때는 왼쪽으로 합친다 그것을 기억을 해 주시면 좋을 것

같습니다 자 그래서 이렇게 부모의 지원을 받아서 형제와 합쳤는데 문제는

그렇게 합쳐서 해결이 될 수도 있지만 부모님이 지원을 해준 뒤에 이제는

부모님이 문제가 생기는 경우도 발생할 수가 있잖아요

그러면이 경우에는 이제 3번으로 가서 3번에 대한 매뉴얼을 따라주면 되는

겁니다 그러면이 3번에 대한 매뉴얼은 뭐냐

이제이 상황에 맞게 대응을 하는 건데요 얘도 바로 예제를 통해서

살펴보도록 하겠습니다 지금이 상황을 해결해야 되는 건데

얘는 지금 이렇게 형제가 있기 때문에 다시 1번부터 시작을 하면 되는

거예요 자 그러면 보시면 일단 형제한테 도움을 요청을 해야 되는데

동생은 없고 형이 있으니까 형한테 가가지고

형 좀 여유 좀 있어 이렇게 물어보는 겁니다

그런데 슬프게도 형이 여유가 없어요 그러면 얘가 이제 터덜터덜 걸음을

걸으면서 부모님한테 가는 거죠 그래서 부모님한테 사실대로 다 얘기를 하고

그러면 이제 부모님께서 내가 도와줄게 대신에 너네 둘이 합쳐 또 이렇게

얘기를 하시는 거죠 그러면 합칠 때는 항상 왼쪽으로 합친다고

했으니까 먼저 부모님의 지원을 받아야 되는데

합치려는 두 형제 사이에 있는이 키를 지원을 해준다고 했죠

왼쪽으로 합치니까 이쪽으로 지원을 해주는 겁니다 그래서이 자리에 이제

15가 들어오게 되고요 그 다음에 얘를 합쳐야 돼요 그러면

30을 일단 이쪽으로 옮겨줍니다 그렇게 옮겨 주면서 당연히

얘네들도이 포인터들도 같이 옮겨 줘야 되겠죠 그래서 이런 식으로 이런

형태로 옮겨 주게 되면 이제는 이런 모습이 됩니다 이렇게 옮겨주고 나서는

이제는 얘는 비어있는 노드니까 얘를 삭제를 해줘요 그러면 이제이 노드를

살펴보면 얘는 이제이 조건을 만족을 하게 됐죠

최소한의 키스보다 더 가지고 있으니까이 조건을 만족을 하게 되면서

얘는 이제 해결이 됐어요 그런데 문제는 이제이 부분입니다이

노드가 아무런 데이터를 가지고 있지 않기 때문에 이제 예를 해결을 해

줘야 돼요 그런데 얘를 해결해 주는 방법은 너무나도 쉽죠

얘가 루트 노드고 여기에 아무런 데이터가 없으니까

얘를 그냥 바로 삭제를 해주면 되는 겁니다 그래서 이렇게 삭제가 됐고

이제 얘가 루트 노드가 되는 거예요 그래서 지금까지 살펴봤던이 과정을

글로 설명을 드리면이 3번 과정은 이렇게

동작을 하게 되는 겁니다 보시면 문제가 생긴 부모노드가 루트 노드가

하면 사실 그 위치에서부터 1번부터 재조정을 시작을 하면 되고요 부모가

루트 노드이고 비어 있다면 그렇다면 그때는 그 부문 노드를 삭제를 하고

그 다음에 직전에 합쳤던 그 노드는 루트 노드가 되도록 그렇게 만들어주면

되는 겁니다 여기서 부모가 루트 노드일 때 비어 있지 않을 수도

있거든요 지금 우리 예전에 3차 B 트리어 가지고

루트 노드가 바로 비어 있게 된 건데 만약에 오차 비트리라면 루트 노드인데

비어 있지는 않을 수도 있어요 그런데이 조건 자체는

루트 노드에서는 제외가 되는 조건이기 때문에

루트 노드에서는 각 노드의 최소 키스보다 키의 수가

적어줘도 그래도 걔는 괜찮거든요 그래서 그 경우에는 그냥 그대로

상황을 종료하고 다음 단계로 넘어가면 되는 겁니다 자 그래서 지금까지

비트리에서 데이터를 어떻게 삭제할 수 있는지를 살펴봤어요

간단하게 요약하면 리프 노드에서 데이터를 삭제를 하고

그렇게 삭제를 하고 난 뒤에 최소한의 그 조건을 만족하지 못하게 됐다면

그렇다면 그때는 재조정을 해준다 그렇게 요약을 할 수 있을 것 같고요

그런데 이제 여기서 한 가지 이슈가 있습니다

삭제는 리프 노드에서만 발생하는 것이 아닌데

즉 인터널 노드에서도 데이터 삭제가

발생할 수 있는데 그러면이 경우에는 어떻게 해야 되냐

이게 이제 궁금할 수가 있는데요 바로 핵심을 얘기를 하면 만약에 인턴을

노드에 있는 데이터를 삭제를 해야 된다면 이때는 어떻게 동작을 하냐

이때는 리프 노드에 있는 데이터와 삭제하려는 그 데이터를 위치를 바꿔

준 뒤에 그래서 리프 노드로 옮겨 준 뒤에 그 위치에서 삭제를 하면 돼요

그러면 이제 리프 노드에서 삭제를 하는 거니까 바로 앞에서 살펴봤던 그

과정을 쭉 따라가면 되겠죠 그래서 예를 들어서 지금 이렇게 3차

비트리가 있다고 해볼게요 그리고 이제 15를 삭제를 할 겁니다 그래서

15를 찾으면 바로이 루트 노드에 있네요 그러면 얘를 삭제를 해줘야

되는데 얘가 지금 인턴을 노드에 있는 거잖아요

그러면 이때 15를 삭제를 해주려면 여기 이렇게 리프 노드에 있는

데이터들 중에 하나랑 위치를 바꿔서이 15를 리프 노드로 옮긴 뒤에 이제

그 위치에서 삭제를 해주면 되는 겁니다

그러면 이제 여기서 하나 중요한 이슈가 떠오르죠 그게 뭐냐면이 리프

노드에 있는 데이터 나중에 어떤 데이터와 위치를 바꿔 줄 것인가 이게

이제 중요한 이슈로 떠오르게 되는 겁니다 만약에

리프 노드에 있는 아무런 데이터나 막 바꾸면 어떻게 될까요 예를 들어서

팔과 15를 바꿔줘 볼게요 그러면은 15는 이제이 자리에 오고

팔이 이제이 자리에 올 건데 그런데 이렇게 하면 안 되는게

왜냐하면 팔이 만약에이 자리에 오게 되면

팔의 왼쪽 서브 트리는 8보다 작은 값만 가지고 있어야 되는데 지금 왼쪽

서브 트리에 9가 있잖아요 9는 8보다 크기 때문에

팔이이 자리에 오면은 이제이 비트리의 특성을 깨뜨리게 돼서 이렇게 바꾸면

안 되는 거예요 그러면 어떤 데이터가 바꿔 줘야 되냐

결론부터 얘기하면 삭제하려는 데이터의 선임자나 혹은

후임자와 그 위치를 바꿔주면 됩니다 여기서이 선임자는 영어로는

프레드세스라고 해서 이틀이에서 나보다 작은 데이터들 중에 가장 큰 데이터를

의미를 하고요 그 다음에 후임자는 영어로나 석세스라고도 하는데이

트리에서 나보다 큰 데이터들 중에 가장 작은 데이터를 의미를 합니다

그래서 예를 들어서 15의 선임자는 15보다 작은 값들 중에 가장 큰

값을 찾으면 되는 거니까 9가 15의 선임자가 되는 겁니다

이해가 되시죠 그러면 인터널 노드에 있는 데이터를 삭제를

할 때 왜 그 삭제하려는 데이터에 선임 전화 혹은 후임자와 그 위치를

바꿔 주면 되냐 예를 들어서이 15의 선임자인 9와 그 위치를 바꿔 준다고

해보면 그러면 이제이 자리에 9가 오고이

자리에 15가 올 거잖아요 그러면 여기서 15가 삭제는 될

거니까 15는 제외하고 생각을 해보면 여기에 올라오니 구를 기준으로

9의 왼쪽 서브 트리는 9보다 작은 값들을 가지고 있고 그 다음에이 구의

오른쪽 서브 트리는 9보다 큰 값을 가지고 있기 때문에

결국이 빅토리의 특성을 그대로 만족시킬 수 있기 때문에 그런

이유에서 삭제하려는 데이터에 선임자 혹은

후임자와 그 위치를 바꿔 줘야 되는 겁니다 그래서 지금까지

인터널 노드에서 데이터를 삭제를 할 때 그 삭제하려는 데이터의 선임자

혹은 후임자의 위치를 바꿔주면 얘는 비트리에 속성을 깨지 않을 수

있다라는 것을 살펴봤잖아요 그러면 이제 하나만 더 확인 하면

되는데 그게 뭐냐면 삭제하려는 데이터에이 선임자는

후임자가 항상 리프 노드에 있는가 이것만 이제 확인을 하면 되는 겁니다

그래서 이제 그것을 간단하게 증명을 해볼게요 자 어차피

선임자나 후임자나 둘 다 비슷하기 때문에 선임자를 예로 들어서 증명을

해보도록 하겠습니다 자 여기이 30이라는 데이터가 있어요 그러면은

30의 선임자를 찾으려면 결국 이틀이에서

30보다 작은 값들 중에 가장 큰 값을 찾으면 되는 거잖아요

그런데 30보다 작은 값들은이 30의 왼쪽 서브 트리로 가도 만날 수가

있고 부모로 가도 만날 수가 있고 그 부모의 또 왼쪽 서브 트리로 가도

만날 수가 있습니다 그러면

실제로이 30의 선임자는 어디에 있을까 생각을 해봤을 때

조금만 생각을 해보면 그 왼쪽 천연 노드로 가는 것이 선임자를 찾으러

가는 길이라는 것을 알 수 있습니다 왜냐하면이 부모노드 입장에서 생각을

해보면 얘를 기준으로

얘의 오른쪽 서브 트리는 얘보다 더 큰 값들을 가지고 있기 때문에 그

말은 즉 얘보다도 얘네들 이쪽에 있는 서브 트리가 더

값이 크다는 얘기인 거잖아요 그렇기 때문에

얘의 선임자를 찾으려면 부모 쪽으로는 갈 필요가 없고

왼쪽 서브트리로 가면 되는 겁니다 그래서 지금 보시는 것처럼 이렇게

왼쪽 서브 트리로 왔으면이 왼쪽 서브 트리 중에서 가장 큰 값을 찾으면

되는 거잖아요 그런데 여기서는 이미 정렬이 되어

있으니까 가장 오른쪽에 있는 값을 선택을 하면 되는데

얘가 지금은 리프 노드니까이 값이 30의 선임자가 되는 거고 만약에

얘가 리프 노드가 아니다 즉 이해가 인터널 노드다 그러면은 비트리의

특성상 가장 오른쪽에 있는이 키를 기준으로 또 좌우에 자녀 노드가 있을

겁니다 그러면 가장 큰 값을 찾으러 가야

되기 때문에 얘를 기준으로 얘의 오른쪽에 있는

잔여 모드로 또 내려가는 거예요 그런 식으로 더 이상 오른쪽으로 갈 수

없을 때까지 계속 내려가는데

그런데 여기서 중요한 것은 뭐냐면 더 이상 오른쪽으로 갈 수 없게 됐을 때

그러면 그때 그 노드는 바로 리프 노드가 된다는 거죠 왜냐하면

피트리의 특성상 이런 식의 구조가 나올 수가 없거든요

즉 가장 오른쪽으로 계속 왔는데 그래서 여기까지 왔는데 여기서 더

이상 오른쪽은 갈 수 없을 때의 왼쪽 잔여 노드는 가지는 이런 경우는 있을

수가 없는 거죠 왜냐하면 키를 기준으로

잔여 노드에게 쓰는 그 키보다 반드시 하나가 많아야 되기 때문에

그렇게 되려면 항상 그 키를 기준으로 좌구로 하나씩

잔여 노드를 가져야 되거든요 그래서 지금 보시는 이런 형태 이런 형태의

구조는 가질 수가 없어서 비트리에서 오른쪽으로 계속 하다가 더 이상

오른쪽으로 내려갈 잔여 노드가 없다면 그 노드는 반드시

리프 노드일 거라고 볼 수가 있습니다

그러면 이제 그 리프 노드의 가장 오른쪽에 찾으려는 선임자가 있게 되는

거죠 이해가 되시나요 혹시나이 부분이 바로 이해가 안

되시면 잠시 멈춰서 생각을 해보시면

그러면 더 잘 이해가 되실 수 있을 거라고 생각을 합니다 어쨌든 선임자도

이런 특징을 가지고 있고 후임자 같은 경우에는 선임자의 반대로

생각을 하면 되기 때문에 결국 핵심은 뭐냐면 비트리에서

인터널 노드에 있는 데이터를 삭제하려고 한다면 그 데이터의 선임

후임자와 위치를 바꿔주면 되는데 왜냐하면 그렇게 해야 바꿔준 후에도

비트리에 속성을 깨지 않을 수가 있거든요 그래서 그렇게 위치를

바꿔주면 되는데이 선임자는 후임자의 위치는

항상 리프 노드에 있기 때문에 삭제할 데이터와 그 위치를 바꿔주면

최종적으로 그 삭제할 데이터의 위치는 항상 리프 노드에 있게 된다 이게

중요한 포인트가 되는 겁니다 그렇기 때문에 결국 맨 처음에

말씀드렸던 것처럼 비트리에서 삭제는 항상

리프 노드에서 발생하게 된다 이게 이제 성립을 하게 되는 거죠 자

그런데이 영상에서는 선임자와 후임자 중에 선임자와 위치를 바꿔 준다고

하겠습니다 그래서 이제 15 삭제를 다시 해보면

얘의 선임자는 얘보다 작은 값들 중에 가장 큰 가스 찾으면 되는 거니까

일단 예의의 왼쪽 잔여 놓으도록 가서 그래서이 왼쪽 서브 트리에서 가장 큰

값을 이제 찾으면 되는 거죠 그래서이 왼쪽 자녀노드에서 지금 오름차순으로

정렬이 되어 있으니까 가장 오른쪽에 있는 값을 찾고 그 오른쪽이 또 잔여

노드가 있으니까 그 잔여 노드로 가서 또 가장 오른쪽에 있는 값을 있고

그런데 얘가 리프 노드였으니까 이제이 9가 15의 선임자가 되는 거고

그래서 9를 이쪽으로 올리고 10으로 이쪽으로 내려주면 이게 여기에는 9가

오고 여기에는 15가 오게 되는 겁니다

그러면 15를 바로 여기서 삭제를 해주면

얘가 지금 3차 비트리니까 최소한의 기술을 한 개만 가지면 되는 거라서

지금 한계가 있으니까 여전히 만족을 하게 되는 거고 지금

올라온이 구 같은 경우에는이 9를 기준으로

왼쪽 서브 트리에는 9보다 작은 값들이 있고 오른쪽 서브 트리에는

9보다 큰 값이 있기 때문에 지금이 상태는 비트리를 만족하고 있는 상태다

그렇게 볼 수가 있는 겁니다 자 그래서 지금까지의 비틀이 데이터

삭제를 요약하면 삭제는 항상 리프 노드에서 발생한다

그래서 만약에 인터널 노드에 있는 데이터를 삭제하려고 하는 경우에는 그

삭제할 데이터의 선임자와 위치를 바꿔준 후에 그러면 리프 노드로

이동을 할 거라서 그 리프 노드 위치에서 삭제를 해주면 된다 이것을

방금 설명을 드렸었고요 그렇게 해서 삭제를 해주고 난 뒤에 만약에

최소한의 키스보다 데이터 수가 적어졌다면 그러면 그때는 재조정을

해주면 된다 이때 재조정을 90을 삭제를 해볼게요 그러면 90을

찾아야 되는데 90이 여기 있는 것을 확인했어요 그러면 얘를 삭제를 해주면

95가 한 칸 이쪽으로 당겨오면서 이런 식으로 80 85 95가 되겠죠

그러면 얘는 최소한의 키에게 쓰인 두 개보다 많이 가지고 있기 때문에

이대로 그냥 90에 대한 삭제는 종료를 하면 됩니다이어서 75를

삭제를 해보도록 할게요 그러면 75를 찾아야 되는데

루트 노드에서부터 시작해서 찾아보니까 여기에 75가 있어요 그러면 얘를

이제 삭제를 하면 되는데 문제는 얘가 지금 인터널 노드잖아요

그러면은 리프 노드로 옮겨 줘야 됩니다 그래서 먼저 얘의 선임자를

찾아야 되는데요 왼쪽 서브 트리로 가면 된다고

했잖아요 그래서 왼쪽 서브 트립 75를 기준으로 왼쪽 서브트리로

내려가서 그 중에서 가장 큰 가스 찾으면 됩니다 그러면 이렇게

오름차순으로 정렬되어 있으니까 가장 큰 값은 70이 되는 거겠죠 그래서

이렇게 70을 75의 선임자로 찾았고 이제이 두 개를 바꿔주면 됩니다

그래서이 자리에는 70이 왔고이 자리에는 75가 왔어요

그러면 이제이 75를 삭제를 해주면 되는데 이렇게

해주고 나서 보니까이 노드에 있는 데이터의 개수가 한계가 됐어요 그러면

최소한의 키스보다 작아진 거잖아요 이제 그래서이 문제를 해결해 줘야

되는 겁니다 그런데 해결해 주는 방법은 일단은

형제들에게 먼저 도움을 요청한다고 했는데 좀 더 마음 편한 동생한테

먼저 요청을 해보는데 동생이 이미 최소한의 개수만 가지고

있어요 그러니까 여유가 없는 겁니다 그러면은 이제는 형한테 가는 거죠

형한테 이제 도움을 요청을 했는데 형은 지금 여유가 있어요

그러면 이제이 형이 얘한테 키를 건네주면 되는 거예요 그런데 바로

건네주면 안 된다고 했잖아요 왜냐하면이 정렬 순서가이 세 개의

노드에 대해서 한정해서 살펴보면 지금 이런 순서로 저장이 되어 있는

거잖아요 그렇기 때문에이 순서를 유지를 시켜

줘야 되거든요 그래서 그 순서를 유지를 시켜 주려면 나와 형 사이에

있는이 값을 일단 나에게 내려줍니다 그 다음에 형이 가지고 있는 값들

중에 가장 작은 값 그래야 순서가 유지가 되겠죠 가장 작은 값을이

부모님의이 자리로 올려주는 거예요 그래서

먼저이 70을이 자리로 내리면 이제 내가 70을 가지 그 다음에이 80을

부모님한테 올려드리면 이제 82 자리에 들어오게 됐고 그 다음에 여기

있는 얘네들은 한 칸씩 이쪽으로 당겨서 이런 형태로 만들어 주게 되면

이제 숫자적으로 변경했었던이 누드들 모두이 최소 조건을 만족을 하기

때문에이 상태 그대로 75에 대한 삭제는 완료를 시켜주면 됩니다이어서

40으로 삭제를 해보도록 하겠습니다 그러면 일단 45를 찾아야 되는데요이

루트 노드에서 출발을 했는데 여기서 바로 찾았어요 그러면 이제 얘를

여기서 바로 삭제를 해주면 되냐 안 되죠 얘가 지금 인터널 노드에 있기

때문에 일단 리프 노드로 옮겨 줘야 됩니다

그러면 먼저이 45의 선임자를 찾아야 되는

거잖아요이 선임자는 45를 기준으로 왼쪽 서브틀이 있기 때문에 일단이

왼쪽 잔여 노드로 이동을 합니다 이제이 서브 트리에서 가장 큰 값을

찾으면 되는 거고 그러면 먼저이 노드에서

얘네들이 정렬이 되어 있으니까 가장 오른쪽에 있는 값을 찾아요

그런데이 가장 오른쪽에 있는 값이 오른쪽 잔여 노드를 가지고 있기

때문에 이제는이 오른쪽 잔여 노드로 갑니다

그러면이 노드에서 다시 한번 가장 큰 값 그러니까 가장 오른쪽에 있는 값을

이렇게 찾아요 그런데 얘는 리프 노드니까

결국은이 42 45의 선임자가 되는 거예요 이제 그러면이 두 개의 위치를

바꿔주면 되겠죠 그래서이 자리에는 40이 왔고이 자리에는 45가

왔습니다 이제이 45를 삭제를 했어요 그렇게 삭제를 하고 보니까이 노드에

있는 데이터의 수가 최소 키수보다 작아졌잖아요

그러면 이제이 노드를 해결을 해줘야 되는 겁니다 그래서 해결을 해주기

위해서 제일 먼저 해야 되는 것은 먼저 형제들에게 도움을 요청을 해야

되는데 왼쪽에 있는 동생한테 가서 요청을

했더니 동생이 이미 최소한의 키스만 가지고

있어요 그래서 동생에게는 도움을 받을 수가 없습니다

그런데 얘는 오른쪽 형제는 없잖아요 같은 부모를 가지는 오른쪽 형제는

없기 때문에 그러면 1번 방법으로는 해결이 안

돼서 이제 부모님한테 가서 도움을 요청을 해야 되는 겁니다

그래서 부모님한테 갔더니 부모님께서 그래 내가 도와줄게 대신에 이제 너네

둘이 같이 살아 이렇게 말을 하신 거죠 그러면 일단 부모님께 이제

지원을 받아야 되는데 이때 지원을 하는 값은

합쳐지는 두 형제 있는이 값을 지원을 한다고 했잖아요 그래서 먼저 얘를

이쪽으로 내려주면 이제이 자리에 30이 왔구요

합칠 때는 항상 이쪽으로 합쳐 준다고 했으니까 여기에 있는이 35라는 값을

이쪽으로 옮겨줍니다 그래서 여기에 35가 들어왔어요 그럼 이제이 노드는

비어 있기 때문에 얘는 삭제를 해주면 되죠 그래서 이제

이런 형태가 됐고 얘는 이제이 최소한의 조건을 만족하게

돼서이 상태로 그대로 두면 되는데요 문제는 이제이 부분이에요이 부문

노드가 지원을 해주고 나서 본인이 가지고 있는 데이터의 수가이

최소한의 갯수보다 적어지게 된 겁니다 그러면 이제 얘를 또 해결해 줘야

되는데 사실 1번부터 반복을 하는 거예요 그래서 얘가 이제 또 형제한테

갑니다 얘는 동생이 없으니까 바로 형한테

도움을 요청하러 가는 거예요 그런데 형도 보니까 상황이 녹록치가

않아요 여유가 없습니다 그래서 부모님한테 갔어요 그래서 부모님께서

알겠다 이제 내가 도와줄게 대신에 너네 둘이 합쳐서 사러 이렇게 말씀을

하셨고 합칠 때는 항상 왼쪽으로 합친다고

했죠 그래서 먼저 부모님한테이 값을 지원을

받습니다 그 다음에 여기에 있는 데이터들을 합쳐야 되니까 개인적으로

옮겨주면 이제 여기에 60과 80이 들어오게 됩니다

그러면서 여기에 있던 값들이 이쪽으로 옮긴 거니까이 포인터들도 같이 옮겨

줘야 되겠죠 그래서 얘네들도 이런 형태로

요렇게 이런 식으로 옮겨 줘야 되고

그렇게 옮겨주면 보시는 것처럼 이런 형태가 됩니다 그러면 이제이 노드는

비워졌으니까 얘를 삭제를 하고요

삭제를 하고 나서 보니까이 부분은 이제 해결이 됐어요이 조건을 만족하기

때문에이 노드는 해결이 됐는데 문제는 이노드죠 얘는 루트 노드인데 아무런

데이터가 없기 때문에 얘 또한 정리를 해줘야 됩니다 그래서

얘를 삭제를 해주면 이제부터는이 친구가 루트 노드가 되는 겁니다

마지막으로 하나만 더 해볼까요 60을 삭제를 해보겠습니다 그러면

60을 찾아야 되는데 여기 60을 찾았어요 그러면 얘를 바로 삭제를

해주면 되냐 안 되죠 얘가 인터널 노드니까 일단 리프 노드로 옮겨 줘야

됩니다 그러면이 친구의 선임자를 찾아야 되는데 선임자는

얘의 왼쪽 서브 트리 중에서 찾아야 되는 거잖아요 그래서이 왼쪽 서브

트리로 이동을 합니다 지금 그림 때문에 속으면 안 돼요

얘가 오른쪽으로 화살표 되어 있다라고 해서

얘를 오른쪽 서버트리라고 생각하면 안 되는 겁니다

얘를 기준으로 왼쪽 서버트립니다 그래서이 왼쪽 서브

트리로 와서 여기서 가장 큰 값을 찾아요

55조 그런데 얘가 리프 노드니까 그러면이 60의 선임자는 이제이

55가 되는 거고 60과 55를 위치를 바꿔주면 이제이

자리에는 55가 오고이 자리에는 60이 왔습니다

그러면 여기서 이제 삭제를 해주면 되는데 이렇게 삭제를 해줬더니이

노드에 있는 데이터의 수가 최소 키스보다 작아졌어요 그러면 이제이

문제를 해결을 해야 되죠 그러면 첫 번째 방법은 형제에게 도움을 요청을

하는 건데 좀 더 마음이 편하고 친근한 동생에게 먼저 요청을 하러

갑니다 그런데 동생이 여유가 있기 때문에

동생이 도와주기로 했어요 그러면 이제 이때 도와줄 때 어떻게 하는지 이제는

잘 아시죠이 순서를 보장을 하면서 키를 옮겨 줘야 되기 때문에 일단

50을 이쪽으로 한 칸 옮기고 그 다음에 나와 동생 사이에 있는이 값을

이제 이쪽으로 내리고 그 다음에 이제 동생이 가지고 있는 값들 중에 가장

큰 값인 이값을 이쪽으로 올려서 35를이

계곡에 만들어 주면 되는 겁니다 그러면 이렇게 바꿔 준 뒤에도 여전히

정렬된 순서대로 데이터가 저장된다는 것을 알 수 있고 그래서 여전히

비트리의 특성을 만족을 하고 있고 그 다음에 데이터의 숫자가 바뀐이 두

개의 노드를 봐도 각각의 노드들이이 조건을 만족을 하고

있기 때문에 그러면 이대로이 60에 대한 삭제는

종료를 하면 되는 겁니다 자 그래서 이제 예제는 모두 끝이났습니다

비트리에서 데이터를 어떻게 삭제를 하는지는 이런 방식에 따라서

진행을 하게 된다 그것을 잘 기억을 해주시면 좋을 것 같아요

끝으로 참고 사항입니다 비트리에서 데이터를 삽입하거나 또 삭제하는

방식은 다른 방식들도 있습니다

그런데 일부 영상에서 그리고 오늘 영상에서 설명드린이 방식이 좀 더

이해하기 쉬운 방법이어서 이렇게 설명을 드리게 됐어요네 오늘 준비한

영상은 여기까지입니다 확실히 레드 블랙 트리도 그렇고

피트리도 그렇고 삽입을 설명할 때보다 삭제를 설명할

때 훨씬 더 어려운 것 같아요 자 아무튼 끝까지 봐주신 모든 분들 정말

최고시고요 저는 또 다음 영상을 준비하러 가보겠습니다

감사합니다