B Tree 데이터 삭제

* 나무위키의 내용 및

*아래 링크의 유튜브 영상을 보고  본 글은 제 학습의 결과를 정리한 내용입니다.

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

 

데이터 삭제

1. 모든 데이터는 leaf-node에서 삭제를 진행한다.

- internal node를 삭제해야 된다면,

lower_bound (삭제 해야되는 노드 보다 작은 값 중 가장 큰것)

upper_bound (삭제 해야되는 노드 보다 큰 값 중 가장 작은 것) 

 

* 항상 lower_bound / upper_bound는 B tree 특성상 항상 leaf 노드에 존재한다.  

둘 중에 1개를 골라 internal node와 위치를 바꾼뒤 삭제를 진행한다면, B tree의 key 정렬 조건을 위배하지 않는다.

 

 

15를 삭제 하려고 한다면,

9 - lower_bound (삭제 해야되는 노드 보다 작은 값 중 가장 큰것) 또는,

20 - upper_bound (삭제 해야되는 노드 보다 큰 값 중 가장 작은 것) 과 값을 변경하여 삭제 진행한다.

 

2. 불만족한 상황 발생시

데이터 삭제 이후 최소 n차 B tree가 가져야하는 최소의 key의 개수 보다 적은 노드가 발생한 경우.

* 최소의 key 수 =  ceil(n/2) - 1

1) 형제 노드에서 불만족한 노드 기준 왼쪽 형제부터 데이터를 가져와서 해결함.

2) 형제 노드만으로 해결이 안된다면,

부모 노드로 각 포인터의 중간값 데이터를 가져오고, 왼쪽으로 노드 병합 및 정렬 이후 불필요한 노드 삭제.

- 위 절차를 시행시 부모 노드가 불만족이 발생하였다면, 동일한 절차를 반복함 

 

예시) 5차 B tree에서 데이터 삭제.

최소의 key 개수  =  2

 90 delete - leaf 노드에 90은 존재하기 때문에, 삭제후 오름차순 정렬

75 delete

internal 노드를 lower_bound와 교체.

삭제이후 불만족 발생으로 인한 재조정.

오른쪽 형제노드에서 데이터를 정렬순대로 빌려옴.

45 delete

internal 노드를 lower_bound와 교체

삭제이 불만족이 발생하였고, 형제노드에서 데이터를 가져올수도 없는 상황이라, 부모로 부터 중간값을 내려받고, 

두노드를 왼쪽으로 병합한다.

부모노드에서 불만족이 발생. 

형제노드에서 데이터를 가져올수도 없는 상황이라, 부모로 부터 중간값을 내려받고, 두 노드를 왼쪽으로 병합한다.

불필요한 노드 삭제.

60 delete

internal 노드를 lower_bound와 교체후 삭제.

불만족 발생하였으나, 형제로부터 key를 빌려 올수 있음, 빌리고 데이터를 오름 차순으로 정렬