1. m원 탐색 트리
1.1. 정의
•
트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리
•
m
◦
그 부모가 가질 수 있는 자식 노드의 개수
•
같은 수의 노드를 갖는 이진 트리보다 낮은 높이가 됨
•
이진 탐색트리의 확장된 형태
•
탐색트리의 제한을 따르되, 2개이상 m개 이하의 자식을 가질 수 있음
1.2. m원 탐색 트리의 제한 조건
1.
i=0, ···, n-2인 i에 대해 ki ＜ ki+1를 만족한다.
2.
i=0, ···, n-1인 i에 대해 pi가 가리키는 서브트리의 모든 키값은 ki의 키값보다 작다.
3.
pn이 가리키는 서브트리의 모든 키값은 kn-1의 키값보다 크다
4.
i=0, ···, n-1인 i에 대해 pi가 가리키는 서브트리는 m원 탐색 트리이다
1.3. 예시
•
잎 노드는 키 값으로만 표기
•
내부 노드 중 자식이 없는 포인터들은 표시 x
1.4. 노드 구조
structmnode {
int n;
struct rectype {
struct mnode *ptr;
int key;
struct rectype *addr;
}keyptrs[n-1];
struct mnode *keyptrn;
}
C
복사
•
탐색 연산
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) // skey 찾고자 하는 값
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]));
else
return(Search(skey,r→keyptrn));
}
}
C
복사
•
일반적으로 노드의 가지 개수가 많을수록(서브트리 수가 많을 수록), 최대 탐색 길이는 짧아짐
2. B 트리
2.1. 정의
•
정의
◦
인덱스 구조를 구현하는데 가장 일반적으로 사용하는 방법으로 차수가 m인 트리
•
특징
◦
m원 탐색 트리는 서브트리의 균형에 대해서는 특별히 제한하지 않음
◦
각 노드가 자식을 많이 갖게 하여 트리의 높이를 줄이고 전체적으로 균형을 유지한다면 탐색 성능을 더욱 향상할 수 있음
◦
m원 탐색트리를 개선한 B트리는 인덱스 구조를 구현하는데 가장 일반적으로 사용함
◦
차수 m인 B트리의 탐색 경로 길이는 같은 개수의 키를 가지는 이상적인 m원 탐색 트리보다 길 수 있지만 키값을 삽입/삭제할 때 B트리를 유지하는 것이 더 쉬움
2.2. 조건
1.
루트와 잎노드를 제외한 트리의 각 노드는 최소 [m/2]개의 서브트리를 갖는다.
2.
트리의 루트는 최소한 2개의 서브트리를 갖는다.
3.
트리의 모든 잎노드는 같은 레벨에 있다.
•
예시
2.3. B 트리 키 삽입 알고리즘
1.
삽입할 위치를 찾기 위해 노드의 키값을 왼쪽에서 오른쪽으로 탐색한다.
(B트리에서 모든 노드는 잎노드에서 삽입이 시작됨)
2.
노드에 빈자리가 있으면 삽입 후 종료한다.
3.
노드가 꽉 찼으면 노드를 2개로 분리하고 키와 포인터를 새 노드에 반씩 할당한다.
a.
잎노드 키값과 삽입노드 키값 중에서 중간값을 선택한다.
b.
선택된 중간값보다 작은 키값을 갖는 것은 왼쪽 노드에 넣고 큰 것은 오른쪽 노드에 넣는다.
c.
중간값을 가지는 노드의 키값과 포인터 를 부모노드에 삽입한다.만일 부모노드가 루트 노드면 두 노드를 가리키도록 (자식노드가 되도록)수정한다.
2.4. B 트리 키 삭제 알고리즘
•
잎 노드에서 삭제
◦
삭제할 키값을 포함한 노드를 찾는다.
1.
노드에서 키값을 삭제한다.
2.
필요하면 재배열한다.
•
내부 노드에서 삭제
◦
내부노드의 키값은 하위 노드에 대한 기준값(중간값)이기 때문에 삭제 시, 대체할 수 있는 적절한 값을 찾아야 한다. 보통 왼쪽 서브트리의 가장 큰 키값 또는 오른쪽 서브트리의 가장 작은 키값으로 대체할 수 있다.이들은 모두 잎노드에 위치한다.
1.
새로운 기준값(삭제된 자리에 올 키값)을 선택하여 해당 (잎)노드에서 삭제하고 그 값을 현재 키값을 삭제한 자리로 옮긴다.즉,대체한 것이다.
2.
기준값으로 대체하기 위해 키를 삭제한 잎노드가 정해진 개수의 키값을 갖지 않으면 트리를 재배열한다.
◦
재배열
1.
키값이 부족한 노드의 오른쪽 형제가 존재하고 키가 정해진 개수보다 많다면 왼쪽으로 회전한다.
a.
부모노드의 기준(키)값을 개수가 부족한 노드의 끝으로 이동한다. 즉,기준 값을 한 단계 아래로 내려 개수를 채운다.
b.
부모노드의 기준값을 오른쪽 형제의 첫 번째 키로 수정해 균형을 맞춘다.
2.
키값이 부족한 노드의 왼쪽 형제가 존재하고 키가 정해진 개수보다 많다면 오른쪽으로 회전한다.
a.
부모노드의 기준(키)값을 개수가 부족한 노드의 끝으로 이동한다. 즉,기준값을 한 단계 아래로 내려 개수를 채운다.
b.
부모노드의 기준값을 왼쪽 형제의 마지막 번째 키로 수정해 균형을 맞춘다.
3.
좌우 형제가 최소개수의 키를 가지고 있다면,좌우 형제를 합친다.
a.
부모노드의 기준 (키)값을 왼쪽 노드의 마지막에 복사한다.
b.
오른쪽 노드의 모든 키값을 왼쪽 노드로 옮긴다(왼쪽노드가 최대 개수의 키를 갖는다).
c.
키를 갖지 않는 오른쪽 노드는 삭제한다.
d.
부모노드가 루트면서 키를 더 이상 갖지 않으면 합쳐진 노드가 새로운 루트가 된다.그렇지 않고 부모노드의 키 개수가 정해진 개수보다 작으면 부모노드를 재배열 한다.
•
예시
3. B*, B+ 트리
3.1. B* 트리의 정의
•
노드의 약 2/3이상이 채워지는 B트리
•
노드가 꽉 차면 분리하지 않고,키와 포인터를 재배치하여 다른 형제 노드로 옮김
•
삽입/삭제 시 발생하는 노드 분리를 줄이려고 고안됨
3.2. B*트리의 정의
•
차수가 m인 B*트리는 다음 조건을 만족하는 B 트리이다.
1.
공집합이거나 높이가 1이상인 m원 탐색 트리이다.
2.
루트 노드는 2개 이상 2[(2m-2)/3]+1 개 이하의 자식노드 를 갖는다.
3.
내부노드는 최소한 (2m-1)/3개의 자식노드 를 갖는다.
4.
모든 잎노드는 동일한 레벨에 놓인다.
5.
포인터가 k개인 잎이 아닌 노드는 k-1개의 키를 갖는다.(루트노드 포함)
3.3. B+트리의 정의
•
탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만,전체 데이터를 차례로 처리하기는 불편함
◦
매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가면서 처리해야 함
•
B+ 트리는 인덱스된 순차 파일을 구성하는데 사용됨
•
B트리와 같이 각 노드의 키가 적어도 1/2이 채워져야 하는 점은 같음
•
잎노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다름
◦
잎노드의 마지막 포인터를 다음 키값을 갖는 노드를 가리킴
◦
순차 처리를 할 때는 이 포인터를 이용해서 (키값을 비교하지 않고) 차례로 다음 데이터에 접근해서 처리
•
모든 키값이 잎노드에 있고 그 키값에 대응하는 실제 데이터 (파일 내용)에 대한 주소를 잎노드만이 가지고 있음
◦
직접 탐색은 잎노드에 도달해야 종료
•
B+ 트리
◦
잎노드를 연결하는 포인터를 가짐
3.4. B+ 트리의 노드 삽입
•
잎 노드가 2개의 노드로 분리될 때는 키값 순서에 따라 배치하고 중간 키값은 부모노드에 올려놓음
•
새 노드는 순서에 맞게 잎노드에 삽입함
3.5. B+ 트리의 노드 삭제
•
키값을 잎노드에서 삭제할 때, 트리의 내부노드에서도 삭제할 필요는 없음
◦
그 키값이 직접 탐색을 위해 쓰이기 때문임
•
잎 노드에서만 데이터 삭제
4. 2-3 트리
4.1. 트리의 분류
•
이진트리
◦
힙
▪
최소, 최대 힙: 루트가 제일 작거나 제일 큼
▪
완전 이진 트리
•
높이가 k인 이진트리가 0레벨 부터 k-2레벨까지 다 채우고, 마지막 k-1레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진 트리
◦
이진 탐색 트리
▪
이진 트리이기만 하면됨 (포화 or 완전 or..)
▪
오른쪽은 나보다 큼, 왼쪽은 나보다 작음
▪
확장
•
AVL - 높이 맞춤
•
BB - 무게를 맞춤
•
Splay - 휴리스틱 알고리즘
•
멀티웨이 트리
◦
m원 멀티웨이 트리
◦
B 트리 - 최소 1/2까지 채움
▪
B* 트리 - 최소 2/3까지 채움
▪
B+ 트리 - 순차적으로 데이터 접근. 잎 노드 연결
▪
2-3 트리
4.2. 정의
•
차수가 2 또는 3인 내부 노드를 갖는 탐색 트리
•
2-노드와 3-노드만으로 구성되는 특수한 형태의 B트리임
•
2-노드 혹은 3-노드라는 제약이 내부 노드에만 해당함
→ 모든 잎 노드는 같은 레벨에 있어야 한다는 제약만 존재함
4.3. 조건
•
각각의 내부 노드는 2-노드이거나 3-노드이다
◦
2-노드: 1개의 키 값
◦
3-노드: 2개의 키 값
•
2-노드 (lkey)
◦
lchild (왼쪽 자식)
▪
루트가 lchild인 모든 2-3서브 트리 키 < lkey
◦
mchild (중간 자식)
▪
루트가 mchild인 모든 2-3서브 트리 키 > lkey
•
3-노드 (lkey, rkey)
◦
lkey < rkey
◦
lchild (왼쪽 자식)
▪
루트가 lchild인 모든 2-3서브 트리 키 < lkey
◦
mchild (중간 자식)
▪
루트가 mchild인 모든 2-3서브 트리 키 > lkey
▪
루트가 mchild인 모든 2-3서브 트리 키 < rkey
◦
rchild (오른쪽 자식)
▪
루트가 rchild인 모든 2-3 서브 트리 데이터 > rkey.
•
모든 잎 노드는 같은 레벨에 있다.
•
예시
4.4. 2-3트리의 탐색
typedef struct two_three *two_three_ptr;
struct two_three {
int lkey,rkey;
two_three_ptr lchild, mchild, rchild;
};
two_three_ptr search23(two_three_ptr t,int x){
while(t)
switch(compare(x,t)){ // 검색키 x와 노드 t에 있는 키값을 비교
case1 : t = t -> lchild ; // x가 노드 t의 왼쪽 키값(lchild)보다 작은 경우
break;
case2 : t = t -> mchild ; // x가 노드t의 왼쪽 키값보다 크고 오른쪽 키값보다 작은경우
break;
case3 : t = t -> rchild ; // x가 노드 t의 오른쪽 키값(rchild)보다 큰 경우
break;
case4 : return(t); // x가 노드 t의 키값들 중 어느 하나와 같은 경우
}
return(NULL);
}
C
복사
4.5. 2-3 트리의 삽입
•
키값 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){
fprintf(stderr,"The keyiscurrentlyinthetree\n");
exit(1); }
q=NULL;
for(;;)
if(p->rkey ==INT_MAX){
put_in(&p,y,q);
break;}
else{
split(p,&y,&q);
if(p==*t){
new_root(t,y,q);
break;}
else
p=delete();
}
}
}
C
복사
4.6. 2-3트리의 삭제
•
2-3 트리의 삭제에서 잎 노드가 아닌 노드의 키를 삭제하면 그곳을 다른 키로 대체해야 함
•
일반적으로 삭제한 키의 왼쪽 서브트리에서 가장 큰 키값이나 오른쪽 서브트리에서 가장 작은 키값을 선택하여 대체함
•
예시
◦
키 값 9의 삭제
◦
키 값 7의 삭제
◦
키 값 10의 삭제
5. 2-3-4 트리
5.1. 2-3-4트리의 정의
•
2-3트리를 확장하여 4개의 자식을 가진 4-노드를 허용하는 탐색 트리
•
2-3-4트리는 2-3트리보다 삽입과 삭제가 용이함
•
2-3-4트리에서는 2-노드와 3-노드에 대한 트리 재구성 확률이 2-3트리에서보다 작음
◦
삽입 및 삭제 연산을 수행하는 데 더 효율적임
각의 내부 노드는 2-노드이거나 3-노드이다
•
2-노드: 1개의 키 값
•
3-노드: 2개의 키 값
•
2-노드 (lkey)
◦
lchild (왼쪽 자식)
▪
루트가 lchild인 모든 2-3서브 트리 키 < lkey
◦
mchild (중간 자식)
▪
루트가 mchild인 모든 2-3서브 트리 키 > lkey
•
3-노드 (lkey, rkey)
◦
lkey < rkey
◦
lchild (왼쪽 자식)
▪
루트가 lchild인 모든 2-3서브 트리 키 < lkey
◦
mchild (중간 자식)
▪
루트가 mchild인 모든 2-3서브 트리 키 > lkey
▪
루트가 mchild인 모든 2-3서브 트리 키 < rkey
◦
rchild (오른쪽 자식)
▪
루트가 rchild인 모든 2-3 서브 트리 데이터 > rkey.
5.2. 2-3-4트리의 조건
•
각각의 내부노드
◦
2-노드 or 3-노드 or 4-노드
▪
2-노드: 1개의 키 값
▪
3-노드: 2개의 키 값
▪
4-노드: 3개의 키 값
•
lchild, lmchild는 각각 2-노드의 왼쪽 자식 노드 및 좌중간 자식 노드이라 하고,lkey를 키값라고 가정.
◦
루트가 lchild인 모든 2-3-4 서브트리 키값은 lkey보다 작음
◦
루트가 mchild인 모든 2-3-4서브트리 키값은 lkey보다 크다.
•
lchild, lmchild 및 rmchild를 각각 3-노드의 왼쪽 자식 노드,좌중간 자식 노드 및 우중간 자식 노드라 하고 lkey,mkey를 이 노드의 키값이라 가정
a. lkey < mkey
b. 루트가 lchild인 모든 2-3-4 서브트리 키값은 lkey 보다 작다.
c. 루트가 lmchild인 모든 2-3-4 서브트리 키값은 lkey 보다 크고 mkey 보다 작다.
d. 루트가 rmchild인 모든 2-3-4 서브트리 키 값은 mkey보다 크다.
•
lchild,lmchild,rmchild및 rchild를 각각 4-노드의 왼쪽, 좌중간,우중간 및 오른쪽 자식이라 하고,lkey,mkey및 rkey를 이 노드의 키값이라 가정
a. lkey < mkey < rkey
b. 루트가 lchild인 모든 2-3-4 서브트리 키값은 lkey 보다 작다.
c. 루트가 lmchild인 모든 2-3-4 서브트리 키값은 mkey보다 작고 lkey 보다 크다.
d. 루트가 rmchild인 모든 2-3-4 서브트리 키값은 rkey 보다 작고 mkey 보다 크다.
e. 루트가 rchild인 모든 2-3-4 서브트리 키값은 rkey보다 크다.
•
모든 잎 노드는 같은 레벨에 있다.
•
예시
5.3. 2-3-4 트리의 삽입
•
2-노드와 3-노드에 대한 트리 재구성의 확률이 2-3트리에서 보다 작음
•
삽입/삭제 연산이 효율적임
•
삽입 연산 시 문제가 되는 4-노드 는 그 위치에 따라 세 가지 경우로 구분하여 분리함
1.
4-노드가 루트인 경우
2.
4-노드가 부모의 2-노드인 경우
3.
4-노드의 부모가 3-노드인 경우
5.4. 2-3-4트리의 삭제 연산
•
잎 노드에 있는 키 값은 단순히 삭제하면 됨
6. 레드 블랙 트리
6.1. 레드 블랙 트리의 정의
•
효율적인 기억 장소 사용을 위하여 2-3-4트리를 이진 트리로 나타낸 탐색 트리
•
레드 간선과 블랙 간선의 서브트리 포인터를 가짐
•
레드 간선
◦
2-3-4트리의 한 노드 내에 있던 노드의 관계
•
블랙 간선
◦
2-3-4트리의 부모-자식 관계
•
레드 블랙 트리의 탐색 방법은 보통의 이진 탐색 트리의 탐색 알고리즘과 동일함
6.2. 3-노드에 대응하는 레드 블랙 트리
•
레드 간선 - 점선
•
블랙 간선 - 실선
6.2. 4노드에 대응하는 레드 블랙 트리
•
예시
6.3. 2-3-4 트리를 레드 블랙 트리로 변환한 결과
•
예시
