IT용어위키



B 트리

Balanced Tree, B-Tree, B Tree

조건

  • 모든 노드는 최대 m개의 자식들을 가진다.
  • 루트노드와 리프노드가 아닌 모든노드는 최소 m/2개의 자식을 가진다.
  • 루트노드는 최소 2개 이상의 자식을 가진다.
  • k개의 자식을 가진 리프노드가 아닌 노드는 k-1개의 키를 가진다.
  • 모든 리프노드들은 같은 높이에 있어야 한다.
  • 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다.
  • 시간 복잡도 : O(logN)

비트리의 장단점

장점 단점
  • 노드의 삽입/삭제 후에도 균등한 응답 속도를 보장
  • 삽입/삭제 시 균형 유지를 위해 복잡한 연산 필요

같이 보기

  • B+ 트리: 순차검색 향상을 위해 Index Set과 Data Set을 구분
  • B* 트리: 삽입 시 빈번한 노드 분할에 따른 연산 감소

  출처: 공대위키(공대위키에서 최신 문서 보기)
  * 본 페이지는 공대위키에서 미러링된 페이지입니다. 일부 오류나 표현의 누락이 있을 수 있습니다. 원본 문서는 공대위키에서 확인하세요!