5/27 (금) 자료구조 - 2️⃣ Tree 와 Graph

 

 

 

Tree구조를 발이 아닌 손으로 그린 거다.

 

 

 

❑ Tree

 

➤ 데이터 사이의 계층 관계를 나타내느 자료구조

➤ 이름 그대로 나무 모양이다.

➤ 비선형 구조

 

 

※ 용어 정리

• node(노드) : 가지로 연결되어 있는 하나하나의 요소
• edge(가지) : 노드 사이를 연결
• root(루트) : 트리의 가장 윗부분에 위치한 노드
• leaf(리프) : 가장 아랫부분에 위치한 노드, 아래에 노드가 더 이상 없는 노드
• 안쪽노드 : 리프를 제외한 나머지 노드(루트 포함)
• child node(자식 노드) : 가지로 연결된 아래쪽 노드, 노드는 자식을 여러 개 가질 수 있습니다
• parent node(부모 노드) : 가지로 연결된 윗쪽 노드, 자식 노드는 하나의 부모 노드만 가질 수 있습니다.
• sibling(형제) : 같은 부모를 가진 노드
• ancestor(조상) : 어떤 노드의 위쪽으로 뻗어 나간 모든 노드
• descendant(자손) : 어떤 노드의 아래쪽으로 뻗어 나간 모든 노드
• level(레벨) : 루트로부터 얼마나 떨어져 있는지를 나타낸 값, 루트는 레벨 0
• degree(차수) : 노드가 갖는 자식의 수, 모든 노드의 차수가 n 이하인 트리를 'n진 트리'라고 함(위의 그림은 2진 트리)
• height(높이) : 루트에서 가장 멀리 떨어진 노드까지의 거리(리프 레벨의 최댓값)
• subtree(서브트리) : 트리 안에서 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리
• null tree(널 트리) : 노드가 전혀 없는 트리

 

 

 

▶️ 순서 트리(Ordered tree)와 무순서 트리(Unordered tree)

 

형제 노드의 순서를 따지면 순서트리

형제 노드의 순서를 따지지 않으면 무순서 트리

 

 

 

▶️ 트리 = 상속

 

트리 관계를 보니까 자바의 상속이 떠오른다.

아무래도 모양이 상속관계랑 똑같은 것 같다.

상속에서 자식 클래스는 하나의 부모 클래스만 가질 수 있고

부모 클래스는 여러 자식 클래스를 가질 수 있다.

트리에서도 하나의 노드는 하나의 부모만 가질 수 있고

부모 노드는 여러 자식을 가질 수 있다.

상속 관계를 그림으로 그리면 트리 모양이다.

 

 

 

▶️ 순서 트리 탐색 방법 알아보기

 

순서 트리를 검색하는 방법에는 두가지 방법이 있다.

너비 우선 탐색(가로형 탐색)

깊이 우선 탐색(세로형 탐색)

 

 

 

 

❑ Graph

 

 

Graph

 

➤ 자료구조에서 그래프는 네트워크망 처럼 복잡하게 연결된 모양이다.

➤ 비선형 구조

 

※ 용어

• vertex(정점) : 하나의 점
• edge(간선) : 점들을 이어주는 선
• 직접적인 관계(인접하다) : 두 점을 직접적으로 이어주는 선 존재
• 간접적이 관계 : 두 점이 두개 이상의 선을 거쳐가야 하는 관계
• weighted Graph(가중치 그래프) : 연결의 강도(추가적인 정보)가 있는 그래프
• unweighted Graph(비가중치 그래프) : 연결의 강도가 없는 그래프
• in-degree(진입차수) / out-degree(진출차수) : 한 정점에 진입하고 진출하는 간선이 몇 개인지
• self loop (자기 루프) : 정점에 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 '자기 루프를 가졌다'고 표현
• cycle (사이클) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 '사이클이 있다'고 표현

 

 

▶️ 그래프의 종류

 

- undirected Graph(무방향 그래프): 간선의 방향이 없는 그래프

- directed Graph(방향 그래프): 간선에 방향성이 있는 그래프

- weighted Graph(가중치 그래프) : 연결의 강도(추가적인 정보)가 있는 그래프

- 루트 없는 트리: 간선을 통해 정점 간 잇는 방법이 한가지인 그래프

- 이분 그래프: 그래프의 간선을 두 그룹으로 나눈 후 다른 그룹끼리만 간선이 존재하게 분할할 수 있는 그래프

- 사이클이 없는 그래프: 정점에서 출발해 자기 자신으로 돌아오는 경로가 없는 그래프

 

 

▶️ 그래프의 표현

 

인접 행렬

 

- 인접행렬 : 2차원 배열로 정점 간의 간선의 존재 여부를 1 또는 0으로 표시

                  가중치 그래프일 경우 가중치로 표시하면 좋음

                  가장 빠른 경로를 찾고자 할 때 주로 사용

 

인접 리스트

 

- 인접 리스트 : 정점 개수만큼 리스트를 만들어 각각의 정점 리스트에 간선 추가

인접 행렬은 간선이 없는 경우에도 확인하기 때문에 간선이 적은 경우 간선이 있는 경우만 확인하는 인접 리스트보다 오래걸린다.

 

 

▶️ 그래프의 표현

 

관계 표현이 필요한 모든 경우에 사용 가능

활용도가 높음

- 최단 경로 탐색

- 소셜 네트워크 관계망

- 인터넷 네트워크망(전송속도 계산)

 

 

 

 

트리에 대해서 조사하다 보니까 지금 내가 보고 있는 건 빙산의 일각인 것 같다..

 

 

너무 욕심부려서 다 알려고 하지말고 궁금한건 그때그때 찾아보자

지금 공부하면 허우적거리다가 진도 못 따라갈 것 같다 ㅋㅋ

금요일에 배운것도 이틀이 지난 오늘에서야 정리한 걸 보면

내 속도가 많이 느리긴 하다.

Today I Learned인데..

이번건 Two days ago I Learned의 TIL이다..

 

 

 

 

읽어주셔서 감사합니다. 도움이 되셨기 바랍니다.

오개념에 대한 지적은 언제나 환영입니다~