Tree(트리) - 2 [Binary Search Tree]

6. 이진 탐색 트리

 - 이진 트리 기반의 탐색을 위한 자료 구조이다.

 - 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미

 - 레코드는 하나 이상의 필드(field)로 구성된다.

 - 레코드들의 집합을 테이블(table)이라고 한다.

 - 레코드들을 구분할 수 있는 값을 주요 키(primary key)라고 한다.

 - 이진 탐색 트리는 위와 같은 탐색 작업을 효율적으로 하기 위한 자료 구조이다.

 

 1) 이진 탐색 트리의 정의

  - 모든 노드의 키는 유일하다.

  - 왼쪽 서브 트리의 키들은 루트의 키보다 작다.

  - 오른쪽 서브 트리의 키들은 루트의 키보다 크다.

  - 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

 2) 순환적인 탐색 함수

TreeNode *search(TreeNode *node, int key) 
{ 
	if( node == NULL ) return NULL; 
	if( key == node->key ) return node; 
	else if( key < node->key ) 
	    	return search(node->left, key); 
	else 
		return search(node->right, key); 
}

 

 3) 반복적인 탐색 함수

TreeNode *search(TreeNode *node, int key) 
{    
	while(node != NULL){ 
	    if( key == node->key ) return node; 
	    else if( key < node->key ) 
		node = node->left; 
	    else 
		node = node->right; 
    } 
    return NULL; 	// 탐색에 실패했을 경우 NULL 반환
}

 ※ 효율성을 따지면 반복적인 함수가 훨씬 우수하다.

 ※ 함수의 매개 변수 node를 직접 사용하였는데, 사실 매개 변수는 원본 포인터의 복사본이므로 변경하여도 호출한 함수에는 별 영향이 없다.

 

 4) 이진 트리 삽입 연산

void insert_node(TreeNode **root, int key)
{
	TreeNode *p, *t; // p는 부모노드, t는 현재노드 
	TreeNode *n;	    // n은 새로운 노드

	t = *root;
	p = NULL;
	// 탐색을 먼저 수행 
	while (t != NULL) {
		if (key == t->key) return;
		p = t;
		if (key < t->key) t = t->left;
		else t = t->right;
	}
	// key가 트리 안에 없으므로 삽입 가능
	n = (TreeNode *)malloc(sizeof(TreeNode));
	if (n == NULL) return;
	// 데이터 복사
	n->key = key;
	n->left = n->right = NULL;
	// 부모 노드와 링크 연결
	if (p != NULL)
		if (key < p->key)
			p->left = n;
		else p->right = n;
	else *root = n;
}

 

 5) 이진 트리 삭제 연산

  (1) 단말 노드일 경우

  (2) 하나의 서브 트리만 가지고 있는 경우

  (3) 두 개의 서브 트리를 가지고 있는 경우 : 가장 값이 비슷한 노드를 후계자로 선택하는데, 왼쪽 서브 트리의 가장 오른쪽 값 or 오른쪽 서브 트리의 가장 왼쪽 값

void delete_node(TreeNode **root, int key)
{
	TreeNode *p, *child, *succ, *succ_p, *t;

	// key를 갖는 노드 t를 탐색, p는 t의 부모노드
	p = NULL;
	t = *root;
	// key를 갖는 노드 t를 탐색한다.
	while( t != NULL && t->key != key )
	{
		p = t;
		t = ( key < t->key ) ? t->left : t->right;
	}
	// 탐색이 종료된 시점에 t가 NULL이면 트리안에 key가 없음
	if( t == NULL )
	{ 	// 탐색트리에 없는 키
		printf("key is not in the tree");
		return;
	}
	// 첫번째 경우: 단말노드인 경우
	if( (t->left==NULL) && (t->right==NULL) )
	{ 
		if( p != NULL ){
			// 부모노드의 자식필드를 NULL로 만든다.
			if( p->left == t )	 
				p->left = NULL;
			else   p->right = NULL;
		}
		else	// 만약 부모노드가 NULL이면 삭제되는 노드가 루트
			*root = NULL;
	}
	// 두번째 경우: 하나의 자식만 가지는 경우
	else if((t->left==NULL)||(t->right==NULL))
	{
		child = (t->left != NULL) ? t->left : t->right;
		if( p != NULL ){
			if( p->left == t )	// 부모를 자식과 연결 
				p->left = child;
			else p->right = child;
		}
		else   // 만약 부모노드가 NULL이면 삭제되는 노드가 루트
			*root = child;
	}
	// 세번째 경우: 두개의 자식을 가지는 경우
	else
	{		
		// 오른쪽 서브트리에서 후계자를 찾는다.
		succ_p = t;
		succ = t->right;
		// 후계자를 찾아서 계속 왼쪽으로 이동한다.
		while(succ->left != NULL){
			succ_p = succ;
			succ = succ->left;
		}
		// 후속자의 부모와 자식을 연결 
		if( succ_p->left == succ )
			succ_p->left = succ->right;
		else 
			succ_p->right = succ->right;
		// 후속자가 가진 키값을 현재 노드에 복사
		t->key = succ->key;
		// 원래의 후속자 삭제
		t = succ;
	}
	free(t);
}

 

 

[Reference]

• 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년