2학년 2학기 자료구조 기말 온라인 평가 참조용

소개글

"2학년 2학기 자료구조 기말 온라인 평가_참조용"에 대한 내용입니다.

목차

없음

본문내용

<B트리>
B트리는 균형 트리로서 기존에 자식을 2개만 가질 수 있던 Binary tree를 확장하여 더 많은 자식을 가질 수 있다. 기존의 binary tree의 경우 추가, 검색, 삭제 등에 O(NlogN)의 시간복잡도를 보여주며, 좌우 균형이 맞지않는 최악의 경우 O(N*N)의 시간복잡도를 가지게 된다. B트리란 하나의 노드에 여러 자료가 배치되는 트리 구조이다. 한 개의 노드에 M개의 자료가 배치되면 M차 B트리라고 한다. 5차 B트리인 경우 자식 노드가 최대 5개인 것을 의미한다. B트리는 스스로 균형을 맞추는 트리이다. 그래서 최악의 경우에도 O(logN)의 검색성능을 보인다. 또한 B트리는 하나의 노드에 많은 수의 데이터를 저장할 수 있다.

참고 자료

없음