B-Tree 삭제

B-Tree 삭제

 

B-Tree 구현 중 제일 복잡한 부분이다. 우선 함수를 살펴보자.

 

deleteNode(Node N, key x) : Node N에서 key x를 찾는다.

(실제 구현은 root 여부를 확인하기 위해 Tree 구조체도 같이 전달하는 방식으로 구현했다. 특정 key를 삭제했을 때 root가 사라지는지 확인하는 과정이 꼭 필요하다.)

 

key X를 삭제하는 과정은 Tree의 root Node로부터 시작해서 X가 들어있는 노드를 찾는 것으로 시작한다. 삭제하는데 발생가능한 경우는 아래와 같이 크게 세 가지로 나눠볼 수 있다.

 

1.  N이 Leaf Node인 경우

 

  → Node N의 key들에 대하여 for문을 돌며 확인한 뒤, X가 존재하면 삭제한 뒤 True를 return, 없다면 False를 return한다.

2. Node N 안에 key X가 있는 경우

 

  a) key X의 선행 자식 Node Y가 최소 t개의 키를 가진다면, X의 선행키(Predecessor) K를 X와 바꾼 뒤, K를 삭제한다. 이후 아래 노드로 내려가며 X를 삭제한다.

 

ex) 아래 그림에서 key 16을 지우려는 경우이다.

 

 

1. 16의 선행자식 Node Y는 3개의 Key를 가지고 있으므로 t(2)개 이상을 만족한다. 따라서 선행키인 15와 교환한 다.

 

2. key X(16)를 지우러 내려간다.

 

  b) key X의 후행 자식 Node Z가 최소 t개의 키를 가진다면, X의 후행키(Successor) K'과 X를 바꾼 뒤, 아래 노드로 내려가며 X를 삭제한다.

 

  c) key X의 선행 자식 Node Y와, 후행 자식 Node Z 모두 t-1개의 자식을 가진다면, Node Y와 Z를 합치고(merge) X를 삭제한다.

 

 

선행키와 후행키란 ? 

아래 그림의 Tree에서 key = 12를 삭제하려고 한다. 선행키와 후행키는 어떤 값인가?

 

* 선행키(Predecessor) : 특정 Key의 왼쪽 자식 노드를 root로 하는 서브트리(초록색)에서 가장 오른쪽에 있는 값 = 11

* 후행키(Successor) : 특정 Key의 오른쪽 자식 노드를 root로 하는 서브트리(초록색)에서 가장 왼쪽에 있는 값 = 13

 

3. Node N 안에 key X가 없는 경우

 

  계속 X를 찾아 들어가야 하므로, 다음 살펴볼 Node C를 정한다. (Node N의 key 값을 기준으로 비교한 뒤 정한다.) 해당 Child Node가 t-1개의 자식을 가진 경우, 아래와 같은 두가지 경우가 있을 수 있다.

  a) Node C 양 옆의 Node 중 t개 이상의 key를 가진 Node가 있는 경우

      → 하나의 key를 해당 Node에서 빌려온 뒤, 재귀적으로 C로 들어간다.(deleteNode(key x, Node C)) 

          (Node C의 key 개수는 2t-2개가 된다.)   

  b) Node C 양 옆의 Node들이 모두 t-1개의 자식을 가진 경우

      → 양 옆 중 하나의 Node와 병합한 뒤, 재귀적으로 C로 들어간다.(deleteNode(key x, Node C)) 이 때, 두 Node를 가리키는 Child Pointer들 사이에 있는 key는 병합된 Node C로 같이 내려온다. (Node C의 key 개수는 2t-1개가 된다.)

 

※ 참고할 사항 ※

 

* 여기서도 삽입할 때 Split을 해주며 찾아내려간 것과 마찬가지로, 만약 Node N이 t-1개의 자식을 갖고있다면 옆의 Node와 Merge를 하거나 옆 Node에서 Key를 빌려서 충분한 key의 개수를 충족시킨 후 내려간다.