11-1. 이진 탐색 트리(binary search tree) 응용

주요 용어

이진 탐색 트리(binary search tree) : 빠르게 탐색할 수 있도록 구성한 이진트리

키 : 각 노드를 식별하기 위해서는 별도의 간단한 이름을 붙여준 것

Splay 트리 : 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 이진 탐색 트리

AVL 트리 : 노드의 왼쪽 서브 트리 높이와 의 오른쪽 서브트리 높이가 최대 1만큼 차이가 난다는 조건을 만족하는 트리

트리의 높이 : 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값으로 루트로부터 잎까지 가장 긴 경로 길이

트리의 무게 : 트리에 속한 잎 노드의 개수

무게가 균형 잡힌 트리 : 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리

 

 

 

01. 이진 탐색 트리

이진 탐색 트리 : 트리에서 특정 데이터의 효과적인 검색에 위해 제한점을 가지는 이진트리

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

- 탐색에 최적화된 이진트리

- 키 : 이진트리의 노드의 데이터 (노드를 특정할 수 있는 값

 

♦ 노드 vi의 키를 k_i 라 할 때 각 노드 v_i 가 다음을 만족하는 이진트리를 이진 탐색 트리(BS트리)라 함

① v_i의 왼쪽 서브 트리에 있는 모든 노드의 키값은 v_i의 키값보다 작다.

② v_i의 오른쪽 서브 트리에 있는 모든 노드의 키값은 v_i의 키값보다 크다.

♦ 같은 순서 데이터에 대해서 BS트리를 다양하게 만들 수 있음

 

BS트리를 위한 노드 정의

struct KNode {
	struct KNode *left;		//왼쪽 자식을 위한 포인터
	char key[10];			//키값을 위한 문자 배열
	int info;				//데이터 필드
	struct KNode *right;	//오른쪽 자식을 위한 포인터
}

BS트리의 중위 순회

void Inorder(struct KNode *rootptr){
	if(rootptr != null){
		Inorder(rootptr -> left);
		printf("%d",rootptr->info);
		Inorder(rootptr->right);	 }		 }

 

 

BS트리에서 키값이 k인 노드를 찾는 과정

① 트리가 비어 있다면 탐색 실패, 아니면 k와 현재 루트 노드의 키값 k_i를 비교한다.

② k = k_i이면 탐색 성공, 이때 찾은 정점은 v_i다.

③ k < k_i 이면 v_i 의 왼쪽 서브 트리를 탐색한다. 즉, v_i = v_i,left 로 바꾸고 ①로 간다.

④ k > k_i 이면 v_i 의 오른쪽 서브 트리를 탐색한다. 즉, v_i = v_i,right 로 바꾸고 ①로 간다.

 

 

BS트리의 노드 탐색

struct KNode *Search(chark[], struct KNode *r){
If(r==null)
return(null);
else
If(strcmp(k , r->key)==0)
return(r);
else if(strcmp(k , r-> key)<0)		//k < r-> key
	return(Search(k , r-> left));
		else return(Search(k , r->right)); 	}

 

BS트리의 노드 삽입 연산

① 트리가 비어 있다면 키 k를 가지는 노드를 삽입한다. 그렇지 않으면 k와 현재 루트 노드의 키 k_i를 비교한다.

② k =k_i이면 멈춘다.

③ k < k_i이면 v_i의 왼쪽 서브 트리에 삽입해야 하므로, v_i = v_i→ left 로 바꾸고 ①로 간다.

④ k > k_i이면 v_i의 오른쪽 서브 트리에 삽입해야 하므로, v_i = v_i→ right로 바꾸고 ①로 간다

 

BS트리의 노드 삽입 연산

struct KNode *Insert(struct KNode *newptr, struct KNode *r){
	if(r==null)
		return(newptr);
	else
		if(strcmp(newptr->key ,r->key)==0)
			DUPLICATE_ENTRY();
		else
			if(strcmp(newptr->key,r->key)<0) 
           		r->left = Insert(newprt,r->left);
			else 
            	r->right = Insert(newptr,r->right);
	return(r);								 }

 

키가 A인 노드와 F인 노드의 삽입

- 자식을 하나만 갖는 노드를 삭제하는 경우, [삭제한 노드를 가리키던 포인터]가 [그 노드의 null이 아닌 서브트리의 루트]를 가리키게 할당함

 

- 두 개의 자식 노드를 가지는 노드는 삭제 시 항상 특정 방향의 자식 노드를 올리는 방법으로 구현

(즉, 항상 오른쪽(혹은 왼쪽) 자식 노드를 삭제 위치로 이동)