💿자료구조 - B-트리

균형을 고려하는 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 삽입

 

 

---