파이썬/코딩테스트
[자료구조] 트리
Suda_777
2024. 5. 17. 01:45
반응형
1. 트리의 기본 개념
- 노드(Node): 트리의 기본 구성 요소로, 데이터를 포함.
- 루트(Root): 트리의 최상위 노드.
- 간선(Edge): 두 노드를 연결하는 선.
- 부모 노드(Parent Node): 다른 노드를 가리키는 노드.
- 자식 노드(Child Node): 부모 노드에 의해 가리켜지는 노드.
- 리프 노드(Leaf Node): 자식 노드가 없는 노드.
- 서브트리(Subtree): 트리의 일부로, 특정 노드를 루트로 하는 트리.
- 깊이(Depth): 루트 노드에서 특정 노드까지의 경로 길이.
- 높이(Height): 특정 노드에서 리프 노드까지의 가장 긴 경로.
2. 트리의 종류
모든 트리의 종류를 다 공부하기에는 양이 많으니, 중요한 트리만 보고 넘어가기로 하자.
- 이진 탐색 트리(Binary Search Tree): 기본적인 트리 자료구조로, 삽입, 삭제, 탐색 연산에 익숙해지는 것이 중요
- 이진 힙(Binary Heap): 우선순위 큐 문제와 힙 정렬에 자주 등장
- 트라이(Trie): 문자열 관련 문제에서 자주 등장
- 세그먼트 트리(Segment Tree): 고급 문제에서 구간 쿼리 처리를 위해 알아두면 좋음
4. 이진 탐색 트리(Binary Search Tree)
4.1. 설명
이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 일종으로, 각 노드가 최대 두 개의 자식을 가지며, 특정 속성을 만족하는 트리다. 이 속성은 각 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 가지는 노드들로만 구성되고, 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 가지는 노드들로만 구성된다. 이 속성을 통해 BST는 효율적인 탐색, 삽입, 삭제 연산을 가능하게 함.
주요 연산은 아래와 같다.
- 탐색(Search): 주어진 값이 트리에 있는지 확인하는 연산.
- 삽입(Insertion): 트리에 새로운 값을 추가하는 연산.
- 삭제(Deletion): 트리에서 특정 값을 제거하는 연산.
- 순회(Traversal): 트리의 모든 노드를 특정 순서로 방문하는 연산 (전위, 중위, 후위, 레벨 순서 등).
4.2. 주요 특성
- 왼쪽 서브트리의 값 < 현재 노드의 값
- 오른쪽 서브트리의 값 > 현재 노드의 값
- 각 서브트리도 BST여야 한다
4.3. 트리 순회 (Tree Traversal)
트리 순회(Tree Traversal)는 트리 자료구조의 모든 노드를 일정한 순서로 방문하는 과정을 의미한다.
- 전위 순회 (Pre-order Traversal)
- 순서: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
- 사용 예: 트리 구조를 복제하거나, 표현식을 전위 표기법으로 변환할 때 사용.
- 중위 순회 (In-order Traversal)
- 순서: 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
- 사용 예: 이진 탐색 트리에서 중위 순회를 하면 오름차순으로 정렬된 결과를 얻을 수 있다.
- 후위 순회 (Post-order Traversal)
- 순서: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트
- 사용 예: 트리 구조를 삭제하거나, 표현식을 후위 표기법으로 변환할 때 사용.
- 레벨 순서 순회 (Level-order Traversal)
- 순서: 루트에서 시작하여 같은 레벨의 노드를 왼쪽에서 오른쪽 순서로 방문
- 사용 예: 트리의 레벨별 노드 방문이 필요할 때 사용.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
class BinaryTree:
def __init__(self):
self.root = None # 트리의 루트 노드를 초기화
# 트리에 새로운 키를 삽입하는 메서드
def insert(self, key):
if self.root is None:
self.root = Node(key) # 루트 노드가 없으면 새로운 노드를 루트로 설정
else:
self._insert(self.root, key) # 그렇지 않으면 재귀적으로 삽입
# 재귀적으로 노드를 삽입하는 헬퍼 메서드
def _insert(self, current_node, key):
if key < current_node.val:
if current_node.left is None:
current_node.left = Node(key) # 왼쪽 자식 노드가 없으면 새로운 노드를 삽입
else:
self._insert(current_node.left, key) # 왼쪽 자식 노드가 있으면 재귀적으로 삽입
else:
if current_node.right is None:
current_node.right = Node(key) # 오른쪽 자식 노드가 없으면 새로운 노드를 삽입
else:
self._insert(current_node.right, key) # 오른쪽 자식 노드가 있으면 재귀적으로 삽입
# 전위 순회(Pre-order traversal) 메서드
def preorder_traversal(self, node):
if node:
print(node.val, end=" ") # 현재 노드를 출력
self.preorder_traversal(node.left) # 왼쪽 서브트리를 재귀적으로 순회
self.preorder_traversal(node.right) # 오른쪽 서브트리를 재귀적으로 순회
# 중위 순회(In-order traversal) 메서드
def inorder_traversal(self, node):
if node:
self.inorder_traversal(node.left) # 왼쪽 서브트리를 재귀적으로 순회
print(node.val, end=" ") # 현재 노드를 출력
self.inorder_traversal(node.right) # 오른쪽 서브트리를 재귀적으로 순회
# 후위 순회(Post-order traversal) 메서드
def postorder_traversal(self, node):
if node:
self.postorder_traversal(node.left) # 왼쪽 서브트리를 재귀적으로 순회
self.postorder_traversal(node.right) # 오른쪽 서브트리를 재귀적으로 순회
print(node.val, end=" ") # 현재 노드를 출력
# 레벨 순서 순회(Level-order traversal) 메서드
def level_order_traversal(self, node):
if not node:
return
from collections import deque # 큐 자료구조를 사용하기 위해 deque 임포트
queue = deque([node]) # 루트 노드를 큐에 추가
while queue:
current_node = queue.popleft() # 큐에서 노드를 꺼냄
print(current_node.val, end=" ") # 현재 노드를 출력
if current_node.left:
queue.append(current_node.left) # 왼쪽 자식 노드를 큐에 추가
if current_node.right:
queue.append(current_node.right) # 오른쪽 자식 노드를 큐에 추가
# 트리에서 특정 값을 탐색하는 메서드
def search(self, key):
return self._search(self.root, key)
# 재귀적으로 노드를 탐색하는 헬퍼 메서드
def _search(self, current_node, key):
if current_node is None or current_node.val == key:
return current_node
if key < current_node.val:
return self._search(current_node.left, key)
return self._search(current_node.right, key)
# 트리에서 특정 값을 삭제하는 메서드
def delete(self, key):
self.root = self._delete(self.root, key)
# 재귀적으로 노드를 삭제하는 헬퍼 메서드
def _delete(self, current_node, key):
if current_node is None:
return current_node
if key < current_node.val:
current_node.left = self._delete(current_node.left, key)
elif key > current_node.val:
current_node.right = self._delete(current_node.right, key)
else:
if current_node.left is None:
return current_node.right
elif current_node.right is None:
return current_node.left
min_larger_node = self._get_min(current_node.right)
current_node.val = min_larger_node.val
current_node.right = self._delete(current_node.right, min_larger_node.val)
return current_node
# 오른쪽 서브트리에서 가장 작은 값을 가진 노드를 찾는 메서드
def _get_min(self, node):
current = node
while current.left is not None:
current = current.left
return current
# 전위 순회를 시작하는 메서드
def print_preorder(self):
self.preorder_traversal(self.root)
# 중위 순회를 시작하는 메서드
def print_inorder(self):
self.inorder_traversal(self.root)
# 후위 순회를 시작하는 메서드
def print_postorder(self):
self.postorder_traversal(self.root)
# 레벨 순서 순회를 시작하는 메서드
def print_level_order(self):
self.level_order_traversal(self.root)
# 트리 생성 및 사용 예제
bt = BinaryTree() # 이진 트리 객체 생성
bt.insert(10) # 노드 삽입
bt.insert(5)
bt.insert(20)
bt.insert(3)
bt.insert(7)
bt.insert(15)
bt.insert(25)
print("전위 순회 결과:")
bt.print_preorder() # 전위 순회 결과 출력
print("\n중위 순회 결과:")
bt.print_inorder() # 중위 순회 결과 출력
print("\n후위 순회 결과:")
bt.print_postorder() # 후위 순회 결과 출력
print("\n레벨 순서 순회 결과:")
bt.print_level_order() # 레벨 순서 순회 결과 출력
# 탐색
print("\n탐색 결과:")
node = bt.search(15)
if node:
print(f"노드 {node.val}를 찾았습니다.")
else:
print("노드를 찾지 못했습니다.")
# 삭제
bt.delete(20)
print("\n삭제 후 중위 순회 결과:")
bt.print_inorder() # 삭제 후 중위 순회 결과 출력
5. 이진 힙(Binary Heap)
5.1. 설명
이진 힙(Binary Heap)은 완전 이진 트리의 일종으로, 힙 속성을 만족하는 자료구조
5.2. 힙의 종류
- 최소 힙(Min-Heap)
- 특징: 부모 노드의 값이 자식 노드의 값보다 작거나 같다.
- 루트 노드: 트리의 최상위 노드는 최솟값을 가진다.
- 최대 힙(Max-Heap)
- 특징: 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
- 루트 노드: 트리의 최상위 노드는 최댓값을 가진다.
5.3. 주요 연산
- 삽입(insert)
- 최솟값/최댓값 추출(Extract)
- 최솟값/최댓값 조회(Get)
아래는 최소 힙을 구한 예제 코드이다.
class BinaryHeap:
def __init__(self):
self.heap = [] # 힙을 리스트로 표현
def insert(self, key):
self.heap.append(key) # 새로운 키를 힙의 끝에 추가
self._heapify_up(len(self.heap) - 1) # 새로운 키를 힙 속성에 맞게 조정
def _heapify_up(self, index):
parent_index = (index - 1) // 2
if index > 0 and self.heap[index] < self.heap[parent_index]:
self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
self._heapify_up(parent_index) # 재귀적으로 힙 속성을 만족하도록 조정
def extract_min(self):
if len(self.heap) == 0:
return None
if len(self.heap) == 1:
return self.heap.pop()
root = self.heap[0]
self.heap[0] = self.heap.pop() # 힙의 마지막 요소를 루트로 이동
self._heapify_down(0) # 힙 속성을 만족하도록 조정
return root
def _heapify_down(self, index):
smallest = index
left_child_index = 2 * index + 1
right_child_index = 2 * index + 2
if left_child_index < len(self.heap) and self.heap[left_child_index] < self.heap[smallest]:
smallest = left_child_index
if right_child_index < len(self.heap) and self.heap[right_child_index] < self.heap[smallest]:
smallest = right_child_index
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
self._heapify_down(smallest) # 재귀적으로 힙 속성을 만족하도록 조정
def get_min(self):
if len(self.heap) == 0:
return None
return self.heap[0]
def print_heap(self):
print(self.heap)
# 이진 힙 생성 및 사용 예제
bh = BinaryHeap() # 이진 힙 객체 생성
# 요소 삽입
bh.insert(10)
bh.insert(5)
bh.insert(20)
bh.insert(3)
bh.insert(7)
bh.insert(15)
bh.insert(25)
print("힙의 요소들:")
bh.print_heap() # 힙의 요소 출력
# 최소값 추출
print("\n최소값 추출:")
print(bh.extract_min()) # 최소값 추출 및 출력
print(bh.extract_min()) # 두 번째 최소값 추출 및 출력
print("\n최소값 추출 후 힙의 요소들:")
bh.print_heap() # 추출 후 힙의 요소 출력
6. 트라이(Trie)
6.1. 설명
트라이(Trie)는 주로 문자열을 저장하고 효율적으로 검색하기 위해 사용하는 트리 기반의 자료구조. 트라이는 각 노드가 문자열의 한 문자를 나타내며, 노드를 따라 내려가면서 문자열을 구성함. 트라이는 특히 많은 문자열을 저장하고, 특정 문자열이나 접두사로 시작하는 문자열을 빠르게 검색할 때 유용함.
6.2. 주요 연산
- 삽입(insert)
- 검색(search)
- 접두사 검색(Prefix Search)
class TrieNode:
def __init__(self):
self.children = {} # 자식 노드를 저장하는 딕셔너리
self.is_end_of_word = False # 단어의 끝을 표시하는 플래그
class Trie:
def __init__(self):
self.root = TrieNode() # 트라이의 루트 노드 초기화
# 단어를 트라이에 삽입하는 메서드
def insert(self, word):
current_node = self.root
for char in word:
if char not in current_node.children:
current_node.children[char] = TrieNode()
current_node = current_node.children[char]
current_node.is_end_of_word = True # 단어의 끝을 표시
# 단어가 트라이에 존재하는지 확인하는 메서드
def search(self, word):
current_node = self.root
for char in word:
if char not in current_node.children:
return False
current_node = current_node.children[char]
return current_node.is_end_of_word
# 주어진 프리픽스로 시작하는 단어가 트라이에 있는지 확인하는 메서드
def starts_with(self, prefix):
current_node = self.root
for char in prefix:
if char not in current_node.children:
return False
current_node = current_node.children[char]
return True
# 트라이의 현재 상태를 출력하는 메서드 (디버깅 용도)
def print_trie(self, node=None, word=""):
if node is None:
node = self.root
if node.is_end_of_word:
print(word)
for char, child_node in node.children.items():
self.print_trie(child_node, word + char)
# 트라이 생성 및 사용 예제
trie = Trie() # 트라이 객체 생성
# 단어 삽입
trie.insert("hello")
trie.insert("hell")
trie.insert("heaven")
trie.insert("heavy")
print("트라이의 단어들:")
trie.print_trie() # 트라이의 단어들 출력
# 단어 검색
print("\n단어 'hell' 검색 결과:")
print(trie.search("hell")) # 단어 'hell'이 있는지 검색
print("\n단어 'hello' 검색 결과:")
print(trie.search("hello")) # 단어 'hello'가 있는지 검색
print("\n단어 'heav' 검색 결과:")
print(trie.search("heav")) # 단어 'heav'가 있는지 검색
# 접두사 검색
print("\n접두사 'he'로 시작하는 단어가 있는지 확인:")
print(trie.starts_with("he")) # 접두사 'he'로 시작하는 단어가 있는지 확인
print("\n접두사 'hea'로 시작하는 단어가 있는지 확인:")
print(trie.starts_with("hea")) # 접두사 'hea'로 시작하는 단어가 있는지 확인
print("\n접두사 'hi'로 시작하는 단어가 있는지 확인:")
print(trie.starts_with("hi")) # 접두사 'hi'로 시작하는 단어가 있는지 확인
7. 세그먼트 트리(Segment Tree)
7.1. 설명
세그먼트 트리(Segment Tree)는 배열의 특정 구간에 대한 질의를 빠르게 처리하기 위한 자료구조 다. 주로 구간 합, 구간 최솟값/최댓값, 구간 곱 등을 계산하는 데 사용.
7.2. 구성
- 리프 노드(Leaf Nodes): 배열의 각 요소를 나타내는 트리의 가장 아래 노드.
- 내부 노드(Internal Nodes): 각 구간의 합 또는 다른 연산 결과를 저장하는 노드.
7.3. 주요 연산
- 구간 합 쿼리(Range Sum Query): 배열의 특정 구간의 합을 계산
- 구간 업데이트(Update): 배열의 특정 인덱스의 값을 변경하고, 이 변경을 반영하기 위해 세그먼트 트리를 업데이트
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (2 * self.n)
self.build(data)
def build(self, data):
# 리프 노드를 배열의 값으로 초기화
for i in range(self.n):
self.tree[self.n + i] = data[i]
# 내부 노드를 초기화
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]
def update(self, index, value):
# 리프 노드 업데이트
pos = index + self.n
self.tree[pos] = value
# 부모 노드 업데이트
while pos > 1:
pos //= 2
self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
def range_query(self, left, right):
# 쿼리 구간을 [left, right)로 조정
left += self.n
right += self.n
result = 0
while left < right:
if left % 2:
result += self.tree[left]
left += 1
if right % 2:
right -= 1
result += self.tree[right]
left //= 2
right //= 2
return result
def print_tree(self):
print("리프 노드:", self.tree[self.n:self.n*2]) # 리프 노드 출력
print("내부 노드:", self.tree[1:self.n]) # 내부 노드 출력
# 세그먼트 트리 생성 및 사용 예제
data = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(data) # 세그먼트 트리 객체 생성
print("초기 세그먼트 트리 상태:")
seg_tree.print_tree() # 세그먼트 트리의 초기 상태 출력
# 구간 합 쿼리
print("\n구간 합 쿼리 [1, 5):")
print(seg_tree.range_query(1, 5)) # 구간 [1, 5)의 합 출력
# 업데이트
seg_tree.update(2, 10) # 인덱스 2의 값을 10으로 업데이트
print("\n업데이트 후 세그먼트 트리 상태:")
seg_tree.print_tree() # 업데이트 후 세그먼트 트리 상태 출력
# 업데이트 후 구간 합 쿼리
print("\n구간 합 쿼리 [1, 5) 업데이트 후:")
print(seg_tree.range_query(1, 5)) # 구간 [1, 5)의 합 출력반응형