12-2. B트리

02. B 트리

- m원 탐색 트리는 서브트리의 균형에 대해서는 특별히 제한하지 않음

- 각 노드가 자식을 많이 갖게 하여 트리의 높이를 줄이고 전체적으로 균형을 유지한다면 탐색 성능을 더욱 향상할 수 있음

- m원 탐색트리를 개선한 B트리는 인덱스 구조를 구현하는데 가장 일반적으로 사용함

 

- 차수 m인 B트리의 탐색 경로 길이는 같은 개수의 키를 가지는 이상적인 m원 탐색 트리보다 길 수 있지만 키값을 삽입/삭제할 때 B트리를 유지하는 것이 더 쉬움

 

B트리의 조건

① 루트와 잎노드를 제외한 트리의 각 노드는 최소 m/2개의 서브트리를 갖는다.

② 트리의 루트는 최소한 2개의 서브트리를 갖는다.

③ 트리의 모든 잎노드는 같은 레벨에 있다. 

 

B트리에 키를 삽입하는 알고리즘

① 삽입할 위치를 찾기 위해 노드의 키값을 왼쪽에서 오른쪽으로 탐색한다.

(B트리에서 모든 노드는 잎노드에서 삽입이 시작됨)

② 노드에 빈자리가 있으면 삽입 후 종료한다.

③ 노드가 꽉 찼으면 노드를 2개로 분리하고 키와 포인터를 새 노드에 반씩 할당한다.

     ③-1잎노드 키값과 삽입노드 키값 중에서 중간값을 선택한다.

     ③-2선택된 중간값보다 작은 키값을 갖는 것은 왼쪽 노드에 넣고 큰 것은 오른쪽 노드에 넣는다.

     ③-3중간값을 가지는 노드의 키값과 포인터 를 부모노드에 삽입한다.만일 부모노드가 루트 노드면 두 노드를 가리키도록 (자식노드가 되도록)수정한다.

 

 

B트리의 노드 삽입

 

 

B트리에서 키를 삭제하는 알고리즘 ­ 잎노드에서 삭제

삭제할 키값을 포함한 노드를 찾는다.

 

• 잎노드에서 삭제하는 경우

① 노드에서 키값을 삭제한다.

② 필요하면 재배열한다.

 

 

B트리에서 키를 삭제하는 알고리즘 ­ 내부노드에서 삭제

• 내부노드에서 키를 삭제하는 경우

내부노드의 키값은 하위 노드에 대한 기준값(중간값)이기 때문에 삭제 시, 대체할 수 있는 적절한 값을 찾아야 한다. 보통 왼쪽 서브트리의 가장 큰 키값 또는 오른쪽 서브트리의 가장 작은 키값으로 대체할 수 있다.이들은 모두 잎노드에 위치한다.

① 새로운 기준값(삭제된 자리에 올 키값)을 선택하여 해당 (잎)노드에서 삭제하고 그 값을 현재 키값을 삭제한 자리로 옮긴다.즉,대체한 것이다.

② 기준값으로 대체하기 위해 키를 삭제한 잎노드가 정해진 개수의 키값을 갖지 않으면 트리를 재배열한다.

 

 

B트리에서 키를 삭제하는 알고리즘 ­ 재배열(계속)

재배열

① 키값이 부족한 노드의 오른쪽 형제가 존재하고 키가 정해진 개수보다 많다면 왼쪽으로 회전한다.

①-1 부모노드의 기준(키)값을 개수가 부족한 노드의 끝으로 이동한다. 즉,기준 값을 한 단계 아래로 내려 개수를 채운다.

①-2부모노드의 기준값을 오른쪽 형제의 첫 번째 키로 수정해 균형을 맞춘다.

 

② 키값이 부족한 노드의 왼쪽 형제가 존재하고 키가 정해진 개수보다 많다면 오른쪽으로 회전한다.

②-1부모노드의 기준(키)값을 개수가 부족한 노드의 끝으로 이동한다. 즉,기준값을 한 단계 아래로 내려 개수를 채운다. ②-2부모노드의 기준값을 왼쪽 형제의 마지막 번째 키로 수정해 균형을 맞춘다.

 

③ 좌우 형제가 최소개수의 키를 가지고 있다면,좌우 형제를 합친다.

③-1부모노드의 기준 (키)값을 왼쪽 노드의 마지막에 복사한다.

③-2오른쪽 노드의 모든 키값을 왼쪽 노드로 옮긴다(왼쪽노드가 최대 개수의 키를 갖는다).

③-3키를 갖지 않는 오른쪽 노드는 삭제한다.

③-4부모노드가 루트면서 키를 더 이상 갖지 않으면 합쳐진 노드가 새로운 루트가 된다.그렇지 않고 부모노드의 키 개수가 정해진 개수보다 작으면 부모노드를 재배열 한다.