12-1. 멀티웨이 탐색 트리

주요용어

m원 탐색 트리 : 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리

B트리 : 인덱스 구조를 구현하는데 가장 일반적으로 사용하는 방법으로 차수가 m인 트리

B* : 노드의 약 2/3 이상이 차야하는 B 트리

B+ : 모든 키값이 잎 노드에 있고 그 키값에 대응하는 실제 데이터에 대한 주소를 잎 노드만이 가지고 있어서 인덱스된 순차 파일을 구성하는데 사용하는 트리

 

 

01. m원 탐색 트리

이진 탐색 트리(BS트리 ; binary search tree)

- 트리에서 특정 데이터를 검색하고,노드의 삽입/삭제 연산이 자주 발생하는 응용 문제에 가장 효과적인 이진 트리

- ‘왼쪽’과 ‘오른쪽’이라는 방향성을 가지며 다루기가 매우 편리함

- 부모노드를 중심으로 [부모보다 큰 데이터 노드]와 [부모보다 작은 데이터 노드]로 구분됨

- 일반적으로 노드의 개수가 많아지면 트리의 높이가 커지게 됨

- BS트리가 2원(2-way)탐색 트리임

 

m원 탐색 트리의 정의

- 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리 

  → 같은 수의 노드를 갖는 이진트리보다 낮은 높이의 m원 트리

- 이진 탐색 트리의 확장된 형태임

- 탐색 트리의 제한을 따르되 2개 이상(m개 이하) 자식을 가질 수 있음

 

 

m원 탐색 트리의 제한 조건

1. 노드구조는 다음과 같다. 여기서 P₀, P₁, .......... , P_n 은 서브트리에 대한 포인터이고

k₀,.....,k_n-1은 키값이다. 또한, n ≤ m-1이 성립한다. 

2. i = 0, ....., n-2 인 i에 대해 k_i < k_i+1을 만족한다.

3. i = 0, ....., n-1 인 i에 대해 p_i가 가리키는 서브트리의 모든 키값은 k_i의 키값 보다 작다.

4. P_n이 가리키는 서브트리의 모든 키값은 k_n-1의 키값보다 크다.

5. i = 0, ...... , n 인 i에 대해 P_i가 가리키는 서브트리는 m원 탐색 트리이다.

 

 

m원 탐색 트리 ­ 3원 탐색 트리

- 잎노드는 키값으로만 표기하고 내부노드 중 자식이 없는 포인터들은 표시하지 않음

 

m원 탐색 트리 노드의 구조

structmnode {
	int n;
	struct rectype {
		struct mnode *ptr;
		int key;
		struct rectype *addr;
	}keyptrs[n-1];
	struct mnode *keyptrn;	 }

 

m원 탐색 트리의 탐색 연산 ­ 키 값을 찾는 연산

 

struct mnode *nodeptr ;
struct rectype *recptr ;
struct rectype *Search(intskey ,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]));
				else
					return(Search(skey,r→keyptrn));	}	}

 

m원 탐색 트리의 탐색

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

- 예를 들어,키가 255개인 경우 4원 트리로 구성하면 최대 경로 길이가 4가 됨