자료구조 - [ B-트리 ]

B-트리

B-트리에서는 한 노드가 여러 개의 데이터를 가질 수 있으며 여러 자식 노드를 가질 수 있다. 

---

1.  분기 요소(Branching Factor)라는 개념을 통해 한 노드가 가질 수 있는 데이터와 자식 수가 달라진다.

 

2. 모든 Leaf노드는 같은 깊이를 가진다. 그러므로 균형 있는 트리이다.

 

3. 특정 키를 기준으로 작은 키는 좌측에 큰 키는 우측에 배치되며, 좌측 자식은 특정 키보다 작은 키들의 모음이고, 우측 자식은 큰 키들의 모음이다. => 트리를 중위 순회하면 정렬된 키를 얻을 수 있다.

4. 분기 요소(t)가 존재하며 최소 t의 수는 2 <= t 와 같다.

 

5. 루트 노드를 제외한 각 노드당 키의 개수 범위는 t-1 <= 키의 수 <= 2t-1 과 같다.

     => 키의 개수가 2t-1개를 초과하면 분할을 통해 규칙을 유지한다. (삽입 시)

     => 키의 개수가 t-2개 미만이면 회전 또는 병합을 통해 규칙을 유지한다. (삭제 시)

6. 각 노드당 키에 따라 가질 수 있는 자식 수의 범위는 t <= 자식 수 <= 2t 와 같다.

1개의 키가 존재 시 2개의 자식이 존재하며, 2개의 키가 존재 시 3개의 자식이 존재해야 한다. (Leaf 노드 제외)

이러한 규칙을 일반화하면 자식 노드의 개수는 t <= childs <= 2t 범위에 속한다.

 

---

B-트리의 탐색

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼