Tree🌳

Tree 자료구조는 이름 그대로 나무의 형태를 가지고있다 하지만 나무를 거꾸로 뒤집은 모습이다.
단반향 그래프의 한 구조로, 뿌리부터 가지까지 사방으로 뻗어나가는게 나무와 유사해서 트리 구조이다.

이미지 출처

트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다
데이터를 순차적으로 나열시킨 선형 구조가 아닌, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형구조 이다.

트리 구조는 root를 시작점으로 여러 개의 데이터를 간선으로 연결한다.
하나 하나의 원들을 '노드(Node)' 라고 부른다.

노드끼리 연결될 시 상위 노드를 부모 노드(parent Node), 하위 노드를 자식 노드 (Child Node) 라 한다.
이렇게 자식이 없는 노드는 리프 노드(Leaf Node) 라고 한다.

또한 트리 구조는 깊이와 높이, 레벨을 측정할 수 있는데,

깊이(depth)

트리 구조에선 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다.
루트 노드는 지면에 있는 것처럼 깊이는 0 이다.
루트 A 깊이는 0
루트 B,C 깊이는 1
루트 D,E,F,G 깊이는 2
내려갈수록 숫자는 증가한다

레벨(level)

트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현이 가능하다.

level1 : 루트 A 깊이는 0
level2 : 루트 B,C 깊이는 1
level3 : 루트 D,E,F,G 깊이는 2

이렇게 동일한 레벨에 나란히 있는 노드를 형제 노드(Sibling Node) 라 한다.

높이(Height)

트리 구조에서 리프 노드를 기준으로 루트까지의 높이 표현이 가능하다
리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height + 1 한 값을 가진다.

리프 노드는 높이를 0 으로 놓는다.
그림 예제에서 리프 노드는 H,I,E,F,J 이며 높이는 0 이다.
D,G의 높이는 1
B,C의 높이는 2
루트 A의 높이는 3 이다.

서브 트리(Sub tree)

트리 구조의 루트에서 시작 된 큰 트리에 내부에서 트리 구조를 갖춘 작은 트리를 서브 트리 라고한다.
간략하게 세 개의 서브 트리를 표현했다.
(B D E)
(D H I)
(C F G J)

---

용어 정리

• 노드 : 트리 구조를 이루는 모든 개별 데이터
• 루트 : 트리 구조의 시작점이 된 노드
• 부모 노드 : 두 노드가 상하관계로 연결되어 있을때 루트와 더 가까운 노드
• 자식 노드 : 두 노드가 상하관계로 연결될 때 상대적으로 루트와 먼 노드
• 리프 : 트리 구조의 끝 지점, 자식 노드가 없는 노드

Graph

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조 이다.
수학에서의 그래프와 컴퓨터 공학에서 설명하는 자료구조 그래프는 다른 모습이다
자료구조 그래프는 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망 처럼 생겼다.

Graph 구조

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
하나의 점을 그래프에선 정점(vertex)라 하며, 하나의 간선(edge)라 한다.

위 그래프에서 V(vertex)= {0,1,2,3,4} E(edges) = {01,12,23,34,04,14,13}으로 표현이 가능하다

Graph의 표현 방식

인접 행렬

두 정점을 이어주는 간선이 있다며 이 두 정점은 인접하다라 말한다.
인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타난다.

인접행렬은 언제 사용되나?

• 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인에 용이하다
• 가장 빠른 경로를 찾고자 할 때 주로 사용된다

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다
각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

간선의 순서는 보통으론 중요하지 않다
그래프, 트리, 스택, 큐 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제가 가능하며, 그래프를 인접 리스트로 구현할 땐 정점별로 살펴봐야 할 우선 순위를 고려해 구현할수도 있다.
이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있다.
만약 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.

인접 리스트는 언제 사용되나?

• 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
  (인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다)

인접 행렬과 인접 리스트의 장단점

--	인접 행렬	인접 리스트
시간복잡도	O(N^2) 정점 N * N만큼 필요	O(N) N : 간선의 개수
두 정점의 연결 여부	graph[x][y] 의 값으로 한번에 확인	graph 의 원소에서 y가 나올때까지 탐색
인접 노드 파악 여부	N * N만큼 반복문을 돌아 확인한다.	각 리스트에 담겨있는 원소를 확인한다

행렬의 경우, 두 정점이 연결되어 있는지 확인하는 방법이 쉽다.
graph[x][y]의 값을 바로 확인해 유무를 판단 할 수 있기 때문
단, 정점이 N개인 경우, 행렬을 만들기 위해선 N*N 만큼의 공간이 필요하다
무방향 그래프의 경우엔 절반의 공간이 낭비되는 셈

리스트의 경우, 실제 연결된 노드들만 리스트 원소에 담겨있으므로 공간 복잡도가 N(간선)이다.
다만, 두 정점 x,y가 연결되어있는지 알고 싶으면 노드x 리스트로 들어가 원소 y가 있는지 처음부터 쭉 탐색해야해서 행렬보다 더 많은 시간이 소요된다.

간선이 많은 그래프의 경우엔 인접 행렬을 통해 빠르게 연결 여부 확인이 가능
간선이 적은 그래프의 경우엔 인접 리스트를 통해 인접 노드를 빠르게 확인이 가능

Binary Search Tree

트리 구조는 편리한 구조를 전시하는 것 외 효율적인 탐색을 위해 사용하기도 한다

이미지출처

가장 간단하고 많이 사용한은 이진 트리(binary tree)와 이진 탐색 트리 (binary search tree)에 대해 알아보자

이진 트리는 자료의 사입, 삭제 방법에 따라 정 이진 트리(Full binary tree). 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다

• 정 이진 트리 (Full binary tree)
  • 각 노드가 0개 혹은 2 개의 자식 노드를 갖는다.
• 포화 이진 트리 (Perfect binary tree)
  • 정 이진 트리이면서 완전 이진 트리인 경우이다, 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.
• 완전 이진 트리 (Complete binary tree)
  • 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하며, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다

이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다

이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰릴수 있다
균형이 잡히지 않은 트리는 탐색하는데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제이다.
이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.

---

알아두어야 할 그래프 용어

• 정점(vertex): 노드(node)라고도 하며, 데이터가 저장되는 그래프의 기본 원소
• 간선(edge): 정점(node) 간의 관계를 나타낸다.
• 인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 말한다.
• 가중치 그래프(weighted Graph): 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프
• 비가중치 그래프(unweightd Graph): 연결의 강도가 적혀져 있지 않는 그래프
• 무(방)향 그래프 (undirected graph): 서울에서 부산을 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능하다, 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산은 갈수 있지만, 부산에서 서울로 가는 것은 불가하다(반대로 되도 마찬가지). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현이 가능하다.
• 진입차수(in-degree)/진출차수(out-degree): 한 정점에 진입하고 진출하는 간선인 몇개인지 나타낸다.
• 인접(adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가져다 한다. 다른 정점을 거치지 않는다는것이 특징
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다 표현
  서울->대전->부산->서울 이동이 가능하니 사이클이 존재하는 그래프이다