트리 | Tree

---

내가 볼려고 작성한 알고리즘 공부.

💾 트리 (Tree)

✅ 1. 트리란?

트리(Tree)는 사이클이 없는 연결 그래프의 일종으로, 계층적 구조를 표현할 때 자주 사용되는 자료구조이다. 하나의 루트 노드에서 시작해 자식 노드로 가지를 뻗는 계층형 구조이며, 노드 간에 유일한 경로만 존재한다.

📌 트리 용어 정리

용어	설명
루트(Root)	트리의 시작점이 되는 노드
리프(Leaf)	자식이 없는 끝 노드
부모/자식	계층 관계 (부모는 자식을 가짐)
서브트리	어떤 노드를 루트로 하는 하위 트리
높이(Height)	루트에서 리프까지 가장 긴 경로의 길이

트리는 파일 시스템, 조직도, HTML 구조, 탐색 알고리즘, 구간 계산 등에서 폭넓게 사용된다.

✅ 2. 이진 트리와 순회

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리이다. 순회(traversal)는 트리의 모든 노드를 특정한 순서로 방문하는 방식이다.

📌 Node 클래스 설계

파이썬에서는 별도의 트리 라이브러리를 import하지 않고, 클래스를 직접 만들어서 트리를 구성한다.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 예시 트리 구성
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리이다. 순회(traversal)는 트리의 모든 노드를 특정한 순서로 방문하는 방식이다.

2.1 전위 순회 (Pre-order)

• 방문 순서: 루트 → 왼쪽 → 오른쪽
• 예: 수식 트리에서 전위 표현식 출력

def preorder(node):
    if node:
        print(node.value)
        preorder(node.left)
        preorder(node.right)

2.2 중위 순회 (In-order)

• 방문 순서: 왼쪽 → 루트 → 오른쪽
• 예: 이진 탐색 트리에서 오름차순 정렬 출력

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value)
        inorder(node.right)

2.3 후위 순회 (Post-order)

• 방문 순서: 왼쪽 → 오른쪽 → 루트
• 예: 디렉토리 삭제 시, 하위 폴더부터 삭제

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value)

✅ 3. 세그먼트 트리 (Segment Tree)

구간 합, 구간 최대값 등을 빠르게 구하고 업데이트할 수 있는 트리 자료구조이다. 구간 질의(쿼리)와 값 변경을 모두 빠르게 처리해야 할 때 사용한다.

3.1 기본 아이디어

• 배열을 기반으로 트리를 구성
• 리프 노드: 배열 원소 값
• 내부 노드: 하위 노드들의 합/최댓값 등 요약 정보 저장

3.2 코드 예제 (구간 합)

def build(arr):
    n = len(arr)
    tree = [0] * (2 * n)
    for i in range(n):
        tree[n + i] = arr[i]
    for i in range(n - 1, 0, -1):
        tree[i] = tree[2 * i] + tree[2 * i + 1]
    return tree

def query(tree, l, r, n):  # [l, r)
    l += n
    r += n
    res = 0
    while l < r:
        if l % 2:
            res += tree[l]
            l += 1
        if r % 2:
            r -= 1
            res += tree[r]
        l //= 2
        r //= 2
    return res

• 시간 복잡도: O(log N) (구간 합, 업데이트 모두)

✅ 4. 펜윅 트리 (Fenwick Tree, Binary Indexed Tree)

세그먼트 트리보다 구현은 간단하지만 구간 쿼리가 누적합일 때만 사용 가능한 트리 구조. 메모리는 적고 빠르며, 실무에서 자주 활용된다.

4.1 코드 예제

def update(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += (i & -i)

def prefix_sum(bit, i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= (i & -i)
    return res

• 시간 복잡도: O(log N)

✅ 5. 트리 관련 연습 문제

난이도	문제 링크
⭐	백준 1991 - 트리 순회
⭐⭐	백준 10868 - 최솟값
⭐⭐⭐	백준 2042 - 구간 합 구하기
⭐⭐⭐⭐	백준 10999 - 구간 합과 구간 업데이트

✅ 6. 문제 풀이

• 백준 1991 - 트리 순회

import sys
input = sys.stdin.readline

class Node:
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None
nodes = {}
child = set()
n = int(input())
for _ in range(n):
    a, b, c = input().strip().split()
    if a not in nodes:
        nodes[a] = Node(a)
        child.add(b)
    parent = nodes[a]
    
    
    if b != '.':
        if b not in nodes:
            nodes[b] = Node(b)
        parent.left = nodes[b]
    if c != '.':
        if c not in nodes:
            nodes[c] = Node(c)
            child.add(c)
        parent.right = nodes[c]
for name in nodes:
    if name not in child:
        root = nodes[name]
        break
        
def preorder(node,result):
    if node:
        result.append(node.value)
        preorder(node.left,result)
        preorder(node.right,result)
    return result
def inorder(node,result):
    if node:
        inorder(node.left,result)
        result.append(node.value)
        inorder(node.right,result)
    return result
def postorder(node,result):
    if node:
        postorder(node.left,result)
        postorder(node.right,result)
        result.append(node.value)
    return result
print(''.join(preorder(root,[])))
print(''.join(inorder(root,[])))
print(''.join(postorder(root,[])))

• 백준 10868 - 최솟값

이슈 :

• 원인:
• 해결:

• 백준 2042 - 구간 합 구하기

이슈 :

• 원인:
• 해결:

• 백준 10999 - 구간 합과 구간 업데이트

이슈 :

• 원인:
• 해결: