[자료구조] AVL 트리와 탐색

탐색

• 여러 개의 자료 중 원하는 자료를 찾는 것
• 탐색키 : 항목과 항목을 구별해주는 키(key)
• 배열, 연결 리스트, 트리 그래프 등 다양한 방법으로 탐색 자료구조로 씀

 

순차 탐색 (sequential search)

• 탐색 방법 중 가장 간단하고 직접적인 방법
• 정렬 안된 배열을 처음부터 마지막까지 검사
• 평균 비교 횟수
  • 성공 시 : (n+1)/2번 비교 -> 한 번에 찾을 경우 1, 최악의 경우 n이니 나누기 2
  • 실패 시 : n번 비교
• 시간 복잡도 : O(n)

예시 코드

int seq_search(int key, int low, int high)
{
	for (int i = low; i <= high; i++)
	{
		if (list[i] == key) // 탐색 성공
			return i;
	}
	return -1; // 탐색 실패
}

 

예시 코드(2)

: 리스트 끝에 탐색 키를 저장

int seq_search2(int key, int low, int hight) {

	list[high + 1] = key; // 끝에 찾을 key 삽입
	for (int i = low; list[i] != key; i++)
		;
	if (i == high + 1) return -1; // 탐색 실패
	else return i; // 탐색 성공
}

 

이진 탐색 (binary search)

• 정렬된 배열의 탐색에 적합
• 배열의 중간에 있는 값을 이용해 찾고자 하는 항목이 왼쪽 또는 오른쪽에 있는지 알아내어 탐색의 범위를 반으로 줄여가며 탐색
• 10억 명에서 특정한 이름 탐색 시
  • 순차 탐색 : 평균 5억 번의 비교가 필요
  • 이진 탐색 : 단지 30번의 비교로 찾기 가능

예제 코드 (재귀)

int search_binary(int key, int low, int high)
{
	int middle;
	if (low <= high)
	{
		middle = (low + high) / 2;
		if (key == list[middle]) 
			return middle; // 탐색 성공
		else if (key < list[middle]) // 왼쪽 탐색
			return search_binary(key, low, middle - 1);
		else // 오른쪽 탐색
			return search_binary(key, middle + 1, high);

	}

	return -1; // 탐색 실패
}

 

예제 코드(반복)

int search_binary2(int key, int low, int high)
{
	int middle;

	while (low <= high)
	{
		middle = (low + high) / 2;
		if (key == list[middle])
			return middle;
		else if (key > list[middle]) // 오른쪽 탐색
			low = middle + 1;
		else // 왼쪽 탐색(middle 기준)
			high = middle - 1;


	}

	return -1; //탐색 실패
}

 

색인 순차 탐색(indesed sequential search)

• 인덱스(index) 테이블을 사용해 효율 증대
  • 주 자료 리스트에서 일정 간격으로 발췌해 인덱스 테이블에 저장
• 주 자료와 인덱스 테이블은 정렬되어 있어야 함

보간 탐색(interpolation search)

• 사전이나 전화번호에서 우리가 찾을 때 방법과 동일
  • 'ㅎ'으로 시작하는 단어는 사전 뒷부분에서 찾는 것과 같은 방식
  • 'ㄱ'으로 시작하는 단어는 앞부분에서 찾음
• 탐색 키가 존재할 위치를 예측해서 찾는 방법임 : O(logn)
• 이진 탐색과 유사하나 리스트를 불균등 분할하여 탐색한다.
• 보간 탐색은 데이터가 균등하게 분포되어 있을 때 효율적

 

균형 이진 탐색 트리

 

들어가기에 앞서

이진 탐색(binary search)과 이진 탐색 트리(binary search tree) 차이점

• 이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리
• 이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입/삭제가 비효율
  • 자료의 삽입/삭제 시 원소들의 이동이 필요하기 때문임
• 이진 탐색 트리는 매우 빠르게 삽입/삭제 수행이 가능
  • 삽입/삭제가 빈번히 이루어진다면 이진 탐색 트리가 용이함(연결 과정을 생각해보자)
• 이진 탐색 트리에서의 시간 복잡도
  • 균형 트리 : O(logn)
  • 불균형 트리 : O(n) , 순차 탐색과 동일

(균형 트리)

(경사트리)

균형 트리가 탐색/삭제에 용이해 보인다. 트리를 균형 있게 만드는 방법이 있을까?

 

AVL 트리

• 모든 노드가 왼쪽과 오른쪽 서브 트리의 높이 차가 1 이하인 이진 탐색 트리
• 트리가 비균형 상태가 되면 노드들을 재배치해 균형 상태를 유지
• 시간 복잡도 : O(logn)
• 균형 인수(balance factor) = ( 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 )
• 모든 노드의 균형 인수가 +- 1 이내면 AVL 트리이다.

AVL 트리

비 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);
}

 

AVL 트리의 연산

• 탐색 연산: 이진 탐색 트리와 등일하다.
• 삽입 삭제 시 균형 상태가 깨질 수 있으므로 생각해야 함
• 삽입 연산
  • 삽입 위치에서 루트까지의 경로상에 영향을 줌(조상 노드들의 균형 인수에 영향)
  • 삽입 후 불균형 상태로 변한 가장 가까운 조상 노드의 서브 트리에 대해 다시 재균형을 해야 함
  • 삽입 노드부터 균형 인수가 +-2가 된 가장 가까운 조상 노드까지 회전이 필요

 

삽입전의 AVL 트리

 

-> key 1을 가진 노드 삽입

불균형 발생(LL)

AVL 트리

 

 

AVL 트리에서 균형이 깨지는 4가지 경우

( N = 삽입된 노드, A = N으로부터 가장 가까우면서 균형 인수가 +-2가 된 조상 노드)

• LL타입 : N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 존재(삽입)
• LR 타입 : N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 존재(삽입)
• RR 타입 : N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 존재(삽입)
• RL 타입 : N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 존재(삽입)

 

각각 타입에 대한 해결 방법

 

(1) LL 타입 ( LL회전 : 오른쪽 회전 )

 

(2) LR 타입 ( LR회전 : 왼쪽 회전 -> 오른쪽 회전 )

 

(3) RR 타입 ( RR 회전: 왼쪽 회전 )

 

(4) RL 타입 ( RL 회전: 왼쪽 회전 -> 오른쪽 회전 )

 

LL 회전 방법

rotate_LL(A)

1. B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다.
2. A를 B의 오른쪽 자식 노드로 만든다.

LL회전-설명이 잘 되어있는 사진이 있어 가져왔습니다.

LL회전 ( 오른쪽으로 회전 ) 구현 코드

typedef struct
{
	int key;
	struct AVLNode* left;
	struct AVLNode* right;
}AVLNode;

AVLNode* rotate_right(AVLNode* parent)
{
	AVLNode* child = parent->left;
	parent->left = child->right;
	child->right = parent;

	return child; // 새로운 root를 반환
}

 

RR 회전 방법

rotate_RR(A)

1. B의 왼쪽 자식을 A의 오른쪽 자식으로 만든다.
2. A를 B의 왼쪽 자식 노드로 만든다.

-설명이 잘 되어있는 사진이 있어 가져왔습니다.

 

RR 회전 ( 왼쪽으로 회전 ) 구현 코드

AVLNode* rotate_left(AVLNode* parent)
{
	AVLNode* child = parent->right;
	parent->right = child->left;
	child->left = parent;

	return child;
}

 

LR 회전 방법

rotate_LR(A)

1. roate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다.
2. rotate_LL(A)

(LR-1) 설명이 잘 되어있는 사진이 있어 가져왔습니다.

(LR-2) 설명이 잘 되어있는 사진이 있어 가져왔습니다.

LR 회전 코드

AVLNode* rotate_left_right(AVLNode* parent)
{
	parent->left = rotate_left(parent->left);
	return rotate_right(parent);
}

 

RL 회전 방법

rotate_RL(A)

1. rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.
2. rotate_RR(A)

(RL-1) 설명이 잘 되어있는 사진이 있어 가져왔습니다.

(RL-2) 설명이 잘 되어있는 사진이 있어 가져왔습니다.

 

RL 회전 코드

AVLNode* rotate_right_left(AVLNode* parent)
{
	parent->right = rotate_right(parent->right);
	return rotate_left(parent);
}

 

 

- AVL 트리의 삽입 때 AVL 이 깨진다면 회전을 시켜주면 됨 -

그림은 RL 회전이 요약되어 결과만 나와있지만

차례대로 풀어나간다면 그림판으로 그려진 부분을 따라가면 RL회전이 됨.