[A+] 방송통신대학교 컴퓨터과학과 자료구조 기말과제

소개글

[A+] [방송통신대학교 컴퓨터과학과] 2학년 2학기 자료 구조 과제물
- 2020년 2학기 작성 자료입니다.

목차

1, B트리, B*트리, B+트리를 설명하고 비교하시오.(30점): 30줄 이상 작성
2. 스택과 큐를 설명하고 비교하시오.(20점): 30줄 이상 작성
3. 자료구조, 추상자료형을 설명하고 비교하시오.(20점): 30줄 이상 작성

본문내용

1. B트리, B*트리, B+트리를 설명하고 비교하시오.(30점): 30줄 이상 작성
B트리: 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리는 m원 탐색 트리이다. 이는 탐색 트리의 제한 아래 두 개 이상, m개 이하의 자식을 가질 수 있다. B트리는 인덱스 구조를 구현할 때 가장 일반적으로 사용하며, 조건 3 가지를 만족하는 m원 탐색 트리를 차수 m인 B트리로 설명할 수 있다. 해당 조건은 루트와 잎 노드를 제외한 트리의 각 노드는 최소 [m/2] 개의 서브트리를 갖는다.(트리의 각 내부 노드는 절반 이상 차있어야함.) 트리의 루트는 최소한 두 개의 서브트리를 갖는다.(트리를 처음부터 분리되게 한다.) 트리의 모든 잎 노드는 같은 레벨에 있다.(트리가 거의 균형 잡히게 한다.) 차수가 m인 B트리의 탐색 경로 길이는 같은 키의 개수를 가지는 최적 상태의 m원 탐색 트리보다 길 수 있다. 하지만 키 값을 삽입, 삭제할 때 수고가 적어서 차수가 m인 B트리를 사용한다. 차수가 m인 B트리의 각 노드는 m원 탐색 트리의 노드 구조와 동일하다. B트리에 키 삽입 시에 노드가 꽉 찬 경우, 분리 후 키 값과 포인터 재분배가 필요하다.

참고 자료

자료구조 | 강태원,정광식 | 한국방송통신대학교출판문화원 | 2017-07-25
홍기천 | 로봇의 미로 탐색 문제해결을 위한 스택과 큐 학습 방안 | 2012