[자료구조] Tree & Graph

💡 Tree

: 트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다. 이 트리라는 자료구조는 표현에 집중한다. 무엇인가를 저장하고 꺼내야 한다는 사고에서 벗어나 트리라는 자료구조를 바라보자.

 

💡 Binary Tree (이진 트리)

: 모든 노드들이 둘 이하의 자식을 가진 트리.

 

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 한다. 레벨의 값은 0 부터 시작하고 따라서 루트 노드의 레벨은 0 이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.

 

📌 Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전 이진 트리), Full Binary Tree (정 이진 트리)

- 포화 이진 트리

: 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 가짐.

 

- 완전 이진 트리

: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리입니다. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함.

 

- 정 이진 트리

:  모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리.

 

💡 BST (Binary Search Tree)

: 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.

• 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
• 규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
• 규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
• 규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

 

💡 Hash Table (해쉬 테이블)

: hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

💡 Graph (그래프)

: 그래프는 정점과 간선으로 이루어진 자료구조. 정확히는 정점간의 관계를 표현하는 조직도.

 

- 정점(vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장됨 (0, 1, 2, 3)
- 간선(edge) : 링크(arcs)라고도 하며 노드간의 관계를 나타냄
- 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점
- 단순 경로(simple-path) : 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로
- 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (정점 0의 차수는 3)
- 진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수
- 진입차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수

 

✔ 깊이우선탐색 (DFS)

: 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식입니다. 간단히 재귀호출을 사용하여 구현하거나 스택을 사용하여 구현.

 

✔ 넓이우선탐색 (BFS)

: 시작정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선방문하는 방법입니다. 일반적으로 QUEUE를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현.

💡 Heap (힙)

: 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조.