크래프톤 정글 6기 TIL - Day 19 | B 트리

오늘은 퀴즈에 B트리가 나온대서 급하게 공부!!

 

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

1. 모든 노드의 왼쪽 서브트리 = 해당 노드의 값보다 작은 값을 가짐
    모든 노드의 오른쪽 서브트리 = 해당 노드의 값보다 큰 값들만 가짐
2. 자녀 노드는 최대 2개까지 가질 수 있다.

 

만약 자녀 노드를 3개 갖고 싶다면!

2개의 키 값을 기준으로 서브트리를 나누고, 기준에 따라 해당 서브트리의 모든 노드는 그 기준에 만족한다.

 

B트리

트리를 가지는 형식이 BST와 유사하면서 최대로 가질 수 있는 자녀 개수를 결정할 수 있다. → BST를 일반화한 Tree 라고도 함.

 

✨ 자녀 노드의 수 늘리기
      1️⃣ 부모 노드에 하나 이상 저장
      2️⃣ 부모 노드의 key들을 오름차순으로 정렬
      3️⃣ 정렬된 순서에 따라 자녀 노드들의 키 값의 범위가 결정됨.

 

B-Tree 주요 Parameter

▶️ internal 노드의 key 수가 x 개라면 자녀 노드의 수는 언제나 x + 1개이다.
▶️ 노드가 최소 하나의 key는 가지기 때문에 몇차 B-tree 인지와 상관없이 internal 노드는 최소 두 개의 자녀를 가진다.
✨ M이 정해지면 root 노드를 제외하고 internal 노드는 최소 [M/2] 개의 자녀도드를 가질 수 있게 된다.

 

B-tree 데이터 삽입

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

2. 노드가 넘치면 가운데( medium ) key를 기준으로 좌우 key들을 분할하고 가운데 key는 승진한다.

 

B-tree의 특징

1. 모든 leaf 노드들은 같은 레벨에 있다. → Balanced Tree

2. 검색 avg/worst case 0(logN)

 

B-tree 데이터 삭제

- 삭제는 항상 leaf 노드에서 발생

- 삭제 후 최소 key수보다 적어졌다면 재조정을 해준다.

1. key수가 여유있는 형제 지원을 받는다.
   1.1 동생(왼쪽 노드)가 여유 있으면
        - 동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 둔다.
        - 원래 그 자리에 있던 key는 나의 가장 왼쪽에 둔다.
  1.2 형(오른쪽 형제)에 여유가 있다면?
        - 형의 가장 작은 key를 부모 노드의 나와 형 사이에 둔다.
        - 원래 그 자리에 있던 key는 나의 가장 오른쪽에 둔다.
2. 형제의 지원이 불가능 하면 , 부모의 지원을 받고 형제와 합친다.
  2.1 동생이 있으면 동생과 나 사이의 key를 부모로부터 받는다.
        - 그 키와 형의 key를 차례대로 나에게 합친다.
        - 형의 노드를 삭제한다.
3. 부모가 지원한 후 부모에게 문제가 있다면 상황에 맞게 대응
  3.1 부모가 루트 노드가 아니라면
       - 그 위치에서부터 다시 1번부터 재조장
  3.2 부모가 root 노드고 비어있다면
       - 부모 노드를 삭제한다.
       - 직전에 합쳐진 노드가 root 노드가 된다.

리프노드에서 키 22를 삭제하는 경우

 

삭제후 재조정 과

Internal 노드 데이터 삭제

- leaf 노드에서 삭제 후 필요하면 재조정

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

내부 노드에서 키 30을 삭제하는 경우

 

정리

- 삭제는 항상 lead 노드에서!

- internal 노드의 경우 선임자와 위치 바꾼 후 삭제

- 삭제 후 최소 key수 보다 적어졌다면 재조정

- 형제지원 → 부모지원 받고 형제 합침 → 부모 도움 후 부모도 문제시 재차 조정