[자료구조] - 탐색 /순차탐색/이진탐색/AVL트리/2-3트리

탐색이란 ...

탐색키 : 항목과 항목을 구별시켜주는 키

탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는것!!!

정렬되지 않은 배열에서의 탐색

• 순차탐색

  항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법 -> O(n)

int seq_search(int *list , int key, int low, int high)	// low 부터 high까지 범위
{
	int i;

	for (i = low; i <= high; i++)
		if (list[i] == key)
			return i;  // 탐색에 성공하면 키 값의 인덱스 반환 
	return -1;    // 탐색에 실패하면 -1 반환 
}

정렬된 배열에서의 탐색

• 이진 탐색

  배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄이는 방법. 찾고자하는 항목이 속해있지 않은 부분은 전혀 고려할 필요 없음.

  • 주의 사항 :
    탐색하기전 배열이 반드시 정렬되어 있어야 하고, 따라서 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 고정된 데이터에 대한 탐색에 적합하다.

  이진 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄인다. 더이상 줄일 수 없을때 : n/$2^k$=1
  따라서 k = log2n -> O(log2n)

int binsearch(int list[], int n, int searchnum)
{   
	int left = 0;
	int right = n-1;
	int middle;   

	count = 0;
	while( left <= right ){		// 아직 숫자들이 남아 있으면
	   count++;
	   middle = (left+right)/2;			
	   if( searchnum == list[middle]){   
			return middle;
	   }
	   else if( searchnum < list[middle] ){
			right = middle-1;
	   }
	   else {
			left = middle+1; break;	
	   }
	}   
	return -1;		// 발견되지 않음 
}

이진 탐색과 이진 탐색 트리

이진 탐색의 단점 : 배열이 정렬되어 있으므로 삽입,삭제가 힘듬-> 앞뒤의 원소들을 이동시켜야 하니깐

따라서....

삽입, 삭제가 심하지 않은 정적인 자료를 대상으로 탐색 --> 이진 탐색
삽입, 삭제가 빈번히 이루어진다면 --> 무조건 이진 탐색 트리

but 이진 탐색 트리가 최악의 경우, 즉 균형 트리가 아닌 경우 탐색의 시간 복잡도는 O(n)으로 up!
이를 보안하기 위해 스스로 균형 트리를 만드는 AVL트리가 있다!!!

AVL트리

각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리

• 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다.
• 따라서 탐색, 삽입, 삭제 모두 O(log2n)이다.

균형 인수 : (왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이)
모든 노드의 균형 인수가 +-1이하면 AVL트리이다.

균형 트리로 되돌리는 4가지 경우

• LL타입 : 노드들을 오른쪽으로 회전
• RR타입 : 노드들을 외쪽으로 회전
• RL타입 : 노드들을 오른쪽 -> 왼쪽으로 회전
• LR타입 : 노드들을 왼쪽 -> 오른쪽으로 회전

AVL트리의 정의

이진 탐색 트리의 일종이므로 데이터 필드, 오른쪽, 왼쪽 자식을 가리키는 포인터

#include<stdio.h>
#include<stdlib.h>

// AVL 트리 노드 정의
typedef struct AVLNode
{
	int key;
    struct AVLNode *left;
    struct AVLNode *right;
} AVLNode;

rotate_right(): 오른쪽으로 회전시키는 함수

AVLNode *rotate_right(AVLNode *parent)
{
	AVLNode* child = parent->left;
    parent->left = child->right;
    child->right = parent;
    
    return child; // 새로운 루트를 반환
}

rotate_left(): 왼쪽으로 회전시키는 함수

AVLNode *rotate_left(AVLNode *parent)
{
	AVLNode* child = parent->right;
    parent->right = child->left;
    child->left = parent;
    
    return child; // 새로운 루트를 반환
}

트리의 높이 계산

왼쪽 서브 트리, 오른쪽 서브 트리에 대해 순환호출하여 각각의 높이를 구한다음 더 큰 값에 1(root노드)를 더하면 트리의 높이가 된다.

//트리의 높이를 반환
int get_height(AVLnode *node)
{
	int height = 0;
    if(node != NULL)
       height = 1 + max(get_height(node->left), get_height(node->right));
      
    return height;
}

노드의 균형 인수 반환

왼쪽 서브트리의 높이에서 오른쪽 서브 트리의 높이를 빼면 구할 수 있다.

// 노드의 균형인수를 반환
int get_balance(AVLNode * node)
{
	if(node == NULL) return 0;
   
   return get_height(node->left) - get_height(node->right)
}

새로운 노드 추가 함수

새로운 노드가 추가되면 트리의 균형이 깨질 수 있으므로 위의 4타입에 맞게 회전을 하여 트리의 균형을 맞춘다.

AVLNode* insert(AVLnode* node, int key)
{
	//이진 탐색 트리의 노드 추가 수행
    if(node == NULL)
       return(create_node(key)) // 이진 탐색 트리와 같이 탐색이 실패한 위치가 삽입 위치가 됨
       
    if(key < node->key)
       node->left = insert(node->left, key);
    else if (key > node ->key)
       node->right = insert(node->right, key);
    else 
       return node;	//  동일한 키는 허용되지 않음
    
    // 노드들의 균형인수 재계산
    int balance = get_balance(node);
    
    //LL 타입 처리
    if(balance > 1 && key < node->left->key) // 새로운 노드가 왼쪽 자식의 왼쪽에 추가 되었으면 LL타입이다.
        return rotate_right(node); // 오른쪽으로 회전
    
    //RR 타입 처리
    if(balance < -1 && key > node->right->key)// 새로운 노드가 오른쪽 자식의 오른쪽에 추가 되었으면 RR타입이다.
    	return rotate_left(node); // 왼쪽으로 회전
        
    //LR 타입 처리
    if(balance > 1 && key > node->left->key) // 새로운 노드가 왼쪽 자식의 오른쪽에 추가되었으면 LR타입이다.
    {
		node->left = rotate_left(node->left); 
        return rotate_right(node); // 왼쪽 회전 -> 오른쪽 회전
    }
    
    //RL 타입 처리
    if(balance < -1 && key < node->right->key) // 새로운 노드가 오른쪽 자식의 왼쪽에 추가되었으면 RL타입이다.
    {
		node->right = rotate_right(node->right);
        return rotate_left(node);	// 오른쪽 회전 -> 왼쪽 회전
    }
   	
    return node; // 변경된 노드 반환
}

전체 확인 프로그램

#include<stdio.h> 
#include<stdlib.h> 
#define MAX(a, b) (a)
// AVL 트리 노드 정의
typedef struct AVLNode
{
	int key;
	struct AVLNode *left;
	struct AVLNode *right;
} AVLNode;

// 트리의 높이를 반환
int get_height(AVLNode *node)
{
	int height = 0;

	if (node != NULL)
		height = 1 + max(get_height(node->left),
			get_height(node->right));

	return height;
}
// 노드의 균형인수를 반환
int get_balance(AVLNode* node)
{
	if (node == NULL) return 0;

	return get_height(node->left)
		- get_height(node->right);
}

// 노드를 동적으로 생성하는 함수
AVLNode* create_node(int key)
{
	AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
	node->key = key;
	node->left = NULL;
	node->right = NULL;
	return(node);
}

// 오른쪽으로 회전시키는 함수
AVLNode *rotate_right(AVLNode *parent)
{
	AVLNode* child = parent->left;
	parent->left = child->right;
	child->right = parent;

	// 새로운 루트를 반환
	return child;
}

// 왼쪽으로 회전시키는 함수
AVLNode *rotate_left(AVLNode *parent)
{
	AVLNode *child = parent->right;
	parent->right = child->left;
	child->left = parent;

	// 새로운 루트 반환
	return child;
}

// AVL 트리에 새로운 노드 추가 함수
// 새로운 루트를 반환한다. 
AVLNode* insert(AVLNode* node, int key)
{
	// 이진 탐색 트리의 노드 추가 수행
	if (node == NULL)
		return(create_node(key));

	if (key < node->key)
		node->left = insert(node->left, key);
	else if (key > node->key)
		node->right = insert(node->right, key);
	else	// 동일한 키는 허용되지 않음
		return node;

	// 노드들의 균형인수 재계산
	int balance = get_balance(node);

	// LL 타입 처리
	if (balance > 1 && key < node->left->key)
		return rotate_right(node);

	// RR 타입 처리
	if (balance < -1 && key > node->right->key)
		return rotate_left(node);

	// LR 타입 처리
	if (balance > 1 && key > node->left->key)
	{
		node->left = rotate_right(node->left);
		return rotate_right(node);
	}

	// RL 타입 처리
	if (balance < -1 && key < node->right->key)
	{
		node->right = rotate_right(node->right);
		return rotate_left(node);
	}
	return node;
}

// 전위 순회 함수
void preorder(AVLNode *root)
{
	if (root != NULL)
	{
		printf("[%d] ", root->key);
		preorder(root->left);
		preorder(root->right);
	}
}

int main(void)
{
	AVLNode *root = NULL;

	// 예제 트리 구축
	root = insert(root, 10);
	preorder(root);
	printf("\n");
	root = insert(root, 20);
	preorder(root);
	printf("\n");
	root = insert(root, 30);
	preorder(root);
	printf("\n");
	root = insert(root, 40);
	preorder(root);
	printf("\n");
	root = insert(root, 50);
	preorder(root);
	printf("\n");
	root = insert(root, 29);
	preorder(root);
	printf("\n");
	printf("전위 순회 결과 \n");

	return 0;
}

2-3트리

2-노드 : 차수가 2인 노드, 하나의 데이터 k1와 두 개의 자식 노드를 가진다.
3-노드 : 차수가 3인 노드, 2개의 데이터 k1, k2와 3 개의 자식 노드를 가진다.

2-3트리 삽입 연산

• 단말 노드를 분리하는 경우
  • 부모노드가 2-노드 -> 새로운 노드와 기존의 2개의 노드 중에서 중간값은 부모 노드로 올라가고 작은값과 큰값은 새로운 노드로 분리됨
  • 부모노드가 3-노드 -> 2-노드 처럼되고 부모 노드 또한 분리
• 비단말 노드를 분리하는 경우
  • 마찬가지로 새로운 노드와 기존의 2개의 노드 중에서 중간값은 부모 노드로 올라가고 작은값과 큰값은 새로운 노드로 분리됨. 부모 노드가 3-노드라면 이러한 분리과정을 반복
• 루트 노드를 분리하는 경우
  • 루트 노드를 분리하게 되면 새로운 노드가 하나 생기게 되므로 트리의 높이가 하나 증가