[컴퓨터] B-Tree
페이지 정보
작성일 21-03-19 14:57본문
Download : B-Tree.hwp
설명
[컴퓨터] B-Tree
b, tree, b tree, b-트리,b트리
(3) B-트리에서의 삽입
(1) B-트리 특성 (2) B-트리에서의 검색 (3) B-트리에서의 삽입 (4) B-트리에서의 삭제 (5) 인덱스된 실제 B-트리 소스코드 (6) 실행화면
B-트리는 m-원 균형탐색 트리로서 균형 알고리즘을 제공한다.
(3) B-트리에서의 삽입
if(i<=x.n && key = x.Ki)
B-트리는 항상 균형 상태를 유지하면서 키 값의 삽입이나 삭제 뒤에도 B-트리 定義(정이)에 명세된 성질이 유지해야 한다. 한 노드의 다음 키를 접근하기 전에 그 키 왼편에 있는 서브트리를 순회한 뒤 노드의 키를 접근하고 다시 오른쪽 서브트리를 순회한다. 리프노드에서의 검색은 순차 검색이된다된다. 또한, 인덱스구조로 가장 효율적이다.
다.
(5) 인덱스된 실제 B-트리 소스코드
// root : 루트 노드
(2) B-트리에서의 검색
나. 빈공간이 없는 경우
x <- root;
- 검색 알고리즘
n<-x.n;
키 값을 검색하기 위해서 m-원 탐색 트리의 직접검색과 같은 과정.
각 노드는 적어도 1/2은 키 값으로 채워져야 한다.
then return Ai; // 레코드의 주소를 반환
새로운 키 값을 단순히 순서에 맞게 삽입
i<-i+1;
① B-트리는 공백이거나 높이가 1이상인 m-원 탐색 트리
순서
}
// n : 노드에서의 키의 개수
Download : B-Tree.hwp( 44 )
return null; // key와 일치하는 rqkt이 트리에 없는 경우
④ 모든 리프는 같은 레벨에 있다
③ 루트는 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다. 그리고 중간 키 값은 분할된 노드의 부모 노드로 올라가 삽입된다된다. // key : 키의 값
end searchBT()
가. 빈공간이 있는 경우
노드에서 오버플로우(Overflow)가 발생한 경우, 노드를 두 개의 노드로 분할한다.
while ( ( x<-x.Pi-1) != null ) //포인터의 값이 널이 아닐 때
레포트 > 공학,기술계열
(4) B-트리에서의 삭제
먼저, 루트노드를 조사하고 작은키 값은 왼쪽으로 큰 키 값은 오른쪽으로 포인터가 이동한다.
(2) B-트리에서의 검색
searchBT(key)
while(i<=n && key > x.kKi) // 노드를 찾는 루프
i<-1;
(1) B-트리 property(특성)
(6) 실행화면
B-트리 전체의 순차 검색은 키 값에 따라 트리의 각 노드를 중위 순회[inorder traversal(왼->위->오)]하면 된다된다.
// x : 노드
② 루트와 리프를 제외한 내부 노드는 최소 (m/2), 최대 m개의 서브트리를 갖는다. 해당 노드의 키 값에 새로운 키 값을 삽입했다고 가정하고 삽입 결과의 중간 키 값. 즉, (m/2)번째의 키 값을 중심으로 왼편 작은 키들은 해당 노드에 그대로 남겨 두고 오른 편 큰 키들은 새로운 노드에 저장한다. 하지만, 삽입해야 되는 리프 노드에 키 값을 삽입할 수 있는 여유 공간이 있느냐 없느냐에 따라 두 가지 경우가 발생한다.
(1) B-트리 特性(특성)
do {
B-트리에서 새로운 키 값은 항상 리프노드에 삽입된다된다.