'b tree' 태그의 글 목록

Balanced Tree (불균형) 이진탐색트리의 문제점은 최악의 경우 O(N)이 발생한다는 것이다. Balanced Tree는 항상 균형을 맞추어진 상태로 유지함으로써 O(logN)의 성능을 보인다. 하지만 데이터의 삭제, 삽입, 갱신이 발생할 때 Balance를 유지하기 위한 연산이 추가로 필요하게 된다는 단점이 있다. Balanced Tree의 종류로 AVL Tree와 레드블랙트리, 2-3 Tree, 2-3-4 Tree, B Tree 등이 있다. B-Tree는 다차원트리 B-Tree는 Balanced Tree이면서 다차원 트리이다. 하나의 노드가 가질 수 있는 자식 노드의 개수(링크 개수)를 M이라고 했을 때 하나의 노드에 '최대' M-1개의 자료를 담을 수 있으며 이 경우 M차 다차원 트리라고 한..