한국방송통신대-2020기말-자료구조

소개글

"한국방송통신대_2020기말_자료구조"에 대한 내용입니다.

목차

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

본문내용

1) B트리, B*트리, B+트리를 설명하고 비교하시오. (30점) :30줄이상 작성
B트리 : 다음 조건을 만족하는 ^(주1))m원 탐색 트리를 차수 m인 B트리라 한다. 이 트리는 인덱스 구조를 구현하는 데 가장 일반적으로 사용하는 방법이다.
1. 루트와 잎 노드를 제외한 트리의 각 노드는 최소 [m/2] 개의 서브트리를 갖는다.
2. 트리의 루트는 최소한 두 개의 서브트리를 갖는다.
3. 트리의 모든 잎 노드는 같은 레벨에 있다.
삽입과 삭제 연산을 할 경우에는 이 조건에 맞는지 확인해야 한다.

54,52 삽입 과정에서 노드 분리가 일어나며 51은 50과 52 사이에 넣어야 하므로 부모 노드가 분리된다. 이 때 키값 51의 오른쪽 포인터를 키값 52인 새 노드를 가리키도록 수정해야 하며, 다른 포인터들도 이전 주소를 차례대로 저장한다. 중간값 53을 부모 노드 어딘가에 저장해야 하는데 고간이 꽉 찼다면 또 분리해야 한다. 마지막에 84를 삽입할 때 트리의 높이가 한 레벨 올라간다.
B 트리에서 노드를 삭제하려면 어떤 노드가 정해진 개수의 키를 가져야 한다. 따라서 삭제 결과 개수가 부족하면 그 노드를 다른 노드와 묶어야 한다.

B*트리 : 노드의 약 2/3 이상이 차야 하는 B트리를 B*트리라고 한다. B*트리는 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮긴다. 삽입, 삭제 시 발생하는 노드 분리를 줄이려고 고안하였다. 정의하자면 차수가 m인 B* 트리는 다음을 만족하는 B 트리이다.
1. 공집합이거나 높이가 1 이상인 m인 탐색 트리이다.
2. 루트 노드는 2개 이상 2[2m-2]/3]+1개 이하의 자식 노드를 갖는다.
3. 내부 노드는 최소한 [(2m-1)/3]개의 자식 노드를 갖는다.
4. 모든 잎 노드는 동일한 레벨에 놓인다.
5. 포인터가 k개인 잎 노드가 아닌 노드는 k-1개의 키를 갖는다(루트 노드 포함)

참고 자료

없음