방송통신대학교 자료구조

소개글

"방송통신대학교 자료구조"에 대한 내용입니다.

목차

1. B트리, B*트리, B+트리
2. 스택과 큐
3. 자료구조, 추상자료형

본문내용

1) B트리, B*트리, B+트리
B 트리는 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 하는 트리형 자료구조로 m원 탐색 트리의 하나이며 인덱스 구조를 구현하는데 가장 일반적으로 사용되는 방법이다. m원 탐색 트리가 B 트리가 되기 위해서는
1) 루트와 잎 노드를 제외한 각 노드는 ⌈m/2⌉개의 서브 트리를 가져야 한다.
2) 트리의 루트는 최소한 두 개의 서브 트리를 가져야 한다.
3) 모든 잎 노드는 같은 레벨에 있다.
위의 세 가지 조건을 만족하여야 한다.
1)의 루트와 잎 노드를 제외한 각 노드는 ⌈m/2⌉개의 서브 트리를 가져야 한다는 것은 트리의 각 내부 노드가 최소한 반이 차 있어야 한다는 것을 의미하는 것으로, 서브 트리의 개수가 ⌈m/2⌉보다는 크거나 같아야 하며 m보다는 작거나 같아야 한다는 것이다. 2)의 트리의 루트는 최소한 두 개의 서브 트리를 가져야 한다는 것은 루트는 2개 이상의 자식을 가져야 한다는 의미이다. 그리고 3)은 모든 잎 노드는 같은 레벨에 있도록 하여 높이를 증가시키는 일을 하지 않음으로 인해 루트로부터 모든 경로는 같은 길이를 가지고, 트리가 균형 상태에 있도록 하는 것을 의미한다. 그러므로 B 트리에 노드를 삽입 또는 삭제할 때는 트리가 정해진 균형을 유지하도록 하는 것이 중요하다.

참고 자료

없음