728x90 B-tree1 [자료구조] B-Tree & Set ADT 기존 Binary Search Tree의 문제점기존 BST는 균형이 맞는다는 가정 하에 logN의 시간에 탐색이 가능하다는 장점이 있었지만, 특정 조건 [ex) 일렬로 정렬된 경우]에서 O(n)의 시간복잡도를 갖게 되는 문제점이 발생하기도 한다. 이를 해결하기 위한 Search Tree중 하나가 B-tree다. B-Tree 규칙B-tree는 아래의 규칙을 만족하여야 한다 1. root Node는 최소 하나의 요소를 갖을 수 있다. 이외 모든 다른 Node는 최소 MINIMUN의 요소를 갖어야 한다.* MINIMUN : B-트리를 설계할 때 정해둔 최소 허용 요소 수를 의미하며, 보통 B-트리 차수(order) m에 대해 ⌈m/2⌉−1 또는 ⌈m/2⌉처럼 정의한다.** 여기서 차수 M이라는 것은 한 Nod.. 2025. 6. 2. 이전 1 다음 728x90 반응형
