[자료구조] 멀티웨이 탐색 트리

m원 탐색 트리

• 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리 → 같은 수의 노드를 갖는 이진 탐색 트리보다 낮은 높이의 m원 트리
• 이진 탐색 트리의 확장된 형태임
• 탐색 트리의 제한을 따르면서, 2개 이상 ~ m개 이하의 자식 노드를 가질 수 있음

노드의 구조

struct Mnode {
	int n;
	struct Rectype {
		struct Mnode * ptr,
		int key;
		struct Rectype *addr,
	} keyptrs[n-1];
	struct Mnode *keyptrn;
}

탐색 연산

일반적으로 노드의 가지 개수가 많을수록(서브 트리가 많을수록) 최대 탐색 시간이 짧아짐(트리의 깊이가 얕으므로 더 빨리 찾을 수 있음)

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 && key == 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));
	}
}

B 트리

• m원 탐색 트리는 서브 트리의 균형에 대해서는 특별히 제한하지 않음
• 각 노드가 자식을 많이 갖게 하여 트리의 높이를 줄이고 전체적으로 균형을 유지한다면 탐색 성능을 더욱 향상할 수 있음
• 인덱스 구조를 구현하는데 일반적으로 사용
• 조건
  • 루트와 잎 노드를 제외한 트리의 각 노드는 최소 [m/2] 개의 서브 트리를 갖음
  • 모든 잎 노드는 같은 레벨에 있다
• 키를 삽입하는 알고리즘

1. 삽입할 위치를 찾기 위해 노드의 키 값을 왼쪽에서 오른쪽으로 탐색
	(B 트리에서 모든 노드는 잎 노드에서 삽입 시작)
2. 노드에 빈자리가 있으면 삽입 후 종료
3. 노드가 꽉 찼으면 노드를 2개로 분리하고 키와 포인터를 새 노드에 반씩 할당
	3-1. 잎 노드 키 값과 삽입 노드 키 값 중에서 중간 값을 선택
	3-2. 선택된 중간 값보다 작은 키 값을 갖는 것은 왼쪽 노드에 넣고 큰 것은 오른쪽 노드에 삽입
	3-3. 중간 값을 가지는 노드의 키 값과 포인터를 부모 노드에 삽입
		만일 부모 노드가 루트 노드면 두 노드를 카리키도록 (자식 노드가 되도록) 수정

• 키를 삭제하는 알고리즘 - 잎 노드에서 삭제

1. 삭제할 키 값을 포함한 노드를 찾는다.
2. 노드에서 키 값을 삭제한다.
3. 필요하면 재배열한다.

• 키를 삭제하는 알고리즘 - 내부 노드에서 삭제 내부 노드의 키 값은 하위 노드에 대한 기준값(중간값)이기 때문에 삭제 시, 대체할 수 있는 적절한 값을 찾아야 한다. 보통 왼쪽 서브 트리의 가장 큰 값 또는 오른쪽 서브 트리의 가장 작은 키 값으로 대체할 수 있다.

1. 새로운 기준값(삭제된 자리에 올 키 값)을 선택하여 해당 (잎) 노드에서 삭제하고 그 값을 
	현재 키 값을 삭제한 자리로 옮긴다. 즉, 대체한 것이다.
2. 기준 값으로 대체하기 위해 키를 삭제한 잎 노드가 정해진 개수의 키 값을 갖지 않으면 
	트리를 재배열한다.
	2-1. 키 값이 부족한 노드의 오른쪽 형제가 존재하고 키가 정해진 최소 개수보다 많다면
		왼쪽으로 회전한다.
		2-1-1. 부모 노드의 기준(키) 값을 개수가 부족한 노드의 끝으로 이동한다. 즉,
			기준 값을 한 단계 아래로 내려 개수를 채운다.
		2-1.2. 부모 노드의 기준 값을 오른쪽 형제의 첫 번째 키로 수정해 균형을 맞춘다.
	2-2. 키 값이 부족한 노드의 왼쪽 형제가 존재하고 키가 정해진 최소 개수보다 많다면
		오른쪽으로 회전한다.
		2-2-1. 부모 노드의 기준(키) 값을 개수가 부족한 노드의 끝으로 이동한다.
		2-2-2. 부모 노드의 기준 값을 왼쪽 형제의 마지막 키로 수정해 균형을 맞춘다.
	2-3. 좌우 형제가 최소 개수의 키를 가지고 있다면 좌우 형제를 합친다.
		2-3-1. 부모 노드의 기준(키) 값을 왼쪽 노드의 마지막에 복사한다.
		2-3-2. 오른쪽 노드의 모든 키 값을 왼쪽 노드로 옮긴다.
			(왼쪽 노드가 최대 개수의 키를 갖는다)
		2-3-3. 키를 갖지 않는 오른쪽 노드는 삭제한다.
		2-3-4. 부모 노드가 루트이면서 키를 더 이상 갖지 않으면 합쳐진 노드가 새로운
			루트가 된다. 그렇지 않고 부모 노드의 키 개수가 정해진 최소 개수보다 작으면
			부모 노드를 재배열한다.

B* 트리

• 노드의 약 2/3 이상이 채워지는 B트리
• 노드가 꽉 차면 분리하지 않고 키와 포인터를 재배치하여 다른 형제 노드로 옮김 → B 트리와 동일한 수의 노드를 갖는다면 높이가 낮고, 삽입/삭제 시 발생하는 노드 분리를 줄이려고 고안
• 차수가 m인 B* 트리의 조건
  • 공집합이거나 높이가 1 이상인 m원 탐색 트리
  • 루트 노드는 2개 이상 2[(2m-2)/3]+1 개 이하의 자식 노드를 갖는다
  • 내부 노드는 최소한 [(2m-1)/3]개의 자식 노드를 갖느다
  • 모든 잎 노드는 동일한 레벨에 놓인다
  • 포인터가 k개이면서 잎 노드가 아닌 노드는 k-1개의 키를 갖는다(루트 노드 포함)

B+ 트리

• 탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만, 전체 데이터를 차례로 처리하기는 불편함
• 매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가면서 처리해야 함
• 인덱스된 순차 파일을 구성하는 데 사용
• 각 노드의 키가 적어도 1/2 채워져야 함
• 잎 노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다름
• 잎 노드의 마지막 포인터를 다음 키 값을 갖는 노드를 가리킴
• 순차 처리를 할 때는 이 포인터를 이용해서 (키 값을 비교하지 않고) 차례로 다음 데이터에 접근해서 처리
• 모든 키 값이 잎 노드에 있고 그 키 값에 대응하는 실제 데이터에 대한 주소를 잎 노드만이 가지고 있음
• 직접 탐색은 잎 노드에 도달해야 종료
• 노드 삽입
  • 잎 노드가 2개의 노드로 분리될 때는 키 값 순서에 따라 배치하고 중간 키 값은 부모 노드에 올려놓음
  • 새 노드는 순서에 맞게 잎 노드에 삽입
• 노드 삭제: 키 값을 잎 노드에서 삭제할 때, 키 값이 직접 탐색에 쓰이기 때문에 트리의 내부 노드에서도 삭제할 필요는 없음

2-3 트리

• 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리
• 2-노드(2개의 자식노드; 차수가 2)와 3-노드(3개의 자식노드; 차수가 3)만으로 구성되는 특수한 형태의 B트리
• 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)) {
			case 1: t = t -> lchild;
				break;
			case 2: t = t -> mchild;
				break;
			case 3: t = t -> rchild;
				break;
			case 4: return (t);
		}
	return(NULL);
}

• 트리의 삽입

void insert23(two_trhee_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) {
			printf(stderr, "The Key is currently in the tree₩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();
			}
	}
}

• 트리의 삭제
  • 2-3 트리의 삭제에서 잎 노드가 아닌 노드의 키를 삭제하면 그 곳을 다른 키로 대체해야 함
  • 일반적으로 삭제한 키의 왼쪽 서브 트리에서 가장 큰 키 값이나 오른쪽 서브 트리에서 가장 작은 키 값을 선택하여 대체함
  • 회전: 3-노드인 형제가 있는 경우, 키 값 중 하나를 부모로 올리고 대신 부모로부터 키 값 하나를 가져다 빈 노드를 채우는 것
  • 결합: 하나의 노드를 삭제하고 형제와 합치는 것

2-3-4 트리

• 2-3 트리를 확장하여 4개의 자식을 가진 4-노드를 허용하는 탐색 트리
• 2-3 트리보다 삽입과 삭제가 용이함
• 2-노드과 3-노드에 대한 트리 재구성 확률이 2-3 트리에서 보다 작기 때문에 삽입 및 삭제 연산을 수행하는 데 더 효율적임
• 2-3-4 트리의 조건
  • lchild, mchild는 각각 2-노드의 왼쪽 자식 노드 및 좌중간 자식 노드라 하고, lkey를 키 값이라고 하면, 루트가 lchild인 모든 2-3-4 서브트리 키 값은 lkey보다 작고, 루트가 mchild인 모든 2-3-4 서브트리 키 값은 lkey보다 크다
  • lchild, 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보다 크다
  • 모든 잎 노드들은 같은 레벨에 있다
• 삽입 연산
  • 2-노드와 3-노드에 대한 트리 재구성의 확률이 2-3 트리에서 보다 작기 때문에 삽입/삭제 연산이 효율적임
  • 삽입 연산의 문제가 되는 4-노드는 그 위치에 따라 다음과 같이 분류
    • 4-노드가 루트인 경우
    • 4-노드의 부모가 2-노드인 경우
    • 4-노드의 부모가 3-노드인 경우
• 삭제 연산: 잎 노드에 있는 키 값은 단순히 삭제하면 됨

레드 블랙 트리

• 효율적인 기억 장소 사용을 위하여 2-3-4 트리를 이진 트리로 나타낸 탐색 트리
• 레드 간선: 2-3-4 트리의 한 노드 내에 있던 노드의 관계
• 블랙 간선: 2-3-4 트리의 부모-자식 관계
• 레드 블랙 트리의 탐색 방법은 보통의 이진 탐색 트리의 탐색 알고리즘과 동일함