멀티웨이 탐색트리
1. m원(m-way) 탐색트리
- 이진트리의 확장된 형태
- 트리의 노드가 m개 이하, 같은수의 노드를 가진 이진탐색트리보다 낮은 높이
- 탐색트리의 제한을 따르면서, 2개 이상~ m개 이하의 자식노드를 가질수 있음
- 단말노드들은 키값만 표기하고 내부노드 중 자식이 없는 포인터는 표시하지 않음
- 노드의 가지가 많을수록 최대탐색시간이 짧아짐(서브트리가 많고 얕으므로 빠른
탐색이 가능하나 2~4원까지만 사용함, 그보다 많으면 빈 공간으로 메모리 효율낮음)
▶ m원 탐색트리의 노드구조
▶ m원 탐색트리 탐색연산 (키값을 찾는 연산)
struct Mnode *nodeptr;
struct Rectype *recptr;
struct Rectype *Search(int skey, struct Mnode *r){
int i ;
extern struct Mnode node;
if(r == NULL) {
return(NULL);
else {
i =0;
while(i < r → n && skey > r → keyptrs[i].key)
i++;
if(i < r → n && skey == r → keyptrs[i].key)
return(r → keyptrs[i].addr);
else if( i < r → n)
return(Search(skey, r → keyptrs[i].ptr);
else
return( (Search(skey, r → keyptrn);
}}
2. B트리
(1)배경
- m원 탐색트리는 서브트리의 균형에 대해 특별히 제한하지 않음
- 각 노드가 자식을 많이 가지도록 하여 높이를 줄이고, 전체적으로 균형유지로 성능으루
개선한 B트리를 인덱스 구조 구현에 사용
- 차수 m인 B트리의 탐색경로의 길이는 같은 개수의 키를 가지는 m원트리보다 길수 있으나,
이상적인 m원 탐색트리에 비해 키값을 삽입/삭제할 때 쉬움 (효율적)
(2)조건
- 루트와 리프노드를 제외한 트리의 각 노드는 최소 ⌈m/2⌉개의 서브트리를 가짐
- 트리의 루트는 최소한 2개의 서브트리를 가짐
- 트리의 모든 리프노드는 같은 레벨
▷ 키를 삽입하는 알고리즘
- 삽입할 위치 (노드의 키값을 왼쪽부터 오른쪽으로 탐색, B트리는 리프노드에서 삽입시작)
- 노드에 빈자리에 있으면 삽입후 종료
- 노드가 꽉 차면 노드를 분리하고 키와 포인터를 새노드에 반씩 할당, 리프노드 키값과 삽입노드 키의
중간값을 선택( 작은것은 왼쪽/큰것은 오른쪽/중간값은 부모노드에 삽입)
부모노드가 루트이면 두 노드를 가리키도록(자식노드가 되도록) 수정
▷ 키를 삭제하는 알고리즘
리프노드
- 삭제할 값을 포함한 노드 탐색하고 키값을 삭제한후, 필요시 재배열 (리프노드가 비면 안됨)
내부노드
- 내부노드 값은 하위노드 기준값(중간값)이므로 삭제시 적절한 대체값 필요
왼쪽 서브트리의 가장 큰값 혹은 오른쪽 서브트리의 가장 작은 키값으로 대체 (리프노드에서)
- 새로운 기준값(대체)을 리프노드에서 삭제한후 현재 키값을 대체, 키를 삭제한 리프노드가
정해진 개수의 키값을 가지지 않으면 트리 재배열
재배열
- 키값이 부족한 노드의 오른쪽 형재노드가 존재하고 정해진 최소갯수보다 많다면 왼쪽회전
부모노드 기준값 갯수가 부족한 노드의 끝(내려서 채움)으로 이동하고 오른쪽 형제를 키로 수정
- 좌우형제가 최소갯수의 키를 가지면 합침, 부모 모드의 기준(키)값을 왼쪽노드의 마지막에
복사하고, 오른쪽 노드의 모든 키값을 왼쪽 노드로 옮김, 키를 가지지 않은 오른쪽 노드 삭제
부모노드가 루트이면서 키를 가지지 않으면 합쳐진 노드가 새로운 루트, 부모노드 키 개수가
정해진 최소보다 작으면 부모노드 재배열
3. B＊트리
(1) 배경
- 노드의 2/3 이상이 채워지는 B트리
- 노드가 꽉차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제노드로 옮김
- B트리와 동일한 수에서 높이가 낮고, 삽입/삭제시 발생하는 노드분리를 줄이기 위해 고안됨
(2)조건
- 공집합이거나 높이가 1이상인 m원 탐색트리
- 루트노드는 2개 이상, 2⌊(2m-2)/3⌋+1개 이하의 자식노드를 가짐
- 내부노드는 최소한 ⌈(2m-1)/3⌉개의 자식노드를 가짐
- 모든 리프노드는 동일레벨
- 포인터가 k개이면서 잎노드가 아닌 노드는 k-1개의 키(루트노드 포함)
(3) B＊트리의 노드삽입
4. B⁺ 트리
(1) 배경
- 탐색 트리로 구성하면 매우 빠르게 탐색되나 전체 데이터를 차례로 처리하기는 불편함
- 매번 왼쪽 혹은 오른쪽 비교해 다음 노드를 찾아가며 처리해야 함
- B⁺ 트리는 인덱스된 순차파일 구성에 사용되며, B트리처럼 각 노드의 키가 1/2이상 채워져야함
(2)조건
- 리프 노드를 순차적으로 연결하는 포인터 집합존재, 노드 마지막 포인터는 다음 키값을 가지는 노드를 할당
- 순차처리는 포인터를 이용하여(키값을 비교하지 않고) 차례로 다음 데이터에 접근해서 처리
- 모든 키값이 리프노드에 있고, 대응하는 실제데이터(파일내용)에 대한 주소를 가짐
- 직접 탐색은 리프노드에 도달해야 종료
(3)특징
- 모든 키값이 리프에 있고, 그 키값에 대응하는 실제 데이터의 주소를 리프노드가 가지고 있음
- 탐색은 리프노드에 도달하면 종료
- 같은 노드의 B트리에 비해 레벨이 작아 같은 차수의 B트리에 비해 탐색성능이 거의 같음
(3)삽입
- 리프노드가 2개의 노드로 분리될때는 키 값순서에 따라 배치하고 중간키값은 부모 노드에 올려놓음
- 새노드는 순서에 맞게 리프노드에 삽입 (내부노드에도 자리잡아야 함)
- 키 값을 리프 노드에서 삭제, 트리의 내부 노드에서 삭제할 필요없음 ( 키값이 탐색에 사용 )
5. 2-3트리
트리의 삽입/삭제 시 전체균형을 맞추는 것에 보다 중점을 두는것이 좋음
(1) 배경
- 차수가 2또는 3인 내부노드를 갖는 검색트리
- 2-노드(2개의 자식노드: 차수가 2)와 3노드(3개의 자식노드:차수가 3)로 구성된 특수한 B트리
- 2-노드 혹은 3-노드라는 제약이 내부노드 (리프노드는 같은 레벨이어야 한다는 제약만 존재함)
(1) 조건
▷ 각각의 내부노드는 2-노드(1개의 키값) 혹은 3-노드(2개의 키값)
▷ Ichild, mchild를 각각 2-노드의 왼쪽자식(left child) 및 중간자식(middle child)이고
lkey가 2-노드의 키 값이라 하면, 루트가 Ichild인 모든 2-3서브트리의 키값은 lkey보다 작고
루트가 mchild인 모든 2-3서브트리의 키값은 lkey보다 크다.
▷ Ichild, mchild, rchild를 각각 3-노드의 왼쪽, 중간 및 오른쪽 자식이라고 두고
lkey와 rkey를 이 두 노드의 키값이라 하면 ,
① lkey < rkey
② 루트가 lchild인 모든 2-3 서브트리의 키값은 lkey보다 작음
③ 루트가 mchild인 모든 2-3서브트리의 키값은 rkey보다작고 lkey보다 큼
④ 루트가 rchild인 모든 2-3서브트리의 데이터는 rkey보다 큼
▷ 모든 잎 노드는 같은 레벨에 있음
▶ 2-3 트리의 구조정의
typedef struct two_three *two_three_ptr;
struct two_three {
int lkey, rkey;
two_three_ptr lchild, mchild, rchild;
};
▶ 2-3 트리의 탐색
two_three_ptr search23(two_three_ptr t, int x) { // 각각 현재의 노드와 키의 값
while(t)
switch(compare(x,t)) {
case 1 : t = t → lchild; // x가 노드t의 왼쪽키값보다 작은경우
break;
case 2 : t = t → mchild; // x가 노드 t의 왼쪽보다 크고 오른쪽보다 작은경우
break;
case 3 : t = t → mchild; // x가 노드 t의 오른쪽보다 큰 경우
break;
case 4 : return (t) ; // x가 노드 t의 키값들 중 어느 하나와 같은 경우
}
return(NULL);
}
▶ 2-3 트리의 삽입 (트리의 경우 구조화되어 있어 삽입/삭제에 이슈)
void insert23( two_three_ptr t, int y) {
two_three_ptr q, p, r;
if( !(*t))
new_root(t, y, null);
else {
p = find_node(*t, y); //기존에 있는 값인지 확인
if(!p) {
fprint(stderr, "The key is currently in the tree₩n") ;
exit(1);
}
q = NULL;
for ( ; ; ) // 키값이 없으면 계속 찾아내려감
if(p → rkey == INT_MAX) {
put_in(&p, y, q); //p노드에 y값 삽입
break; }
else {
split(p, &y, &q); // 쪼개서 새노드
if(p == *t ) {
new_toor(t,y,q);
break; }
else
p = delete(); }
}}
▶ 2-3 트리의 삭제
- 리프노드가 아닌 노드의 키를 삭제하면 그곳을 다른 키로 대체
(통상 삭제키의 왼쪽서브트리의 가장 큰값, 오른쪽 서브트리의 가장 작은값 대체)
6. 2-3-4트리
(1) 배경
- 2-3트리를 확장하여 4개의 자식을 가진 4-노드를 허용하는 탐색트리
- 2-3-4트리는 2-노드와 3-노드에 대한 트리 재구성 확률이 작아 삭제/삽입 효율적
(2)조건
- 각각의 내부노드는 2-노드(키값 1개), 3-노드(키값 2개), 4-노드(키값 3개)
- Ichild, mchild는 각각 2-노드의 왼쪽자식 및 좌중간 자식노드, lkey를 키값이면
lchild가 루트인 모든 2-3-4서브트리의 키는 lkey보다 작고, mchild의 모든
2-3-4 서브트리의 키값은 lkey값보다 크다.
- Ichild, mchild, rchild를 각각 3노드의 왼쪽, 좌중간, 우중간 자식노드라 하고
lkey, mkey를 이 노드의 키값이라고 하면
① lkey < mkey,
② 루트가 lchild인 모든 2-3-4서브트리의 키값은 lkey값보다 작다.
③ 루트가 lmchild인 모든 2-3-4서브트리의 키값은 lkey보다 크고 mkey보다 작다.
④ 루트가 rmchild인 모든 2-3-4서브트리의 키값은 mkey보다 크다.
- lchild, lmchild, rmchild, rchild가 4노드의 왼쪽, 좌중간, 우중간, 오른쪽자식이고
lkey, mkey 및 rkey가 이 노드의 키값일때
① lkey < mkey < rkey
② 루트가 lchild인 모든 2-3-4서브트리의 키값은 lkey값보다 작다.
③ 루트가 lmchild인 모든 2-3-4서브트리의 키값은 lkey보다 크고 mkey보다 작다.
④ 루트가 rmchild인 모든 2-3-4서브트리의 키값은 mkey보다 크고 rkey보다 작다.
⑤ 루트가 rchild인 모든 2-3-4서브트리의 키값은 rkey보다 크다.
- 모든 리프노드들은 같은 레벨
(3)삽입 연산
- 2-3-4트리에서는 2-노드와 3-노드에 대한 트리 재구성의 확률이 작아 삽입/삭제 효율적
- 삽입연산에서 문제가 되는 4-노드는 위치에 따라 3개지로 분류
① 4노드가 루트인경우
② 4노드의 부모가 2-노드인 경우
③ 4노드의 부모가 3-노드인 경우
(4)삭제연산
- 리프노드의 키값은 단순삭제
- 삭제시 노드를 분리하고 값을 아래로 떨어트려 삭제 (트리 구조를 유지)
7. 레드블랙트리
- 효율적인 기억장소 사용을 위해 2-3-4트리를 이진트리로 나타낸 탐색트리- 레드간선과 블랙간선의 서브트리 포인터를 나타냄- 레드간선은 2-3-4트리의 한 노드내에 노드관계, 블랙은 2-3-4트리의 부모-자식관계- 레드블랙트리의 탐색방법은 보통의 이진탐색트리의 탐색알고리즘과 동일
(3)삽입 연산
- 4-노드가 루트노드인 경우 레드 블랙트리의 노드분리
