자료구조 정리 - 트리(Tree)의 개념과 이진 트리

트리 (Tree)

핵심 개념:

계층 구조 (부모-자식 관계)
하나의 루트(root)에서 시작
사이클 없음 (순환 안 함)

트리의 기본 용어

        1          ← 루트 (Root)
       / \
      2   3        ← 자식 (Children), 1의 자식
     / \   \
    4   5   6      ← 리프 (Leaf, 자식 없는 노드)

트리 용어 - 완전판

깊이 (Depth)

루트부터 그 노드까지의 거리
노드 1의 깊이: 0
노드 2의 깊이: 1
노드 4의 깊이: 2

높이 (Height)

그 노드부터 가장 깊은 리프까지의 거리
노드 4의 높이: 0 (리프니까)
노드 2의 높이: 1 (자식까지 1칸)
노드 1의 높이: 2 (가장 깊은 리프까지 2칸)

트리의 높이 = 루트의 높이

레벨 (Level)

깊이랑 같은 말
노드 1: 레벨 0
노드 2, 3: 레벨 1
노드 4, 5, 6: 레벨 2

차수 (Degree)

자식의 개수
노드 1의 차수: 2 (자식 2개)
노드 2의 차수: 2 (자식 2개)
노드 3의 차수: 1 (자식 1개)
노드 4의 차수: 0 (리프)

형제 (Sibling)

같은 부모를 가진 노드
노드 2와 3: 형제
노드 4와 5: 형제

조상 (Ancestor)

그 노드의 부모, 부모의 부모, ...
노드 4의 조상: 2, 1

자손 (Descendant)

그 노드의 자식, 자식의 자식, ...
노드 1의 자손: 2, 3, 4, 5, 6

서브트리 (Subtree)

어떤 노드를 루트로 하는 트리

노드 2를 루트로 하는 서브트리:
      2
     / \
    4   5

용어 정리

용어	의미	예시 (노드 4 기준)
깊이 (Depth)	루트부터 그 노드까지	2
높이 (Height)	그 노드부터 가장 깊은 리프까지	0
레벨 (Level)	깊이랑 같음	2
차수 (Degree)	자식 개수	0
부모 (Parent)	위 노드	2
자식 (Children)	아래 노드	없음
형제 (Sibling)	같은 부모	5
조상 (Ancestor)	부모, 부모의 부모...	2, 1
자손 (Descendant)	자식, 자식의 자식...	없음

트리의 특징

노드 N개 → 간선 N-1개
- 위 예시: 노드 6개, 간선 5개
루트는 하나
사이클 없음

   1 → 2 → 3 → 1  ← 이런 순환 없음!

모든 노드는 연결됨

이진 트리 (Binary Tree)

핵심: 자식이 최대 2개

노드 2: 자식 2개 (4, 5)
노드 3: 자식 0개
노드 1: 자식 2개 (2, 3)

자식이 3개면? → 이진 트리 아님!

이진 트리 종류

1. 포화 이진 트리 (Full Binary Tree)

모든 레벨이 꽉 참
리프가 모두 같은 레벨

2. 완전 이진 트리 (Complete Binary Tree)

왼쪽부터 차례로 채워짐
마지막 레벨만 오른쪽이 비어있을 수 있음

힙(Heap)이 이것!

3. 편향 트리 (Skewed Tree)

한쪽으로만 치우침
사실상 연결 리스트

이진 트리 구현

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None   # 왼쪽 자식
        self.right = None  # 오른쪽 자식

# 트리 만들기
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

#       1
#      / \
#     2   3
#    / \
#   4   5

트리 순회 (Traversal)

방문 순서에 따라 3가지:

1. 전위 순회 (Preorder) - Root → Left → Right

        1
       / \
      2   3
     / \
    4   5

순서: 1 → 2 → 4 → 5 → 3
(루트 먼저!)

def preorder(node):
    if node is None:
        return
    
    print(node.val)      # 루트
    preorder(node.left)   # 왼쪽
    preorder(node.right)  # 오른쪽

2. 중위 순회 (Inorder) - Left → Root → Right

        1
       / \
      2   3
     / \
    4   5

순서: 4 → 2 → 5 → 1 → 3
(왼쪽 → 루트 → 오른쪽)

def inorder(node):
    if node is None:
        return
    
    inorder(node.left)   # 왼쪽
    print(node.val)      # 루트
    inorder(node.right)  # 오른쪽

이진 탐색 트리에서 중위 순회 → 정렬된 순서!

3. 후위 순회 (Postorder) - Left → Right → Root

        1
       / \
      2   3
     / \
    4   5

순서: 4 → 5 → 2 → 3 → 1
(루트를 마지막에!)

def postorder(node):
    if node is None:
        return
    
    postorder(node.left)   # 왼쪽
    postorder(node.right)  # 오른쪽
    print(node.val)        # 루트

용도: 트리 삭제 (자식부터 지워야 함)

레벨 순회 (Level Order) - BFS

        1
       / \
      2   3
     / \
    4   5

순서: 1 → 2 → 3 → 4 → 5
(레벨별로!)

from collections import deque

def levelorder(root):
    if root is None:
        return
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        print(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

정리

트리:

계층 구조
사이클 없음
루트 하나

이진 트리:

자식 최대 2개

순회:

전위: Root → Left → Right
중위: Left → Root → Right (정렬 순서)
후위: Left → Right → Root (삭제)
레벨: BFS (큐 사용)

이진 트리 vs 이진 탐색 트리

이진 트리 (Binary Tree)

그냥 자식이 최대 2개인 트리
순서 규칙 없음

→ 아무렇게나 배치 가능

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

자식이 최대 2개 + 순서 규칙 있음

규칙:

왼쪽 자식 < 부모 < 오른쪽 자식

확인:

5의 왼쪽(3) < 5 < 5의 오른쪽(8) ✓
3의 왼쪽(2) < 3 < 3의 오른쪽(4) ✓
8의 오른쪽(9) > 8 ✓

BST의 핵심 특징

1. 중위 순회하면 정렬된 순서!

      5
     / \
    3   8
   / \   \
  2   4   9

중위 순회 (Left → Root → Right):
2 → 3 → 4 → 5 → 8 → 9

→ 오름차순 정렬!

2. 탐색이 빠름

      5
     / \
    3   8
   / \   \
  2   4   9

8을 찾는다면?
1. 5와 비교 → 8 > 5 → 오른쪽으로
2. 8 발견!

2단계만에 찾음!

시간복잡도:

평균: O(log n)
최악: O(n) (편향 트리일 때)

BST 연산

1. 탐색 (Search)

      5
     / \
    3   8
   / \   \
  2   4   9

4를 찾는다:
1. 5와 비교 → 4 < 5 → 왼쪽
2. 3과 비교 → 4 > 3 → 오른쪽
3. 4 발견!

과정:

찾는 값 < 현재 노드 → 왼쪽
찾는 값 > 현재 노드 → 오른쪽
찾는 값 = 현재 노드 → 찾음!

2. 삽입 (Insert)

      5
     / \
    3   8
   / \
  2   4

6을 추가한다:
1. 5와 비교 → 6 > 5 → 오른쪽
2. 8과 비교 → 6 < 8 → 왼쪽
3. 빈 자리 → 여기 삽입!

결과:
      5
     / \
    3   8
   / \ /
  2  4 6

규칙:

리프까지 내려가서 삽입
BST 규칙 유지

3. 삭제 (Delete)

3가지 경우:

Case 1: 자식 없음 (리프)

Case 2: 자식 1개

      5
     / \
    3   8
     \   \
      4   9

3을 삭제:
→ 자식(4)을 3 자리로

      5
     / \
    4   8
         \
          9

Case 3: 자식 2개 (복잡!)

      5
     / \
    3   8
   / \   \
  2   4   9

5를 삭제:

방법 1: 왼쪽 서브트리의 최대값(4)으로 대체
      4
     / \
    3   8
   /     \
  2       9

방법 2: 오른쪽 서브트리의 최소값(8)으로 대체
      8
     / \
    3   9
   / \
  2   4

이유:

BST 규칙 유지해야 함
왼쪽 최대값 또는 오른쪽 최소값만 가능

시간복잡도

연산평균최악

탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

최악의 경우 - 편향 트리

삽입 순서: 1, 2, 3, 4, 5

결과:
1
 \
  2
   \
    3
     \
      4
       \
        5

→ 사실상 연결 리스트!
→ 탐색 O(n)

문제:

BST인데 느림
균형이 안 맞음

해결:

균형 이진 탐색 트리 (AVL, Red-Black Tree)

정리

이진 트리:

자식 최대 2개
규칙 없음

이진 탐색 트리 (BST):

자식 최대 2개
왼쪽 < 부모 < 오른쪽 (규칙 있음!)
탐색/삽입/삭제 평균 O(log n)
중위 순회 → 정렬됨

장점:

탐색 빠름 (정렬된 배열처럼)
삽입/삭제 가능 (배열보다 나음)

단점:

편향되면 느림 (O(n))

'개발공부 > 자료구조' 카테고리의 다른 글

자료구조 정리 - 힙(Heap) (0)	2025.10.03
자료구조 정리 - AVL 트리와 Red-Black 트리 (0)	2025.10.03
자료구조 정리 - 해시(Hash) (0)	2025.10.03
자료구조 정리 - 스택(Stack)과 큐(Queue) 그리고 덱(Deque) (0)	2025.10.03
자료구조 정리 - 배열(Array)과 리스트(List) (0)	2025.10.03

트리 (Tree)

트리의 기본 용어

용어 정리

트리의 특징

이진 트리 (Binary Tree)

이진 트리 종류

1. 포화 이진 트리 (Full Binary Tree)

2. 완전 이진 트리 (Complete Binary Tree)

3. 편향 트리 (Skewed Tree)

이진 트리 구현

트리 순회 (Traversal)

1. 전위 순회 (Preorder) - Root → Left → Right

2. 중위 순회 (Inorder) - Left → Root → Right

3. 후위 순회 (Postorder) - Left → Right → Root

레벨 순회 (Level Order) - BFS

정리

이진 트리 vs 이진 탐색 트리

이진 트리 (Binary Tree)

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

BST의 핵심 특징

1. 중위 순회하면 정렬된 순서!

2. 탐색이 빠름

BST 연산

1. 탐색 (Search)

2. 삽입 (Insert)

3. 삭제 (Delete)

Case 1: 자식 없음 (리프)

Case 2: 자식 1개

Case 3: 자식 2개 (복잡!)

시간복잡도

최악의 경우 - 편향 트리

정리

'개발공부 > 자료구조' 카테고리의 다른 글

티스토리툴바