이진 탐색 트리 (BST, Binary Search Tree)
모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가진다.
모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값만 가진다.
- 자녀 노드는 최대 2개까지 가질 수 있다.
만약 자녀 노드를 3개까지 가지고 싶다면 어떻게 해야될까?
그렇다면 각 자식 노드의 크기는 다음과 같을 것이기에 부모 노드는 값을 1개가 아닌 2개를 저장해야 된다.
- 노드1 < k1
- k1 < 노드2 < k2
- 노드3 > k2
이를 B-Tree라고 한다.
- 자녀 노드의 최대 개수를 늘리기 위해서는 부모 노드에 key를 하나 이상 저장한다. (k1, k2)
- 부모 노드의 key들을 오름차순으로 정렬한다.
- 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다.
B-Tree Parameter
B-Tree를 사용하면 자녀 노드의 최대 개수를 직접 제어할 수 있다.
B-Tree를 구현할때 몇 개의 자녀 노드를 가질 것인지가 중요한 파라미터이다.
- : 각 노드의 최대 자녀 노드 수
- M차 트리: 최대 M개의 자녀를 가질 수 있는 B-Tree를 말한다.
- : 각 노드의 최대 key 수
- : 각 노드의 최소 자녀 노드 수 (반올림 필요, 3차 B-Tree는 )
- 해당 조건은 root node와 leaf node에서는 제외한다.
- : 각 노드의 최소 key 수
- 해당 조건은 root node에서는 제외한다.
101차 B-Tree
- 최대 자녀 수: 101
- 최대 Key 수: 100
- 최소 자녀 수: 51
- 최소 Key 수: 50
Best Case일 경우 약 1억개의 데이터 저장 가능, Worst Case일때는 약 26만개 데이터 저장 가능
internal 노드의 key 수가 개라면 자녀 노드의 수는 언제나 개이어야 하므로 아래 트리와 같은 형태는 불가능하다.
시간 복잡도
B Tree에서 조회/삽입/삭제의 시간 복잡도는
B-Tree 데이터 삽입
B- 트리에 데이터를 삽입하는 과정은 탐색과는 다르게 상향식으로 진행
- 데이터의 추가는 항상 leaf 노드에 (오름차순으로 정렬하여 추가)
- 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할, 가운데 key는 승진
출처 및 참고자료
이 채팅을 확인해 보세요누군가 회원님이 보고 싶어 할 것 같다고 생각한 채팅입니다.
www.youtube.com