B-트리

B-트리는 자가 균형 탐색 트리로, 각 노드가 두 개 이상의 자식 노드를 가질 수 있다.

속성

n차 B-트리는 다음과 같은 속성을 만족한다:

• 모든 노드는 최대 2n개의 키를 가질 수 있다.
• 루트 노드를 제외한 모든 노드는 최소 n개의 키를 가져야 한다.
• k개의 키를 가진 리프가 아닌 노드는 k+1개의 자식 노드를 가진다.
• 모든 노드의 키는 오름차순으로 정렬되어 있다.
• 리프가 아닌 노드의 두 키 k와 l 사이의 서브트리는 k와 l 사이의 모든 키를 포함한다.
• 모든 리프 노드는 동일한 레벨에 위치한다.

1부터 20까지의 키를 가진 2차 B-트리는 다음과 같은 모습이다:

B-Tree 노드의 코드 표현

class BTreeNode<Key: Comparable, Value> {
  unowned var owner: BTree<Key, Value>
  
  fileprivate var keys = [Key]()
  var children: [BTreeNode]?
  
  ...
}

노드의 주요 구성 요소는 두 개의 배열이다:

• 키를 담는 배열
• 자식 노드를 담는 배열

노드는 또한 자신이 속한 트리에 대한 참조를 가지고 있다.
이 참조는 노드가 트리의 순서를 알아야 하기 때문에 필요하다.

참고: 자식 노드를 담는 배열은 Optional 타입이다. 리프 노드는 자식 노드를 가지지 않기 때문이다.

검색

1. 키 k를 검색할 때는 루트 노드에서 시작한다.
2. 노드의 키 배열을 선형 검색하며, 키 k보다 작지 않은 키 l을 찾거나 배열의 끝에 도달할 때까지 진행한다.
3. 만약 k == l이라면, 키를 찾은 것이다.
4. 만약 k < l이라면:
   • 현재 노드가 리프 노드가 아니라면, l의 왼쪽 자식 노드로 이동한 후 3~5단계를 다시 수행한다.
   • 현재 노드가 리프 노드라면, k는 트리에 존재하지 않는다.
5. 배열의 끝에 도달했다면:
   • 현재 노드가 리프 노드가 아니라면, 노드의 마지막 자식 노드로 이동한 후 3~5단계를 다시 수행한다.
   • 현재 노드가 리프 노드라면, k는 트리에 존재하지 않는다.

value(for:) 메서드는 주어진 키를 검색한다. 트리 안에 키가 존재하면 해당 키와 연결된 값을 반환하고, 그렇지 않으면 nil을 반환한다.

삽입

키는 리프 노드에만 삽입할 수 있다.

1. 삽입하려는 키 k를 검색한다.
2. 키를 찾지 못했고 현재 위치가 리프 노드라면, 키를 삽입할 수 있다.

• 검색 후 현재 위치한 키 l이 k보다 크다면:
  l 앞에 k를 삽입한다.
• 그렇지 않다면:
  l 뒤에 k를 삽입한다.

삽입 후 노드의 키 개수가 올바른 범위에 있는지 확인해야 한다.
노드의 키 개수가 order*2보다 많다면, 노드를 분할해야 한다.

노드 분할

1. 분할하려는 노드의 중간 키를 부모 노드로 이동한다. (부모 노드가 있는 경우)
2. 부모 노드가 없는 경우(루트 노드인 경우), 새로운 루트 노드를 생성하고 중간 키를 삽입한다.
   또한 기존 루트 노드를 새로운 루트 노드의 왼쪽 자식으로 추가한다.
3. 중간 키 이후의 키들(그리고 리프 노드가 아닌 경우 자식 노드들도)을 새로운 노드로 이동시켜 노드를 둘로 나눈다.
4. 이동시킨 키의 오른쪽 자식으로 새로운 노드를 추가한다.

노드를 분할한 후, 부모 노드도 키가 너무 많아질 수 있다. 이 경우 부모 노드도 분할해야 한다.
최악의 경우 분할이 루트 노드까지 이어질 수 있다. 이 경우 트리의 높이가 증가한다.

1차 트리에 삽입하는 과정은 다음과 같다:

코드 설명

insert(_:for:) 메서드는 삽입 작업을 수행한다.
키를 삽입한 후, 재귀 호출이 진행되면서 각 노드는 자식 노드의 키 개수를 확인한다.
만약 어떤 노드가 너무 많은 키를 가지고 있다면, 그 노드의 부모 노드가 split(child:atIndex:) 메서드를 호출한다.

루트 노드는 트리 자체가 확인한다.
삽입 후 루트 노드가 너무 많은 노드를 가지고 있다면, 트리는 splitRoot() 메서드를 호출한다.

키 삭제

키는 리프 노드에서만 삭제할 수 있다.

1. 삭제하려는 키 k를 검색한다.
2. 키를 찾은 경우:
   • 현재 노드가 리프 노드라면:
     키를 삭제한다.
   • 리프 노드가 아니라면:
     키 k를 중위 순회 기준 직전 키 p로 덮어쓴 후, 리프 노드에서 p를 삭제한다.

키를 삭제한 후에는 해당 노드에 충분한 키가 남아 있는지 확인해야 한다.
노드가 트리의 차수보다 적은 수의 키를 가지고 있다면, 다른 노드에서 키를 가져오거나
형제 노드와 병합해야 한다.

키를 자식 노드로 이동하기

문제가 있는 노드가 트리의 차수보다 더 많은 키를 가진 가장 가까운 형제 노드를 가지고 있다면, 이 작업을 수행한다. 그렇지 않다면 해당 노드를 형제 노드 중 하나와 병합한다.

수정하려는 자식 노드 c1이 부모 노드의 자식 배열에서 인덱스 i에 위치한다고 가정하자.

만약 인덱스 i-1에 있는 자식 노드 c2가 트리의 차수보다 더 많은 키를 가지고 있다면:

1. 부모 노드의 인덱스 i-1에 있는 키를 자식 노드 c1의 키 배열 인덱스 0으로 이동한다.
2. c2의 마지막 키를 부모 노드의 키 배열 인덱스 i-1로 이동한다.
3. (c1이 리프 노드가 아닌 경우) c2의 마지막 자식을 c1의 자식 배열 인덱스 0으로 이동한다.

그렇지 않다면:

1. 부모 노드의 인덱스 i에 있는 키를 자식 노드 c1의 키 배열 끝으로 이동한다.
2. c2의 첫 번째 키를 부모 노드의 키 배열 인덱스 i로 이동한다.
3. (c1이 리프 노드가 아닌 경우) c2의 첫 번째 자식을 c1의 자식 배열 끝으로 이동한다.

두 노드 병합하기

부모 노드의 자식 배열에서 인덱스 i에 위치한 자식 노드 c1을 병합하려고 한다고 가정해 보자.

만약 c1이 왼쪽 형제 노드 c2를 가지고 있다면:

1. 부모 노드의 인덱스 i-1에 있는 키를 c2의 키 배열 끝으로 이동한다.
2. c1의 키와 자식 노드(리프 노드가 아닌 경우)를 c2의 키와 자식 배열 끝으로 이동한다.
3. 부모 노드에서 인덱스 i-1에 있는 자식 노드를 제거한다.

반면, c1이 오른쪽 형제 노드 c2만 가지고 있다면:

1. 부모 노드의 인덱스 i에 있는 키를 c2의 키 배열 시작 부분으로 이동한다.
2. c1의 키와 자식 노드(리프 노드가 아닌 경우)를 c2의 키와 자식 배열 시작 부분으로 이동한다.
3. 부모 노드에서 인덱스 i에 있는 자식 노드를 제거한다.

병합 후, 부모 노드에 키가 너무 적게 남을 수 있다.
최악의 경우 병합이 루트 노드까지 올라갈 수 있으며, 이 경우 트리의 높이가 줄어든다.

코드 설명

• remove(_:) 메서드는 주어진 키를 트리에서 제거한다. 키가 삭제된 후, 모든 노드는 자식 노드의 키 개수를 확인한다. 만약 자식 노드의 키 개수가 트리의 차수보다 적다면, fix(childWithTooFewKeys:atIndex:) 메서드를 호출한다.

• fix(childWithTooFewKeys:atIndex:) 메서드는 자식 노드를 어떻게 수정할지 결정한다. 키를 이동시킬지, 아니면 병합할지를 선택한 후, 그에 따라 move(keyAtIndex:to:from:at:) 메서드나 merge(child:atIndex:to:) 메서드를 호출한다.

함께 보기

Wikipedia
GeeksforGeeks

Swift Algorithm Club을 위해 Viktor Szilárd Simkó가 작성함