[유니티 / C#] 트리(Tree)와 그래프(Grap

⭐ 비선형 자료구조

● 데이터가 계층적이거나 그래프 형태로 저장되는 구조

    ○ 나열된 형태가 아님

    ○ 서로 연결 가능 (양방향)

    ○ 1:N 또는 N:N 관계가 가능

 

 

 

⭐ 대표적인 비선형 자료구조

비선형이 특징인 자료구조로는 트리와 그래프가 있습니다.

선형 자료구조에 비해서 데이터 요소들 간의 관계가 복잡하지만 효율적인 탐색, 삽입, 삭제가 가능하기 때문에

계층적인 표현이나 경로 탐색, 데이터 관리 등에서도 쓰입니다.

 

 

트리 (Tree)

---

한 개의 루트 노드에서 시작해 여러 자식 노드로 뻗어나가는 계층적 구조입니다.

특정 기준에 따라서 트리의 종류가 여러가지로 나뉘며,

여러가지 방향으로 순회하는 방법이 있습니다.

 

● 사이클이 없음

● 노드 사이의 간선은 무조건 한개

● 트리의 간선은 부모 -> 자식으로 연결

● N개의 정점을 가지고, N - 1개의 간선을 가짐

 

📘트리와 관련된 용어 정리

● 노드(Node): 트리의 기본 단위(데이터 저장 단위)

● 루트(Root): 트리의 시작점이 되는 최상위 노드

● 간선(Edge): 노드와 노드 사이를 잇는 연결선

● 부모(Parent): 어떤 노드의 상위 노드

● 자식(Child): 부모에 직접 연결된 하위 노드

● 형제(Sibling): 같은 부모를 공유하는 노드들

● 리프(Leaf): 자식이 없는 노드(끝노드)

● 내부 노드(Internal Node): 루트와 리프 사이, 자식이 있는 노드

● 레벨(Level): 루트에서 떨어진 거리(깊이)

● 깊이(Depth): 루트에서 특정 노드까지의 경로 길이

● 높이(Height): 루트에서 가장 깊은 리프까지의 거리

● 차수(Degree): 한 노드가 가진 자식의 수

● 서브트리(Subtree): 특정 노드를 루트로 하는 작은 트리

 

 

 

 

 

 

💡 트리의 종류

트리는 노드가 가지는 자식의 수, 높이, 레벨 등 다양한 특성을 기준으로 종류가 나뉩니다.

아래의 서술된 종류 외에도 수 많은 변형 트리들이 있습니다.

 

● 일반 트리: 자식 수에 제한이 없는 가장 기본적인 트리

● 트라이: 문자열 탐색에 특화된 트리, 문자열의 각 문자가 노드로 표현됨

● 포레스트 트리: 나무가 숲을 이루는 것 처럼 하나 이상의 트리로 이루어진 집합

● 이진트리: 각 노드가 최대 두 개의 자식을 가지는 트리

    ○ 포화 이진 트리: 모든 노드가 0 또는 2개의 자식을 가지는 트리

    ○ 완전 이진 트리: 마지막 레벨만 왼쪽부터 차례대로 채워지는 트리

    ○ 정 이진 트리: 모든 내부 노드가 자식을 두 개씩 가지고, 모든 리프의 깊이가 동일한 트리

    ○ 이진 탐색 트리: 데이터를 정렬된 형태로 저장하여 효율적인 검색을 보장하는 이진트리

        ▶ 왼쪽 서브트리의 모든 값은 루트보다 작음

        ▶ 오른쪽 서브트리의 모든 값은 루트보다 큼

    ○ 균형 이진 트리: 트리의 높이가 가능한 균형을 이루는 트리, 왼쪽과 오른쪽 서브트리의 높이 차이가 1이하

    ○ 힙 트리: 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진트리

 

 

 

💡 이진트리 순회 방법

 

● 중위 순회(in-order traversal): 왼쪽 → 루트 → 오른쪽 순으로 방문하는 순회 방법

● 전위 순회(pre-order traversal): 루트 → 왼쪽 → 오른쪽 순으로 방문하는 순회 방법

● 후위 순회(post-order traversal): 왼쪽 → 오른쪽 → 루트 순으로 방문하는 순회 방법

● 레벨 순서 순회(level-order traversal): 위에서 아래로 한 레벨씩 탐색하는 순회 방법

 

https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)?from=%EC%9D%B4%EC%A7%84%20%ED%8A%B8%EB%A6%AC#s-4.1

 

● 중위 순회: 1 3 4 6 7 8 10 13 14

● 전위 순회: 8 3 1 6 4 7 10 14 13

● 후위 순회: 1 4 7 6 3 13  14 10 8

● 레벨 순서 순회: 8 3 10 1 6 14 4 7 13

 

 

 

그래프 (Graph)

---

그래프는 정점(Vertex)와 간선(Edge)으로 이루어진 비선형 자료구조입니다.

계층적으로 표현하는 트리와 달리, 복잡한 연결 관계를 직관적으로 모델링 할 수 있어

네트워크, 길찾기 시스템 등에서 널리 사용됩니다.

루트, 부모, 자식 노드의 개념이 존재하지 않습니다.

 

 

💡 그래프 구성 요소

 

● 정점(Vertex): 그래프에서 대상이나 위치를 의미 = 객체

● 간선(Edge): 두 정점 간의 관계

    ○ 방향이 있을 수도, 없을 수도 있음

    ○ 가중치(Weigth): 거리, 비용, 용량 등 연결의 크기 및 비용을 나타냄

 

 

 

💡 그래프 종류

 

● 무방향 그래프: 두 정점을 연결하는 간선의 방향이 없는 그래프

 

 

● 방향 그래프: 두 정점을 연결하는 간선 사이에 방향이 있는 그래프, 특정 방향으로만 이동 가능

    ○ 단방향, 양방향 그래프가 있습니다.

 

 

 

● 가중 그래프: 정점을 연결하는 간선에 가중치가 있는 그래프

 

 

 

● 완전 그래프: 그래프의 모든 정점들이 간선으로 연결된 그래프

 

 

 

● 다중 그래프: 두 정점이 2개 이상의 간선으로 연결된 그래프

 

 

 

● 연결 그래프: 모든 정점 사이에 간선이 존재하는 그래프

 

 

● 비연결 그래프: 모든 정점 사이에 간선이 하나라도 존재하지 않는 그래프

 

 

 

 

💡 그래프 표현 방식

 

● 인접 행렬(Adjacency matrix): 2차원 배열(행렬)을 이용하여 표현하는 방법

    ○ 정점 i와 j를 잇는 간선이 존재한다면 [i][j] = 1, 그렇지 않다면 [i][j] = 0 으로 표현

    ○ 정점의 개수가 적고, 간선의 수가 많을 때 유용한 방법

 

● 장점

    ○ 간선의 조회가 빠르고 구현이 간단

 

● 단점

    ○ 노드 추가, 제거가 오래걸림

    ○ 메모리를 많이 사용함

    ○ 특정 노드의 인접 노드를 찾거나, 그래프의 모든 간선의 수를 찾기 위해 모든 노드를 순회해야 함

 

 

 

 

● 인접 리스트(Adjacency List): 시작 정점을 기준으로 정점의 개수만큼 연결 리스트가 1차원 배열에 저장

    ○ 배열의 크기는 정점의 개수와 같음

    ○ 정점의 개수가 많고, 간선의 개수가 적을 때 유용한 방법

 

● 장점

    ○ 간선의 추가, 삭제가 용이

    ○ 정점 탐색 효율적

    ○ 연결된 정점만 저장하기 때문에 메모리를 절약

 

● 단점

    ○ 간선 존재 여부 확인이 느림

    ○ 메모리 단편화 가능성

    ○ 접근이 복잡해질 수 있음