💿자료구조 - B-트리

비엔 Vien 2024. 5. 9. 17:45

균형을 고려하는 AVL과는 또 다른 트리!

m차 B-트리 의 조건

1. 모든 leaf 노드의 깊이가 동일

2. 노드 당 자식 수는 [m/2] ~ m개 (leaf 노드 제외) *[m/2] : 올림 함수

3. 자식 노드의 수는 데이터 수보다 1 많음 (leaf노드 제외)

>> 즉, m차 B트리 에서 노드 내 데이터의 수는 최대 m-1개

4. 단일 노드 내에서 데이터는 정렬됨

5. 트리의 관점에서도 데이터는 정렬됨

B-트리에서의 데이터 탐색 과정

높이에 따라 결정되므로.. 시간복잡도는 O(hN) = O(logN)

[ B-트리에서의 원소 삽입 ]

1. 데이터 수 제한을 넘어서지 않는 경우에서의 삽입

- 새 데이터가 들어갈 적절한 리프 노드를 선정

- 해당 리프 노드에 데이터가 추가될 여유가 있는 경우 그대로 삽입 수행

ex1) 65 를 삽입하자

ex2)

2. 데이터 수 제한을 넘어서는 경우에서의 삽입

- 리프 노드에 데이터가 삽입될 여유가 없을 경우, 가운데 데이터를 튕겨내는 과정을 반복

- 튕겨 나가는 데이터의 좌우 값들이 분리됨!!

ex) 39 삽입