B tree 데이터 삭제 동작 방식

재조정 조건

M 차 B 트리일 경우 -> 즉, 각 노드의 최대 자녀 수: M

• 각 노드의 최소 자녀 수: ceil(M/2)
  - 각 노드의 최소 key 수: ceil(M/2)-1 을 유지하도록!

삭제 로직

• 삭제는 항상 leaf node에서 일어난다.
  - 그럼 internal node에서의 삭제는?
  • predecssor(선임자: 본인 노드보다 작은 값을 가진 서브트리 중 가장 큰 값을 가진 노드) 또는 successor(후임자: 본인 노드보다 큰 값을 가진 서브트리 중 가장 작은 값을 가진 노드) 와 swap후 leaf node에서 삭제.
• 삭제 후에 재조정 조건(각 노드의 최소 key 수) 에 위배되면 재조정을 한다.

재조정 우선순위

1. 형제(왼쪽, 오른쪽 순으로)가 여유가 있다면 도움을 받는다.
   • 부모 노드의 값을 본인 노드로 옮기고 도와줄 형제 노드의 값을 부모 노드 위치로 옮긴다.
2. 부모 노드의 도움을 받는다.
   • 부모 노드의 값을 왼쪽 노드로 옮기고 형제 노드의 값 또한 왼쪽 노드로 옮겨 합친다.
3. 1,2과정에서 부모 노드에게 문제가 생겼다면,
   • 부모 노드 != root 라면 다시 1번부터 재조정 시작.
   • 부모 노드 == root and 비어있다면 삭제하고 직전에 합쳐진 노드는 root가 된다.