[TIL] 알고리즘&자료구조: 트리와 바이너리 인덱스 트리
3. 트리 자료구조 (Tree)
가계도처럼 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
- 트리 관련 용어
- 루트 노드: 부모가 없는 최상위 노드
- 단말 노드: 자식이 없는 노드
- 크기: 트리에 포함된 모든 노드의 개수
- 깊이: 루트 노드부터의 거리
- 높이: 깊이 중 최댓값
- 차수: 각 노드의 자식 방향 간선 개수
📌 트리 크기가 N일 때 전체 간선의 개수는 N-1
3-1. 이진 탐색 트리(Binary Search Tree)
- 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조
- 특징
- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
- 부모 노드보다 왼쪽 자식 노드가 작다.
- 부모 노드보다 오른쪽 자식 노드가 크다.
- 데이터 조회 과정
- 루트 노드부터 방문하여 탐색 진행
- 현재 노드와 찾는 원소 값을 비교
- 찾는 원소가 더 크면 오른쪽 노드 방문
- 현재 노드가 찾는 원소보다 더 크면 왼쪽 노드 방문
- 찾는 원소에 다다를 때까지 반복
3-2. 트리의 순회
트리 자료구조에 포함된 노드를 특정 방법으로 한 번씩 방문하는 방법. 트리의 정보를 시각적으로 확인할 수 있으므로 자주 사용한다.
- 트리 순회 방법
- 전위 순회: 루트➡왼쪽 자식➡오른쪽 자식
- 중위 순회: 왼쪽 자식➡루트➡오른쪽 자식
- 후위 순회: 왼쪽 자식➡오른쪽 자식➡루트
📌 구현 예제
class Node:
def __init__(self, data, left_node, right_node):
self.data = data
self.left_node = left_node
self.right_node = right_node
# 전위 순회
def pre_order(node):
print(node.data, end=' ')
if node.left_node != None:
in_order(tree[node.left_node])
print(node.data, end=' ')
if node.right_node != None:
in_order(tree[node.right_node])
# 중위 순회
def in_dorder(node):
if node.left_node != None:
in_order(tree[node.left_node])
print(node.data, end=' ')
if node.right_node != Nonde:
in_order(tree[node.right_node])
# 후위 순회
def post_order(node):
if node.left_node != None:
post_order(tree[node.left_node])
if node.right_node != None:
post_order(tree[node.right_node])
print(node.data, end=' ')
n = int(input())
tree = []
for i in range(n):
data, left_node, right_node = input().split()
if left_node == "None":
left_node = None
if right_node == "None":
right_node = None
tree[data] = Node(data, left_node, right_node)
pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])
4. 바이너리 인덱스 트리 (Binary Indexed Tree)
a.k.a. BIT, 펜윅 트리(Fenwick Tree). 이진법 인덱스 구조를 활용해서 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조
👉 구간 합 알고리즘 문제: https://www.acmicpc.net/problem/2042
-
정수에 따른 이진수 표기 예시
정수 이진수 표기 7 00000000 00000000 00000000 0000111 -7 11111111 11111111 11111111 1111001 -
0이 아닌 마지막 비트를 찾는 방법
- 특정 숫자 K의 0이 아닌 마지막 비트 계산: K & -K
n = 8 for i in range(n+1): print(i, "의 마지막 비트:", (i & -i))
-
바이너리 인덱스 트리 구현 동작 원리
-
생성: 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수
-
업데이트
-
특정 값을 변경하는 경우: 0이 아닌 마지막 비트만큼 더하면서 구간들의 값을 변경
예) 3번 값 변경: 1~4번 값 변경 ➡ 1~8번 값 변경 ➡ 1~16번값 변경
-
-
누적 합 구하기
-
1부터 N까지의 누적 합: 0이 아닌 마지막 비트만큼 빼면서 구간들의 값의 합을 계산
예) 11번까지 누적 합 구하기: 11번 값 + 9~10번 값 + 1~8번 값
-
-
📌 구현 예시
import sys
input = sys.stdin.readline
# 데이터의 개수(n), 변경 횟수(m), 구간 합 계산 횟수(k)
n, m, k = map(int, input().split())
# 전체 데이터의 개수는 최대 1,000,000개
arr = [0] * (n + 1)
tree = [0] * (n + 1)
# i번째 수까지의 누적 합을 계산하는 함수
def prefix_sum(i):
result = 0
while i > 0:
result += tree[i]
# 0이 아닌 마지막 비트만큼 빼가면서 이동
i -= (i & -i)
return result
# i번째 수를 dif만큼 더하는 함수
def update(i, dif):
while i <= n:
tree[i] += dif
i += (i & -i)
# start부터 end까지의 구간 합을 계산하는 함수
def interval_sum(start, end):
return prefix_sum(end) - prefix_sum(start - 1)
for i in range(1, n + 1):
x = int(input())
arr[i] = x
update(i, x)
for i in range(m + k):
a, b, c = map(int, input().split())
# 업데이트 연산인 경우
if a == 1:
update(b, c - arr[b]) # 바뀐 크기(dif)만큼 적용
else:
print(interval_sum(b, c))
Author And Source
이 문제에 관하여([TIL] 알고리즘&자료구조: 트리와 바이너리 인덱스 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minami/알고리즘자료구조-트리와-바이너리-인덱스-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)