본 시리즈는 프로그래밍 자료구조의 개념을 정리하고 실습을 진행해보는 시리즈입니다.
- 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
- IDE : IntelliJ IDEA (Ultimate Edition)
- Java : JDK 21 (corretto-21)
- Python : 3.9 (conda env)
트리(Tree) - Binary Search Tree
- 일반적인 Tree에 대한 전반적인 내용들은 다음 포스팅에서 확인하실 수 있습니다.
- 이진트리에 대한 기본적인 내용들은 다음 포스팅에서 확인하실 수 있습니다.
1. Binary Search Tree란?
Binary Search Tree (BST)는 이진 트리의 일종으로, 데이터를 효율적으로 검색, 삽입, 삭제할 수 있는 자료구조입니다.
- 각 노드는 왼쪽 자식은 부모 노드보다 작은 값, 오른쪽 자식은 부모 노드보다 큰 값을 가지는 이진 탐색 규칙을 따릅니다. (중복은 허용하지 않습니다.)
- 이 규칙 덕분에 BST는 검색이나 정렬된 데이터의 관리에 매우 유용하게 사용됩니다.
1.1 Binary Search Tree의 주요 특징
BST는 다음과 같은 특징을 가집니다:
-
이진 탐색 규칙:
- BST의 가장 큰 특징은 각 노드의 왼쪽 서브트리에 있는 모든 값은 부모보다 작고, 오른쪽 서브트리의 모든 값은 부모보다 크다는 규칙을 따릅니다.
- 이 규칙 덕분에 빠른 탐색과 삽입/삭제가 가능하며, 특히 탐색에서는 이진 탐색과 동일한 시간 복잡도를 가집니다.
-
시간 복잡도:
- 평균적으로 탐색, 삽입, 삭제는 O(log n)의 시간 복잡도를 가집니다.
- 그러나 트리의 균형이 깨질 경우, 예를 들어, 한쪽으로 편향된 트리가 되면 성능이 O(n)으로 저하될 수 있습니다.
- 이를 보완하기 위해 균형 이진 탐색 트리(AVL 트리, Red-Black 트리)가 사용되기도 합니다.
- 균형 이진 탐색 트리는 다음 포스팅에서 자세히 다룹니다.
-
중복 데이터 처리:
- BST는 기본적으로 중복을 허용하지 않는 구조입니다.
- 동일한 값을 삽입할 경우 일반적으로 삽입이 무시되거나, 특정 트릭을 사용하여 중복 데이터를 처리할 수 있습니다.
-
재귀적 구조:
- 트리의 왼쪽 서브트리와 오른쪽 서브트리 역시 각각 BST로 취급되며, 이는 재귀적인 자료구조 특성을 가집니다.
1.2 Binary Search Tree의 주요 용도
BST는 그 특성상 다양한 응용 분야에서 매우 유용하게 사용됩니다. 주요 용도를 살펴보면 다음과 같습니다:
-
데이터 탐색(Search):
- BST는 정렬된 데이터를 효율적으로 탐색할 수 있어, 검색 연산에 적합한 자료구조입니다.
- 평균적으로 O(log n)의 성능을 제공하여 선형 검색에 비해 더 효율적입니다.
-
동적 데이터 관리(Dynamic Data Management):
- 정렬된 배열과는 달리, BST는 동적 데이터 삽입 및 삭제가 용이합니다.
- 데이터가 계속 추가되거나 제거되는 상황에서 유연하게 데이터를 관리할 수 있습니다.
-
정렬된 데이터 출력(In-order Traversal):
- 중위 순회(In-order Traversal)를 사용하면 BST는 정렬된 데이터를 효율적으로 출력할 수 있습니다.
- 이는 데이터가 오름차순 또는 내림차순으로 출력되기를 원하는 경우 유용합니다.
-
Set과 Map 구조:
- 많은 프로그래밍 언어에서 제공하는 Set 또는 Map 자료구조는 BST를 기반으로 구현되기도 합니다.
- 예를 들어, Java의
TreeSet과TreeMap은 BST를 활용한 대표적인 예입니다.
-
트리 기반 알고리즘:
- 여러 그래프 알고리즘이나 경로 탐색 알고리즘에서 BST가 효율적으로 활용됩니다.
- 트리 기반 자료구조를 사용한 알고리즘은 최단 경로 탐색, 데이터 정렬, 범위 쿼리 처리 등에서 응용됩니다.
BST는 이처럼 탐색과 데이터 관리가 빈번하게 이루어지는 다양한 응용 분야에서 사용되며, 기본적인 자료구조로 널리 활용됩니다.
2. Binary Search Tree 탐색,삽입,삭제
Binary Search Tree(BST)는 탐색, 삽입, 삭제와 같은 주요 연산을 이진 탐색(Binary Search)의 원리를 기반으로 합니다. 이 섹션에서는 각 연산의 개념과 과정을 설명합니다.
2.1 탐색(Search)
탐색 연산은 트리에서 특정 값을 찾는 과정입니다.
- 이진 탐색 트리는 노드의 정렬된 구조를 이용해 탐색 시간을 최적화할 수 있습니다.
탐색 과정:
- 루트 노드에서 시작하여 찾으려는 값(target)과 현재 노드의 값을 비교합니다.
- target이 현재 노드의 값보다 작다면 왼쪽 서브트리로 이동합니다.
- target이 현재 노드의 값보다 크다면 오른쪽 서브트리로 이동합니다.
- target을 찾으면 탐색을 종료하고, 찾지 못하면
null을 반환하며 탐색이 종료됩니다.
탐색 시간 복잡도:
- 최선의 경우: O(log n) (완전 균형 상태에서)
- 최악의 경우: O(n) (비균형 상태, 즉 한쪽으로 치우친 트리)
2.2 삽입(Insertion)
삽입 연산은 트리에서 새로운 값을 추가하는 연산입니다.
- 삽입할 때도 이진 탐색의 규칙을 따릅니다.
삽입 과정:
- 루트 노드에서 시작하여 삽입할 값(newValue)을 현재 노드의 값과 비교합니다.
- newValue가 현재 노드의 값보다 작다면 왼쪽 서브트리로 이동합니다.
- newValue가 현재 노드의 값보다 크다면 오른쪽 서브트리로 이동합니다.
- 비어있는 자리를 찾을 때까지 이동을 반복한 후, 그 위치에 새로운 노드를 삽입합니다.
삽입 시간 복잡도:
- 최선의 경우: O(log n)
- 최악의 경우: O(n) (비균형 상태)
2.3 삭제(Deletion)
삭제 연산은 트리에서 특정 노드를 제거하는 연산으로, 다른 연산보다 복잡한 편입니다.
- 삭제할 노드의 자식 노드의 수에 따라 세 가지 경우로 나뉩니다.
삭제 과정:
-
자식 노드가 없는 경우 (리프 노드):
- 노드를 단순히 제거합니다.
- 예시 : 이미지 예시에서 값이
33인 리프 노드를 삭제하는 경우, 부모 노드(40)의 왼쪽 자식 포인터를null로 설정해서 값이33인 노드를 제거합니다.
- 자식 노드가 하나인 경우:
- 삭제할 노드를 자식 노드와 교체하고 삭제합니다.
- 예시 : 이미지 예시에서 값이
90인 노드를 삭제하는 경우, 부모 노드(75)의 오른쪽 자식 포인터를 삭제 노드의 자식노드인99노드로 설정해서 값이90인 노드를 제거합니다.
-
자식 노드가 두 개인 경우:
-
삭제 연산에서 자식 노드가 두 개 있는 경우, 후계자 또는 선행자를 찾아 삭제할 노드와 교체하는 과정이 필요합니다. 일반적으로 오른쪽 서브트리에서 후계자(successor)를 찾는 방법이 더 자주 사용되며, 이는 균형을 덜 깨뜨리는 방식으로 알려져 있습니다.
- 하지만, 왼쪽 서브트리에서 선행자(predecessor)를 찾아 교체하는 방식도 가능합니다.
-
후계자와 선행자 찾는 과정
- 후계자(successor): 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 찾습니다.
- 선행자(predecessor): 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 찾습니다.
- 다만 오른쪽 서브트리에서 찾는 경우엔, 후계자의 부모노드를 선행자(predecessor)라고 부르기도 하여 해당 노드를 함께 추적합니다.
후계자 예시 (오른쪽 서브트리에서 가장 작은 값)
- 예를 들어, 삭제할 노드가
50이고, 자식 노드가 두 개 있을 때, 후계자를 찾아 교체하는 과정을 살펴보겠습니다.
- 삭제할 노드(
50)의 오른쪽 서브트리에서 가장 작은 값을 찾습니다. 즉,55가 후계자가 됩니다. 55와50을 교체합니다.- 이후
55자리에 있던 노드(후계자)를 삭제합니다. (후계자가 자식을 가지면, 후계자의 자식과 부모를 연결하고 후계자를 삭제합니다.)
선행자 예시 (왼쪽 서브트리에서 가장 큰 값)
- 삭제할 노드가
55로 변경되었을 때, 선행자를 찾아 교체하는 방식도 가능합니다.
50의 왼쪽 서브트리에서 가장 큰 값(40)을 찾습니다.40과50을 교체한 후, 40의 자리를 제거합니다.
Tip: 일반적으로는 오른쪽 서브트리의 최소값을 찾는 것이 왼쪽 서브트리의 최대값을 찾는 것보다 효율적일 때가 많습니다. 하지만 특정 상황에서는 왼쪽 서브트리의 최대값을 선택하는 것이 더 적절할 수 있습니다.
- 쉽게 말해 취향 차이인 셈입니다.
삭제 시간 복잡도:
- 최선의 경우: O(log n)
- 최악의 경우: O(n) (비균형 상태)
3. Binary Search Tree 구현 (Java, Python)
이제 탐색, 삽입, 삭제 연산을 살펴보았으니, 이러한 연산을 실제로 어떻게 구현할 수 있는지 Java와 Python으로 구현하는 단계로 넘어가 보겠습니다.
3.1 Java에서의 Binary Search Tree 구현
Java에서는 각 노드를 클래스로 정의하고, BST의 탐색, 삽입, 삭제 연산을 메서드로 구현합니다.
3.1.1 Node 클래스
각 노드는 데이터와 왼쪽, 오른쪽 자식에 대한 참조를 가지고 있습니다.
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null; // 노드 생성 시 자식 노드는 null로 초기화
}
}- Node 클래스: 각 노드는 데이터를 저장하고, 왼쪽과 오른쪽 자식 노드를 가리키는 포인터를 가집니다.
3.1.2 Binary Search Tree 클래스
BST 클래스에서는 루트 노드를 관리하며, 탐색, 삽입, 삭제 메서드를 정의합니다.
class BinarySearchTree {
Node root;
BinarySearchTree() {
root = null; // 트리의 루트 노드는 처음에 null
}
// 탐색 연산
public Node search(Node root, int key) {
if (root == null || root.data == key)
return root; // key를 찾으면 해당 노드를 반환, 아니면 null
if (key < root.data)
return search(root.left, key);
return search(root.right, key);
}
// 삽입 연산
public Node insert(Node root, int key) {
if (root == null) {
root = new Node(key); // 비어있는 자리에 노드 삽입
return root;
}
if (key < root.data)
root.left = insert(root.left, key);
else if (key > root.data)
root.right = insert(root.right, key);
return root;
}
// 삭제 연산
public Node delete(Node root, int key) {
if (root == null) return root; // 노드를 찾지 못하면 그대로 반환
if (key < root.data)
root.left = delete(root.left, key);
else if (key > root.data)
root.right = delete(root.right, key);
else {
// 자식이 하나도 없는 경우
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 자식이 두 명인 경우: 후계자(successor)를 찾음 (오른쪽 서브트리에서 최소값)
root.data = minValue(root.right);
// 후계자 삭제
root.right = delete(root.right, root.data);
}
return root;
}
// 오른쪽 서브트리에서 가장 작은 값을 찾는 함수 (후계자 찾기)
int minValue(Node root) {
int minv = root.data;
while (root.left != null) {
minv = root.left.data; // 왼쪽으로 계속 이동해 가장 작은 값을 찾음
root = root.left;
}
return minv;
}
// 중위 순회 (In-order Traversal) 출력
public void inOrder(Node root) {
if (root != null) {
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
}
}
- BinarySearchTree 클래스: 트리의 루트 노드를 관리하고, 탐색, 삽입, 삭제 연산을 처리하는 메서드를 정의합니다.
- 삽입 연산: 루트를 기준으로 왼쪽과 오른쪽으로 내려가면서 적절한 위치에 새 노드를 삽입합니다.
- 삭제 연산: 자식 노드의 수에 따라 리프 노드 삭제, 자식 하나 삭제, 후계자와 교체하는 세 가지 경우를 처리합니다.
- minValue(): 오른쪽 서브트리에서 가장 작은 값을 찾는 함수로, 후계자를 찾을 때 사용합니다.
3.1.3 트리 실행
다음은 BST 트리를 생성하고, 탐색, 삽입, 삭제 연산을 테스트하는 코드입니다.
public class Main {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// 삽입 연산
bst.root = bst.insert(bst.root, 50);
bst.insert(bst.root, 30);
bst.insert(bst.root, 20);
bst.insert(bst.root, 40);
bst.insert(bst.root, 70);
bst.insert(bst.root, 60);
bst.insert(bst.root, 80);
System.out.print("In-order Traversal: ");
bst.inOrder(bst.root); // 출력: 20 30 40 50 60 70 80
// 삭제 연산
System.out.println("\n\nAfter deleting 20");
bst.root = bst.delete(bst.root, 20);
bst.inOrder(bst.root); // 출력: 30 40 50 60 70 80
System.out.println("\n\nAfter deleting 30");
bst.root = bst.delete(bst.root, 30);
bst.inOrder(bst.root); // 출력: 40 50 60 70 80
System.out.println("\n\nAfter deleting 50");
bst.root = bst.delete(bst.root, 50);
bst.inOrder(bst.root); // 출력: 40 60 70 80
}
}
3.2 Python에서의 Binary Search Tree 구현
Python에서도 Node와 BST 클래스를 정의하고, 탐색, 삽입, 삭제 메서드를 구현할 수 있습니다.
3.2.1 Node 클래스
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
- Node 클래스: 각 노드는 키 값을 가지며, 왼쪽과 오른쪽 자식 노드에 대한 참조를 가집니다.
3.2.2 Binary Search Tree 클래스
class BinarySearchTree:
def __init__(self):
self.root = None # 루트 노드 초기화
# 탐색 연산
def search(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self.search(node.left, key)
return self.search(node.right, key)
# 삽입 연산
def insert(self, node, key):
if node is None:
return Node(key) # 빈 자리에 새 노드를 삽입
if key < node.key:
node.left = self.insert(node.left, key)
else:
node.right = self.insert(node.right, key)
return node
# 삭제 연산
def delete(self, node, key):
if node is None:
return node
if key < node.key:
node.left = self.delete(node.left, key)
elif key > node.key:
node.right = self.delete(node.right, key)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
# 자식이 두 명인 경우 후계자(successor)를 찾음 (오른쪽 서브트리에서 최소값)
temp = self.minValueNode(node.right)
node.key = temp.key
node.right = self.delete(node.right, temp.key)
return node
# 오른쪽 서브트리에서 가장 작은 값을 찾는 함수 (후계자 찾기)
def minValueNode(self, node):
current = node
while current.left is not None:
current = current.left # 왼쪽으로 계속 이동하여 최소값을 찾음
return current
# 중위 순회 (In-order Traversal) 출력
def inOrder(self, node):
if node:
self.inOrder(node.left)
print(node.key, end=" ")
self.inOrder(node.right)
- BinarySearchTree 클래스: 탐색, 삽입, 삭제 연산을 관리하고 루트 노드를 설정하는 클래스입니다.
- 삽입 연산: 트리를 순회하며 적절한 위치에 새로운 노드를 삽입합니다.
- 삭제 연산: 노드 삭제 시 자식 노드 수에 따라 처리하며, 후계자(오른쪽 서브트리의 최소값)를 찾아 노드와 교체합니다.
- minValueNode(): 후계자를 찾는 함수로, 삭제 연산 시 후계자 노드를 교체할 때 사용합니다.
3.2.3 트리 실행
다음은 BST 트리를 생성하고, 탐색, 삽입, 삭제 연산을 테스트하는 코드입니다.
# 트리 생성 및 테스트
bst = BinarySearchTree()
bst.root = bst.insert(bst.root, 50)
bst.insert(bst.root, 30)
bst.insert(bst.root, 20)
bst.insert(bst.root, 40)
bst.insert(bst.root, 70)
bst.insert(bst.root, 60)
bst.insert(bst.root, 80)
print("In-order Traversal:", end=" ")
bst.inOrder(bst.root) # 출력: 20 30 40 50 60 70 80
# 삭제 연산
print("\n\nAfter deleting 20")
bst.root = bst.delete(bst.root, 20)
bst.inOrder(bst.root) # 출력: 30 40 50 60 70 80
print("\n\nAfter deleting 30")
bst.root = bst.delete(bst.root, 30)
bst.inOrder(bst.root) # 출력: 40 50 60 70 80
print("\n\nAfter deleting 50")
bst.root = bst.delete(bst.root, 50)
bst.inOrder(bst.root) # 출력: 40 60 70 80
4. 비균형 BST의 한계
Binary Search Tree (BST)는 탐색, 삽입, 삭제가 O(log n)의 성능을 제공하는 매우 효율적인 자료구조입니다.
- 하지만, BST가 항상 균형을 유지하지는 않기 때문에 몇 가지 한계를 가지고 있습니다.
- 특히, 비균형 트리가 발생할 경우, 탐색, 삽입, 삭제와 같은 연산의 시간 복잡도가 크게 증가할 수 있습니다.
4.1 비균형 트리의 문제점
BST는 이진 탐색 규칙에 의해 노드가 삽입되지만, 데이터의 삽입 순서에 따라 비균형 트리가 만들어질 수 있습니다.
편향 트리의 예시
- 오름차순으로 삽입되는 경우: 노드가 오름차순으로 삽입될 경우, 모든 노드가 오른쪽 자식으로만 연결된 편향 트리가 만들어질 수 있습니다.
- 내림차순으로 삽입되는 경우: 내림차순으로 삽입되는 경우, 모든 노드가 왼쪽 자식으로만 연결된 편향 트리가 형성됩니다.
이렇게 비균형 상태가 되면, BST의 성능은 선형 탐색(Linked List)과 동일해져 O(n)의 시간 복잡도를 갖게 됩니다.
- 따라서 BST는 데이터를 효율적으로 관리하지 못하는 구조로 변질될 수 있습니다.
4.2 비균형 BST의 성능 저하
비균형 트리에서는 특정 연산을 수행할 때, 한쪽 방향으로 깊이 탐색을 해야 하는 경우가 생깁니다. 이러한 구조는 탐색, 삽입, 삭제 연산 모두에서 성능 저하를 유발할 수 있습니다. 특히 다음과 같은 상황에서 문제가 발생합니다.
- 탐색(Search): 루트에서 시작해 왼쪽 또는 오른쪽으로만 계속해서 내려가야 하므로, 최악의 경우 O(n)의 시간 복잡도를 가집니다.
- 삽입(Insertion): 새로운 노드를 삽입할 때도 편향된 방향으로 깊이 이동해야 하므로, 역시 O(n)의 성능 저하가 발생합니다.
- 삭제(Deletion): 삭제 과정에서 후계자를 찾거나, 자식을 재구성하는 연산도 비균형 트리에서는 성능이 떨어집니다.
따라서, BST의 장점을 제대로 활용하려면 트리가 균형 상태를 유지해야 합니다.
4.3 균형 이진 탐색 트리의 필요성
비균형 트리의 문제를 해결하기 위해, 스스로 균형을 유지하는 트리가 필요합니다. 이러한 트리를 균형 이진 탐색 트리(Self-balancing BST)라고 부릅니다.
- 균형 트리는 각 서브트리의 높이 차이를 일정한 범위 내로 제한하여, 모든 연산에서 최적의 성능을 보장합니다.
- 균형을 유지함으로써, 탐색, 삽입, 삭제 연산을 항상 O(log n)의 시간 복잡도로 처리할 수 있습니다.
4.4 AVL 트리와 Red-Black 트리 소개
균형 이진 탐색 트리의 대표적인 두 가지 종류로 AVL 트리와 Red-Black 트리가 있습니다.
1. AVL 트리
- AVL 트리는 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지하는 트리입니다.
- 삽입과 삭제 연산이 이루어질 때마다 회전 연산을 통해 트리의 균형을 조정합니다.
- 균형 유지에 더 많은 연산이 필요하지만, 그만큼 엄격한 균형을 보장합니다.
2. Red-Black 트리
- Red-Black 트리는 균형을 약간 덜 엄격하게 유지하는 트리입니다.
- 각 노드가 빨간색 또는 검은색으로 색칠되며, 몇 가지 색상 규칙을 통해 트리의 균형을 유지합니다.
- 삽입과 삭제 시에는 적은 회전 연산이 필요하며, AVL 트리보다 삽입과 삭제 성능이 더 나을 수 있습니다.
- Java의
TreeMap과TreeSet자료구조가 Red-Black 트리로 구현되어 있습니다.
다음 포스팅부터는 BST의 균형을 유지하는 AVL 트리와 Red-Black 트리를 각각 다루어 보겠습니다.
- 각 트리의 균형 조정 알고리즘과 구현을 살펴보며, 왜 균형 트리가 필수적인지 구체적으로 알아보겠습니다.
마무리
이번 포스팅에서는 이진 탐색 트리(BST)의 개념과 주요 연산인 탐색, 삽입, 삭제를 살펴보았습니다.
- BST는 데이터를 효율적으로 관리하고 탐색하는 데 매우 유용한 자료구조이지만, 비균형 트리가 발생할 경우 성능이 저하될 수 있다는 한계를 가지고 있습니다.
이러한 한계를 해결하기 위해, 균형을 유지하는 트리인 AVL 트리와 Red-Black 트리와 같은 균형 이진 탐색 트리(Self-balancing BST)가 필요하게 됩니다.
- 이들 트리는 회전 연산을 통해 트리의 균형을 유지하고, 항상 O(log n)의 성능을 보장합니다.
다음 포스팅에서 균형 이진 탐색 트리의 대표적인 두 가지 유형 중 AVL 트리를 먼저 다루고 이후 포스팅에서 Red-Black 트리에 대해 다루어 보겠습니다.
일 때문에 포스팅은 잠시 쉬어요 ㅠ 바쁘다 바빠 모두들 화이팅! // Machine Learning (AI) Engineer & BackEnd Engineer (Entry)