B-tree 검색, 삽입, 삭제

B-tree 구현을 위한 검색, 삽입, 삭제 동작 과정
bottom-up 방식 구현

B-tree의 개념은 찾아보면 훨씬 더 잘 정리된 자료들이 많기 때문에 따로 정리하지 않고,
검색, 삽입, 삭제 과정만 정리하기로 했다.
(출처 : programiz)

<성질>

M차 Btree
1. 노드는 ($[m/2]$ ~ $m$)개의 자식을 가질 수 있다.
2. 노드에는 ($([m/2] - 1)$ ~ $(m-1)$)개의 키가 포함될 수 있다.

노드의 키가 x개면, 자식은 (x+1)개
최소차수는 자식의 하한
최소차수 t라면 m = 2t - 1을 만족해야함
ex. 최소차수 2라면 3차 tree이며, key의 하한은 1

<검색>

검색은 루트 노드에서부터 하향식으로 이루어진다.

검색하려는 키를 k 라고 하자.

1. 루트 노드에서 시작하여, 노드의 첫번째 키를 k와 비교한다.
   만약 k가 노드의 첫번째 키와 같다면(k = the first key of the node),
   그 노드와 인덱스를 반환한다.
2. 만약 현재 검색하고 있는 노드가 leaf라면, NULL을 반환한다.
3. 만약 k가 노드의 첫번째 키보다 작다면(k < the first key of the root node), 왼쪽 자식에서 이 키를 재귀적으로 찾는다.
4. 만약 현재 노드에 하나 이상의 키가 있고 k가 현재 노드의 첫번째 키보다 크다면(k > the first key), k를 현재 노드의 다음 키와 비교한다.

• 만약 k가 다음 키보다 작다면(k < next key), 왼쪽 자식에서 이 키를 찾는다.
• 만약 k가 다음 키보다 크다면, 오른쪽 자식에서 이 키를 찾는다.

5. 1~4 과정을 리프에 도달할 때까지 반복한다.

<삽입>

요소를 삽입하기 위해선 1. 요소 삽입에 적절한 노드를 검색하고, 2. 필요한 경우, 노드를 분할해야 한다.
삽입은 상향식으로 이루어진다.

1. 트리가 비어있으면 루트 노드를 할당하고, 키를 삽입한다.
2. 노드에 넣을 수 있는 키 수를 업데이트한다. (count 변수 활용)
3. 삽입할 적절한 리프 노드를 검색한다.
4. 노드가 가득 찬 경우, 4-a로 간다.
   노드가 가득 안 찬 경우, 4-b로 간다.
   4-a. 위 과정에서 적절한 노드 검색했는데 노드가 가득찬 경우
   1. 오름차순으로 요소를 삽입한다.
   2. 그러면 노드가 담을 수 있는 개수를 초과해서 노드에 담겨있는 상태이므로, 중앙값에서 분할한다.
   3. 중앙값은 위쪽 노드로 보내고, 왼쪽 키들은 왼쪽 자식으로, 오른쪽 키들은 오른쪽 자식으로 만든다.
   4. 부모 노드를 검사해서 또다시 가득 찼다면, 해당 부모노드에서부터 4-a-2~4를 반복한다.
   4-b. 위 과정에서 적절한 노드가 가득 안 찬 경우
   오름차순으로 삽입한다.
   
   

<삭제>

요소를 삭제하기 위해선 1. 삭제할 키가 있는 노드 검색, 2. 키 삭제, 3. 필요한 경우, 트리 균형 조정을 해야한다.
삭제 과정을 이해하기 위해선 두 가지 용어를 알아야 한다.

• inorder predecessor : 노드의 왼쪽 자손에서 가장 큰 키
• inorder successor : 노드의 오른쪽 자손에서 가장 작은 키

💡 Case 1. 삭제할 키가 리프에 있는 경우

if 현재 노드에 키가 최소 키수보다 크다면:
	그냥 삭제한다.
elif 왼쪽 형제 노드의 키가 최소 키수보다 크다면:
	1. 왼쪽 형제를 방문하고, 왼쪽 형제 노드에서 가장 큰 키를 저장한다.(tmp)
	2. 현재 키를 삭제한다.
	3. 부모 노드를 현재 위치로 내리고, tmp를 부모 노드로 이동시킨다.
elif 오른쪽 형제 노드의 키가 최소 키수보다 크다면:
	1. 오른쪽 형제를 방문하고, 오른쪽 형제 노드에서 가장 작은 키를 저장한다.(tmp)
	2. 현재 키를 삭제한다.
	3. 부모 노드를 현재 위치로 내리고, tmp를 부모 노드로 이동시킨다. 
elif 부모의 키가 최소 키수보다 크다면 :
	부모키를 내려서 왼쪽 형제 노드랑 병합한다.
	(부모키란 현재 `index-1`번째 키를 의미한다.
	단, 0번 index일 땐, 0번째 부모키로 처리한다.)
else (부모 노드의 키가 최소만큼이라면):
	키를 삭제하고, 부모 노드를 아래로 내리고, case3의 2번 과정으로 이동한다.

💡 Case 2. 삭제할 키가 내부 노드에 있고, 노드나 자식에 키가 최소 키수보다 많을 경우

if 자식이 리프인 경우:
	if 그 자식의 키가 최소 키수보다 크다면: 
    		키를 삭제한 후, 그 자식에서 가장 큰 값으로 삭제된 부분을 대체한다.
     	elif 내 키수가 최소 키수보다 크다면:
            	현재 키를 삭제한 후, 내 키의 자식 노드들을 병합한다. (왼쪽으로)
	else (나와 자식 모두 최소 키수인 경우): 
    		case 3으로 이동한다.

else (자식이 리프가 아닌 경우):
	왼쪽 자손의 inorder predecessor(리프)와 현재 키의 자리를 바꾼다.
    	현재 키를 삭제한 후, case 1으로 이동한다.

💡 Case 3. 삭제할 키가 내부 노드에 있고, 노드에 키가 최소만큼, 노드의 자식의 키도 모두 최소인 경우

이 경우에는 삭제할 키가 있는 노드도 최소, 내 자식들도 최소이므로, 키를 삭제하면 트리의 높이가 줄어든다.

1. 양쪽 자식을 병합하여, tmp변수에 저장한다.
2. 현재 키를 삭제한다.
3. 나의 부모 키를 왼쪽 형제 노드에 붙인다.
4. 이 형제 노드의 마지막에 tmp를 붙인다.

if 형제 노드가 최대 키수를 넘어갔다면:
	삽입 연산의 4-a를 수행한 후, 종료한다.
else:
	if 부모 노드가 최소 키수보다 작다면:
    		부모 노드에 대하여 2번 과정부터 반복한다.
	else: 종료한다.