이진 탐색 트리(BST: Binary Search Tree)

이재원·2025년 1월 5일

알고리즘

목록 보기

20/23

이진 탐색 트리

이진 탐색 트리는 근본적으로 이진 탐색과 같은 원리이다. 하지만 이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입과 삭제할 때마다 앞뒤의 원소들을 이동시켜야 하기 때문에 비효율적이다. 반면에 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조로 되어 있다. 따라서 삽입과 삭제가 심하지 않은 정적인 자료를 대상으로 탐색이 이루어지는 경우에는 이진 탐색도 무난한 방법이나 삽입, 삭제가 빈번히 이뤄진다면 반드시 이진 탐색 트리를 사용해야 한다.

이진 트리와 이진 탐색 트리의 시간 복잡도 비교

장점과 단점

장점

탐색, 삽입, 삭제에서 효율적이다. → 시간 복잡도: $O(logn)$
트리 구조를 이용해 데이터가 정렬된 상태를 유지

단점

트리의 균형이 깨지는 경우(한쪽으로 치우친 경우), 시간 복잡도가 $O(n)$ 까지 증가
균형을 유지하려면 AVL 트리 같은 추가적인 균형 트리 기법이 필요

힙 트리와 차이점

최대 힙(Max Heap)

부모 노드는 자식 노드보다 항상 크거나 같아야 한다는 규칙만 따른다.
왼쪽 자식과 오른쪽 자식 사이에는 크기 비교나 정렬 규칙이 없다.
노드 삽입 시, 완전 인진 트리 형태를 유지하기 위해 트리의 가장 마지막 레벨의 왼쪽부터 순서대로 채운다.
삽입 후, 부모-자식 관계를 정렬하기 위해 힙을 재구성한다.

이와 같은 방식으로 최대 힙을 구성하는데, 여기서 중요한 점은 데이터 크기의 기준을 부모 노드로 한다는 점이다.

이진 탐색 트리의 경우 왼쪽은 모두 루트 노드보다 작고, 오른쪽 노드는 모두 루트 노드보다는 크다는 기준이 있지만, 힙 트리의 경우 루트 노드를 기준으로 자식 노드들은 데이터가 모두 작은 것을 확인할 수 있다.

AVL 트리

AVL 트리는 이진 탐색 트리의 한 종류로, 트리의 균형을 유지하도록 설계된 자체 균형 이진 탐색 트리이다.

이진 탐색 트리의 경우, 한쪽으로 치우친 트리가 되면 탐색, 삽입, 삭제의 성능이 $O(n)$ 까지 떨어질 수 있지만, AVL 트리는 높이 균형 조건을 유지함으로써 항상 $O(logn)$ 의 성능을 보장한다.

균형 인수와 균형 조건

각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 -1, 0, 1 중 하나여야 한다. 두 서브 트리의 차를 균형 인수(balance factor)라고 하고, 균형 인수가 클수록 비균형이다.

AVL 트리의 삽입 연산

균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 것은 삽입 연산과 삭제 연산 시이다. 삽입 연산 시에는 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 따라서 노드의 삽입/삭제 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 -2, 2가 된 최초의 노드의 서브 트리들에 대하여 회전을 통해 다시 균형을 잡아야 한다.

회전(Rotation)

AVL 트리에서 균형을 복원하는 핵심 동작은 회전이다.

트리의 균형이 깨지는 경우는 총 4가지로 나눌 수 있으며, 이 경우 각각 적절한 회전을 수행한다.

LL(Left-Left) 회전

왼쪽 서브트리의 왼쪽에서 삽입이 발생한 경우
해결 방법: LL 회전(오른쪽 회전)

Before LL Rotation:
       10
      /
     5
    /
   2

After LL Rotation:
       5
      / \
     2   10

RR(Right-Right) 회전

오른쪽 서브트리의 오른쪽에서 삽입이 발생한 경우
해결 방법: RR회전(왼쪽 회전)

Before RR Rotation:
       10
          \
           15
             \
              20

After RR Rotation:
       15
      /  \
     10   20

LR(Left-Right) 회전

왼쪽 서브트리의 오른쪽에서 삽입이 발생한 경우
해결 방법: LR회전(왼쪽 회전 후 오른쪽 회전)

Before LR Rotation:
       10
      /
     5
      \
       8

After LR Rotation:
       8
      / \
     5   10

RL(Right-Left) 회전

오른쪽 서브트리의 왼쪽에서 삽입이 발생한 경우
해결 방법: RL 회전(오른쪽 회전 후 왼쪽 회전)

Before RL Rotation:
       10
          \
           15
          /
         12

After RL Rotation:
       12
      /  \
     10   15

AVL 트리 예제

마지막 그림을 보면, 노드 6의 균형 인수가 균형 조건(±1)을 위반했다. 불균형의 원인은 6의 왼쪽 서브트리(2)에 새 노드 3이 추가되었기 때문이다. 따라서 6번 노드가 균형을 복구하기 위해 중심이 되는 회전 대상이 된다.

이 경우 왼쪽 자식의 오른쪽 서브트리에서 불균형이 발생한 것으로 LR 타입 불균형이다. 따라서 LR 회전을 수행해 준다.

첫 번째 회전: 불균형의 원인이 된 2를 기준으로 왼쪽 회전(Left Rotation)
두 번째 회전: 불균형이 최초로 발생한 6을 기준으로 오른쪽 회전(Right Rotation)

AVL 트리 구현

AVL 트리 정의

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

오른쪽으로 회전시키는 함수(Right Rotation)

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

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

왼쪽으로 회전시키는 함수(Left Rotation)

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

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

트리의 높이와 균형 인수 계산

// 트리의 높이를 반환
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);
}

전체 코드

#include<stdio.h> 
#include<stdlib.h> 
#define MAX(a, b) ((a) > (b) ? (a) : (b))
// 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);
	root = insert(root, 20);
	root = insert(root, 30);
	root = insert(root, 40);
	root = insert(root, 50);
	root = insert(root, 29);

	printf("전위 순회 결과 \n");
	preorder(root);

	return 0;
}

장점과 단점

장점

항상 $O(logn)$ 의 탐색 속도를 보장
일반 BST가 편향 트리(Skewed Tree)로 인해 $O(n)$ 이 되는 상황을 방지
균형 잡힌 트리를 유지하기 때문에 삽입 및 삭제 작업 이후에도 성능 저하가 발생하지 않음

단점

균형을 유지하기 위한 추가 연산(회전)이 필요
특히 삽입, 삭제 시 균형 인수를 계산하고 회전을 수행하는 과정이 복잡
노드마다 높이를 저장하거나 계산해야 하므로, 추가적인 메모리 공간이 필요

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구

이재원

20학번 새내기^^(였음..)

이전 포스트

보간 탐색(Interpolation Search)

다음 포스트

이진 탐색 트리(BST: Binary Search Tree)

알고리즘

이진 탐색 트리

이진 트리와 이진 탐색 트리의 시간 복잡도 비교

장점과 단점

장점

단점

힙 트리와 차이점

최대 힙(Max Heap)

AVL 트리

균형 인수와 균형 조건

AVL 트리의 삽입 연산

회전(Rotation)

LL(Left-Left) 회전

RR(Right-Right) 회전

LR(Left-Right) 회전

RL(Right-Left) 회전

AVL 트리 예제

AVL 트리 구현

AVL 트리 정의

오른쪽으로 회전시키는 함수(Right Rotation)

왼쪽으로 회전시키는 함수(Left Rotation)

트리의 높이와 균형 인수 계산

전체 코드

장점과 단점

장점

단점

보간 탐색(Interpolation Search)

2-3트리

0개의 댓글