[C언어로 쉽게 풀어쓴 자료구조] Chapter13. 탐색 (2)

13.4 이진 탐색 트리

이진 탐색은 자료들이 배열에 저장되어 있어 삽입과 삭제가 힘들다는 단점 존재

이진 탐색 트리는 삽입, 삭제가 빈번한 상황에서 사용

 

- 이진 탐색 트리는 트리가 균형 트리 일 때 O(log2n)의 시간 복잡도를, 균형 트리가 아닐 때는

최악의 경우 O(n)의 시간복잡도를 가짐

알고리즘	최악		평균
	탐색	삽입	탐색	삽입
순차 탐색(정렬x)	N	N	N/2	N
이진 탐색(정렬o)	logN	N	logN	N/2
이진 탐색 트리	N	N	logN	logN

모든 항목이 균일하게 탐색된다는 가정 하에 평균 비교 횟수를 비교

좌측 트리와 같은 편향된 경사 트리는 (1+2+3+4+5+6+7)/7 = 4

우측 트리와 같은 균형트리는 (1+2+2+3+3+3+3)/7 = 2.4

따라서 이진 탐색 트리에서는 균형을 유지하는 것이 중요

 

13.5 AVL 트리

AVL트리: 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리

 

- 트리가 삽입, 삭제 등으로 비균형 상태가 되면 스스로 노드를 재배치하여 균형 상태로 만듦

- 균형 트리가 항상 보장되어 O(logn)시간안에 탐색, 삽입, 삭제 가능

 

균형 인수(balance factor): (왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이)

균형 인수가 ±1이하면 AVL 트리

 

● AVL 트리의 탐색 연산

일반적인 이진 탐색 트리와 같이 O(log2n)의 시간 복잡도를 가진다.

 

● AVL 트리의 삽입 연산

- 삽입되는 위치 ~ 루트 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있기에 

삽입 연산 이후 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 ±2가 된 가장 가까운 조상 노드의

서브 트리들에 대하여 재배치하여 균형 상태로 만들어야 한다.

 

재배치: 새로운 노드~ 균형 인수가 ±2가 된 가장 가까운 조상 노드까지를 회전

● AVL 트리 예제

삽입을 통해 트리의 균형이 깨지게 되면 균형을 이루기 위해 LL, LR, RL, RR 회전 중 상황에 맞는 회전을 선택한다.

이들 회전은 모두 새로 삽입된 노드로부터 ±2의 균형 인수를 가지는 가장 가까운 조상 노드에 대하여 이루어진다.

 

● AVL 트리의 정의

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

AVL 트리도 이진 탐색 트리의 일종

 

● rotate_right(), rotate_left() 함수 구현

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

부모 노드의 왼쪽 노드를 자식 노드의 오른쪽 노드로 바꾸고, 자식 노드의 오른쪽 노드를 기존 부모노드로 둔 뒤

자식 노드를 return하면 오른쪽으로 회전 된다.

 

● get_height(), get_balance() 함수 구현

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_balanced(AVLNode *node){
	if(node ==NULL) return 0;
	return get_height(node->left) - get_height(node->right);
}

 

● 새로운 노드 추가 함수

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_balanced(node);
	// balance >1 이면 왼쪽 자식, balance <-1 이면 오른쪽 자식에 삽입되었고
	// key<node->left->key 이면 자식의 왼쪽에 추가 key>node->right->key 이면 자식의 오른쪽에 추가
	
	if(balance >1 && key< node->left->key){
		return rotate_right(node);
	} // LL
	if(balance <-1 && key> node->right->key){
		return rotate_left(node);
	} //RR
	if(balance >1 && key> node->left->key){
		node->left = rotate_left(node->left);
		return rotate_right(node);
	} //LR
	if(balance <-1 && key< node->right->key){
		node->right = rotate_right(node->right);
		return rotate_left(node);
	} //RL
	
	return node;
	
}

주석참고

 

♠ 523p Quiz 

01

 

13.6 2-3 트리

● 2-3 트리: 차수가 2 또는 3인 노드를 가지는 트리

- 삽입이나 삭제 연산이 AVL트리보다 간단

- 2-노드는 하나의 데이터 k1와 두개의 자식 노드를, 3-노드는 두개의 데이터 k1,k2와 3개의 자식노드를 가짐

- 왼쪽 서브트리는 k1보다 작은 값, 중간 서브트리는 k1보다 크고 k2보다 작은 값, 오른쪽 서브트리는 k2보다 큰 값

 

● 2-3 트리의 탐색 연산

노드가 2-노드인지 3-노드인지에 따라 탐색을 각각 진행

2-노드면 탐색 key가 현재 노드의 key보다 작다면 왼쪽 서버트리를, 크다면 오른쪽 서브트리를 순환탐색

 

● 2-3 트리의 삽입 연산

노드는 2개의 데이터값을 저장. 저장 가능할 때까지 데이터 추가, 더 이상 저장할 장소가 없을 땐 노드 분리

중간 값을 한레벨 위로 올리고 제일 작은 값을 왼쪽 노드, 큰 값을 오른쪽 노드로 만듦

 

노드 분리되는 상황

case1. 단말 노드를 분리

- 부모노드가 2-노드: 중간값이 부모노드로 올라가고 작은 값과 큰 값은 새로운 노드로 분리

- 부모노드가 이미 2개의 데이터를 가진 3-노드: 부모 노드가 다시 재분리 되어 case2 적용

 

case2. 비단말 노드를 분리

- 중간 값을 다시 부모 노드로 올려보내고 작은 값과 큰 값은 새로운 노드로 분리

- 부모 노드에 올라간 추가 노드를 받을 공간이 없다면 계속 상위 부모 노드로 순환 ( bottom up )

 

case3. 루트 노드를 분리

- bottom up이 진행되다가 루트 노드에 도달하여 루트 노드를 분리하게 되면 트리의 노드 1 증가

- 중간값이 올라가서 만든 새로운 노드는 새로운 루트 노드가 됨

case3에서만 트리의 높이가 1 증가

 

♠ 528p Quiz 

01

 

 

13.7 2-3-4 트리

● 2-3-4 트리: 차수가 2 또는 3 또는 4인 노드를 가지는 트리, 2-3 트리의 확장 버전

- 4-노드는 4개의 자식을 가질 수 있으며 3개의 데이터를 가질 수 있다.

 

3개의 데이터를 크기 순으로 small, middle, large라고 하면

1. small 보다 작은 값은 첫번째 자식 노드

2. small보다 크고 middle보다 작은 값은 두번째 자식 노드

3. middle보다 크고 large보다 큰 값은 세번째 자식 노드

4. large보다 큰 값은 네번째 자식 노드

 

● 2-3-4  트리의 삽입 연산

- 삽입하는 단말노드가 4-노드이면 후진분할이 일어나는데, 이를 방지하기 위해

삽입노드를 찾는 순회 과정에서 4-노드를 만나면 미리 분할을 수행해놓는다.

이는 2-3트리와 달리 루트에서 단말 노드로 한번만 순회하여 삽입이나 삭제가 가능하게 한다.

 

순회 중 4-노드를 만난 경우

case1. 4-노드가 루트인 경우

- 4-노드의 중간값을 상위 레벨로 올려 새로운 노드를 만들며 해당 노드가 새로운 루트 노드가 된다.

case2. 4-노드의 부모가 2-노드인 경우

case3. 4-노드의 부모가 3-노드인 경우

- 4-노드의 중간값을 상위 레벨로 올려 위치하게 한 뒤, 작은 값과 큰 값은 적절한 위치에 자식 노드로 분리한다.