밤둘레

1. 트리(Tree)

트리는 정점(Node)와 선분(Branch)을 이용하여 사이클이 이루어지지 않게 구성된 자료구조이다.

 트리의 특징

• 트리는 계층 모델이다.
• 트리는 비순환 그래프이다.
• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
• 순회는 Pre-order, In-order, Post-order로 이루어진다.
• 트리는 이진트리, 이진 탐색 트리, 균형 트리, 이진 힙 등이 있다.

트리의 용어

• 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드 만을 가진다.
• 단말 노드(leaf node) : 자식이 없는 노드
• 내부(internal) 노드 : 단말 노드가 아닌 노드
• 간선(edge) : 노드를 연결하는 선
• 형제(sibling) : 같은 부모를 가지는 노드
• 조상 노드(ancestors node) : 임의의 노드에서 루트 노드에 이르는 경로상에 있는 노드들 (D의 조상은 B, A이다) 
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 커쳐야하는 간선 수
• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree) : 각 노드에서 뻗어나온 가지의 수 (D의 차수는 2이다.)
• 트리의 차수(degree of tree) : 트리에서 가장 큰 차수 
• 트리의 높이(height) : 가장 깊숙히 있는 노드의 깊이 (3)

2. 그래프(Graph)

노드와 노드를 연결하는 간선들로 구성된 자료구조

그래프의 특징

• 그래프틑 네트워크 모델이다.
• 노드들 사이에 방향/무방향 경로를 가질 수 있다.
• 그래프틑 순환 혹은 비순환이다.
• 그래프틑 크게 방향 그래프와 무방향 그래프가있다.

그래프의 용어

• 정점(vertext) : 위치라는 개념
• 간선(edge) : 정점을 연결하는 선
• 인접 정점(adjacent vertex) : 간선에 직접 연결된 정점
• 차수(degree) : 한 정점에 연결된 간선의 수 (주로 무방향 그래프에서 사용)
• 입력 차수(in-degree) : 한 정점으로 들어오는 간선의 수 (주로 방향그래프에서 사용)
• 출력 차수(out-degree) : 한 정점에서 나가는 간선의 수(주로 방향그래프에서 사용)
• 사이클(cycle) : 한 정점에서 출발하여 시작했던 정점으로 돌아오는 경로
• 가중치 그래프 : 간선마다 가중치 값이 매겨져있는 그래프

그래프의 종류

무방향 그래프(Undirected Graph)

• 간선을 통해 양방향으로 갈 수 있다.
• 정점 A와  정점 B를 연결하는 간선은 (A,B), (B,A) 이다.

방향 그래프(Directed Graph)

• 간선에 방향성이 존재하는 그래프
• A -> B로 갈 수 있는 간선은 (A, B)로 표시한다. 

가중치 그래프(Weighted Graph)

• 간선을 이동하는데 비용이나 가중치가 할당된 그래프
• 네트워크라고도 한다.

참조 : https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

https://justicehui.github.io/easy-algorithm/2018/03/19/GraphIntro/

1. 배열(Array)

배열은 특정 자료형들이 메모리 공간상에 연속적으로 이루어져 있는 자료구조이다.

배열의 특징

• 메모리상에 연속적으로 저장되는 특성 때문에, 데이터 접근 속도가 빠르다.
• 인덱스를 통해 접근하기 때문에 어떤 열에 접근하더라도 접근하는 속도가 같다.
• 배열의 최대크기를 변경 할 수 없다.
• 삽입/삭제 시 자료의 이동이 생기기 때문에 오버헤드가 발생한다.

2. 연결리스트(LinkedList)

연결리스트는 여러개의 노드들이 연결된 형태의 자료구조이다. 메모리상에 노드들이 흩어져 있으며, 각각의 노드는 다음 노드에 대한 위치 정보를 저장하고 있다. 

연결리스트의 특징

• 노드는 자료와 링크로 구성된다.
• 배열 보다 삽입, 삭제 연산이 빠르다.
• head와 tail이 존재한다. head는 가장 첫번째 노드를 의미하고, tail은 가장 마지막 노드를 의미한다.
• 자료 외에 링크를 저장하는 변수가 필요함으로 배열 보다 메모리 효율이 떨어진다.
• 링크가 중간에 끊어지면 다음 노드를 찾는 것이 어렵다.
• 단순 연결 리스트, 이중 연결리스트, 환형 연결 리스트가 존재한다.

3. 스택

가장 최근에 저장한 자료를 먼저 꺼내는 LIFO(Last In First Out)방식의 자료 구조이다.

스택의 특징

• 리스트의 마지막 인덱스에서 삽입과 삭제 연산을 수행한다.
• 마지막으로 저장된 자료의 인덱스를 저장하며 해당 인덱스를 TOP이라고 부른다.
• 자료를 저장하는 연산을 PUSH라고 한다.
• 자료를 꺼내는 연산을 POP이라고 한다.
• 함수 호출 순서 제어, 인터럽트 처리, 수식계산 등 에서 사용한다.

4. 큐

가장 먼저 저장한 자료를  먼저 꺼내는 FIFO(First In First Out) 방식의 자료구조이다.

큐의 특징

• 가장 먼저 저장한 자료의 위치를 기억하며 Front라고 부른다.
• 새로운 자료를 보관할 위치를 기억하며 Rear라고 부른다.
• 큐에 자료를 보관하는 연산을 Put 혹은 Enqueue라고 부른다.
• 큐에 자료를 꺼내는 연산을 Get 혹은 Dequeue라고 부른다.
• 스케줄러, 대기순서에 따라 처리되는 연산 등 에서 사용한다. 

참조 : http://ehpub.co.kr/tag/%EC%8A%A4%ED%83%9D%EC%9D%98-%ED%8A%B9%EC%A7%95/