[방송통신대학교] 자료구조 기말시험(온라인)

소개글

자료구조 기말시험(온라인)은 설명과 비교를 작성하는 형식입니다.
교재와 강의를 참고하여 작성하였으며 해당 과제는 A의 점수를 받았습니다.
잘 활용하여 좋은 점수 받으시길 바랍니다.

목차

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

본문내용

B트리란, 균형트리로서 기존에 자식을 2개만 가질 수 있던 Binary tree를 확장하여 더 많은 자식을 가질 수 있는 것을 말한다. B트리는 하나의 노드에 여러 자료가 배치되는 트리구조이며 한 개의 노드에 m개의 자료가 배치되면 m-tree라고 한다. B트리는 스스로 균형을 맞추는 트리로써, 최악의 경우에도 O(logN)의 검색성능을 보인다. 또한 하나의 노드에 많은 수의 데이터를 저장할 수 있는 장점을 가지고 있다. 따라서 단순하지만 효율적인 트리라고도 할 수 있다.
B트리의 조건으로는 노드의 데이터가 정렬된 상태여야 하며, 루프노드는 적어도 두 개 이상의 자식을 가져야한다는 것, 루트노드를 제외한 모든 노드는 적어도 m/2개의 자료를 가지고 있어야 한다는 것, 외부 노드로 가는 경로의 길이는 모두 같아야 한다는 것, 입력 자료는 중복될 수 없다는 것 등이 있다.

참고 자료

없음