[크래프톤 정글 5기] week04 C언어 주차 여섯번째 날, 이진 검색 트리, B-Tree

이진 탐색 트리(Binary Search Tree, BST)

- 왼쪽 서브트리는 부모 노드보다 작고 오른쪽 서브트리는 부모 노드보다 큰 이진 트리

- BST의 최소값은 “트리의 가장 왼쪽”에 존재한다

- BST의 최대값은 “트리의 가장 오른쪽”에 존재한다

 

이진 탐색 트리의 삽입

- 아무것도 없는 트리라면 그냥 삽입한다.

- 삽입할 노드를 루트 노드부터 하나씩 비교한다. 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 빈 자리를 찾을 때 까지 반복한다.

- 같은 값을 가지는 노드는 없다.

 

이진 탐색 트리의 삭제/검색

- 삭제를 하려면 검색부터 해야 한다.

- 찾을 노드를 기준으로, 루트 노드부터 하나씩 비교한다. 삽입할 때처럼 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 값이 같다면 해당 노드를 찾은 것이다.

- 자식이 없는 노드 삭제

    -> 그냥 삭제하면 된다.

- 자식이 1개인 노드 삭제

    -> 삭제한 후, 삭제된 노드의 부모 노드가 혼자남은 자식을 가리키게 한다.

- 자식이 2개인 노드 삭제

    -> 삭제한 후, 삭제된 노드의 왼쪽 서브트리에서 가장 큰 값(선임자)이 삭제된 노드를 대체 하거나 / 삭제된 노드의 오른쪽 서브트리에서 가장 작은 값(후임자)이 삭제된 노드를 대체한다.

 

B-Tree

- BST와 유사하며, BST에서 차수를 높인 트리

- 차수가 몇이냐에 따라 M차 BTree라고 불린다. 차수는 원하는 대로 늘릴 수 있다.

- 각 노드는 최대 M개의 자식과 M-1 개의 키를 가진다.

- 각 노드의 키는 모두 오름차순으로 정렬된다.

- 키는 자식이 가지는 값의 범위를 정한다.

- 각 노드는 키 + 1 갯수의 자식을 향하는 포인터를 가진다

- 키가 1개일 경우 : 해당 키보다 작은 포인터, 해당 키보다 큰 포인터

- 키가 2개일 경우 : 작은 키보다 작은 포인터, 작은 키와 큰 키의 사이에 있는 포인터, 큰 키보다 큰 포인터

- ex)3차 BTree이고 k1: 10 , k2: 20 일 경우

왼쪽 자식 : 10 미만

가운데 자식 : 10 초과 ~ 20 미만

오른쪽 자식 : 20 초과

 

M : B-Tree가 가질 수 있는 최대 자식 수

M - 1 : B-Tree가 가질 수 있는 최대 키의 수

M/2(올림) : B-Tree가 가져야 하는 최소 자식 수 ( root, leaf 제외 )

M/2(올림) - 1 : B-Tree가 가져야 하는 최소 키의 수 ( root 제외 )

 

B-tree2

- internal 노드의 key의 수가 x개라면, 자녀 노드의 수는 언제나 x+1 개다.

- 노드가 최소 하나의 key는 가지기 때문에, 몇 차 BTree인지 상관없이 internal 노드는 최소 두 개의 자녀는 가진다.

 

B-tree의 삽입

- 추가는 항상 leaf노드에 한다.

- 노드가 넘치면 가운데 key를 기준으로, 좌우 key는 분할하고 가운데 key는 승진한다.

 

B-tree의 삭제

- 합칠 땐 항상 왼쪽으로 합친다. 문제가 생겼을 경우 동생 쪽부터 탐색한다.

- 삽입처럼 삭제도 항상 leaf노드에서 한다

- 삭제 후 최소 key 수보다 적어졌다면 트리를 재조정해야 한다.

1. key의 수가 여유있는 형제의 지원을 받는다

2. 1번이 불가하면 부모의 지원을 받고 형제와 합친다

3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다

 

1번 과정

- 동생에게 지원을 받을 경우, 동생의 가장 큰 key를 부모의 나와 동생 사이에 둔다, 원래 그 자리에 있던 부모의 key는 나의 가장 왼쪽에 둔다

- 형에게 지원을 받을 경우, 형의 가장 작은 key를 부모의 나와 형 사이에 둔다, 원래 그 자리에 있던 부모의 key는 나의 가장 오른쪽에 둔다

 

2번 과정( 동생에게 먼저 가야 한다 )

- 동생이 있을 경우, 동생과 나 사이의 key를 부모에게 받는다, 그 key와 나의 key를 동생에게 합치고 나의 노드를 삭제한다.

- 동생이 없는 경우, 형과 나 사이의 key를 부모에게 받는다. 그 key와 형의 key를 나에게 합치고 형의 노드를 삭제한다

-> 부모꺼 한개 받고 형제끼리 합치기 ( 항상 왼쪽으로 합친다 )

 

3번 과정( 1, 2를 했는데 부모에 문제가 있을 경우 )

- 부모의 형제도 있기 때문에 다시 1번부터 시작해야 한다

- 부모가 root가 아니라면 그 자리에서 다시 1번부터 시작한다

- 부모가 root고 비어있다면 부모를 삭제한다. 직전에 합쳐진 노드가 root가 된다.

 

internal 노드의 데이터 삭제 ( internal 노드 -> 내부 노드(root 또는 leaf가 아닌 노드))

- internal 노드에 있는 데이터를 leaf노드의 데이터와 위치를 바꾼 후 삭제한다

- 삭제하려는 노드의 왼쪽 서브트리의 선임자(가장 오른쪽) 또는 오른쪽 서브트리의 후임자(가장 왼쪽)와 위치를 바꾸면 된다.

- 왼쪽 서브트리의 선임자를 찾으려면 오른쪽으로 들어갈 수 없을 때까지 들어가면 그게 leaf노드고 선임자이다.

- 반대로 오른쪽 서브트리의 후임자를 찾으려면 왼쪽으로 들어갈 수 없을 때까지 들어가면 그게 leaf노드고 후임자이다.

- 최소 1개의 키, 2개의 자식을 갖기 때문에 이 공식이 성립한다.

- 선임자 : 나보다 작은 데이터들 중 가장 큰 데이터

- 후임자 : 나보다 큰 데이터들 중 가장 작은 데이터

- leaf와 자리를 바꾼다는 점이 다르며, 그 외 삭제 로직은 동일하다.

 

 

========================

B트리 공부에 매우 크게 도움을 받은 강의 영상

B트리 개념과 특징, 데이터 삽입

https://www.youtube.com/watch?v=bqkcoSm_rCs

 

B트리 데이터 삭제

https://www.youtube.com/watch?v=H_u28u0usjA

 

영상이 살짝 길긴 한데, 설명을 너무 잘 하셔서 그냥 쭉 보기만 해도 따로 공부할 필요도 없이 이해가 한번에 된다.

여기저기 자료 찾아다니는 것 보단 그냥 이 영상 2개를 보면 효율적으로 빠르게 학습할 수 있다.