[전산학] B-Tree
페이지 정보
작성일 22-10-06 08:01
본문
Download : B-Tree.hwp
한 노드의 다음 키를 접근하기 전에 그 키 왼편에 있는 서브트리를 순회한 뒤 노드의 키를 접근하고 다시 오른쪽 서브트리를 순회한다.
(1) B-트리 characteristic(특성)
① B-트리는 공백이거나 높이가 1이상인 m-원 탐색 트리
② 루트와 리프를 제외한 내부 노드는 최소 (m/2), 최대 m개의 서브트리를 갖는다.
(2) B-트리에서의 검색
키 값을 검색하기 위해서 m-원 탐색 트리의 직접검색과 같은 과정.
먼저, 루트노드를 조사하고 작은키 값은 왼쪽으로 큰 키 값은 오른쪽으로 포인터가 이동한다.
- 검색 알고리즘
searchBT(key)
// key : 키의 값
// x : 노드
// root : 루트 노드
// n : 노드에서의 키의 개수
x <- root;
do {
i<-1;
n<-x.n;
while(i<=n && key > x.kKi) // 노드를 찾는 루프
i<-i+1;
if(i<=x.n && key = x.Ki)
then return Ai; // 레코드의 주소를 반환
}
while ( ( x<-x.Pi-1) != null ) //포인터의 값이 널이 아닐 때
return null; // key와 일치하는 rqkt이 트리에 없는 경우
end searchBT()
(3) B-트리에서의 삽입
B-트리에서 새로운 키 값은 항상 리프노드에 삽…(省略)
다.
순서
B,Tree,기타,레포트
[전산학] B-Tree
B-Tree - 미리보기를 참고 바랍니다.
설명
B-트리는 m-원 균형탐색 트리로서 균형 알고리즘을 제공한다.
④ 모든 리프는 같은 레벨에 있다아
B-트리는 항상 균형 상태를 유지하면서 키 값의 삽입이나 삭제 뒤에도 B-트리 定義(정의)에 명세된 성질이 유지해야 한다.
각 노드는 적어도 1/2은 키 값으로 채워져야 한다. 리프노드에서의 검색은 순차 검색이된다된다.
③ 루트는 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
B-트리 전체의 순차 검색은 키 값에 따라 트리의 각 노드를 중위 순회[inorder traversal(왼->위->오)]하면 된다된다. 또한, 인덱스구조로 가장 효율적이다. , [전산학] B-Tree기타레포트 , B Tree
Download : B-Tree.hwp( 40 )
레포트/기타
B-Tree - 미리보기를 참고 바랍니다.
