.jpg)
자료구조는 종류가 너무 많다. 그래서인지 단순히 눈으로 보면서 공부하는 것보다는 스스로 그림을 그려보고, 블로깅을 하면서 다시 한 번 정리하는 게 헷갈리지 않고 제대로 알게 되는 느낌이랄까.. 그래서 어제오늘 배운 자료구조 역시 간단한 개념만이라도 정리해보려고 한다.
📎 Graph
그래프는 vertex(정점)를 연결하는 edge(간선)으로 이루어진 자료구조이다. 여기서 vertex는 노드이다. 그래프는 생긴 것을 보면 꼭 복잡한 네트워크 구조 같은데, 실제로 그래프는 소셜 네트워크에서도 사용된다. 예를 들면 각 유저들은 노드가 되고, 친구맺기와 같은 네트워크 기능은 edge로 나타낼 수 있다.
🏷️ Graph의 종류
- 무방향 그래프 (Undirected Graph)
한 개의 edge에 두 노드가 방향성 없이 연결되어 있는 그래프다. 무방향 그래프에서는 특정 노드를 향한 화살표가 없는데, 그래프에 방향성이 없다는 것을 말해준다.
- 방향 그래프 (Directed Graph)
한 노드에서 다른 노드로 방향성을 가지고 있는 edge가 존재하는 그래프이다. 화살표를 가진 노드에서 화살표가 가리키는 노드로는 이동할 수 있지만, 반대로 화살표가 가리켜진 노드에서 화살표를 가진 노드로는 이동할 수 없다. 위 그림을 예로 들면 A에서는 B로 이동할 수 있지만, B에서 A로는 이동이 불가능하다.
🏷️ 진입 차수 & 진출 차수
-
진입 차수 (in-degree)
: 방향 그래프에서 외부에서 오는 edge의 수 -
진출 차수 (out-degree)
: 방향 그래프에서 외부로 향하는 edge의 수
👉 진입 차수 = 진출 차수 = 모든 edge의 수
🏷️ 인접 리스트 & 인접 행렬
그래프를 구현하는 방법에는 두 가지가 있다.
- 인접 리스트 (Adjacency List)
일반적으로 많이 쓰는 방법이라고 한다. 인접 리스트는 노드를 key로 하여 인접 노드들을 리스트에 저장하는 방식인데, 그래프에 존재하는 edge의 수를 O(n+e)의 시간복잡도로 알 수 있다. 무방향 그래프에서는 두 번씩 저장해야 서로 이어질 수 있다.
- 인접 행렬 (Adjacency Matrix)
인접 행렬은 2차원 배열에 모든 노드의 연결 관계, 즉 모든 경우의 수를 담는 방식이다. 예를 들어 5개의 노드가 있다고 가정했을 때 최대 25(n^2)개의 메모리 공간이 필요하다. 인접 행렬에서는 순회 시 모든 노드를 다 순회해야 하기 때문에.. 노드의 빈번한 추가, 삭제, 탐색에 적합하다.
👉 인접 리스트는 한 개의 노드를 기준으로 탐색을 할 때,
👉 인접 행렬은 노드와 노드 사이의 edge를 탐색 할 때 용이하다.
🏷️ 주요 속성
addNode(node): 그래프에 노드를 추가contains(node): 그래프에 해당 노드가 존재하는지 여부를 반환removeNode(node): 그래프에서 노드를 삭제hasEdge(fromNode, toNode): fromNode와 toNode 사이의 간선 존재 여부를 반환addEdge(fromNode, toNode): fromNode와 toNode 사이의 간선을 추가remove(fromNode, toNode): fromNode와 toNode 사이의 간선을 삭제
📎 Tree
트리는 노드로 구성된 계층적 자료구조이다. 최상위 노드인 루트를 만들고, 루트에 child 노드들을 추가하고, 각 child 노드에 또 child 노드들을 추가하고... 뿌리로부터 나뭇가지가 자라고, 이 나뭇가지에 또 작은 나뭇가지가 자라듯이 만들어지는 것이 바로 트리구조이다.
🏷️ 주요 개념
- Node : 트리의 구성 요소
- Root : 트리의 가장 최상위에 존재하는 노드
- Depth: 루트를 기준으로 다른 노드로 접근하기 위한 거리
- Height: 트리 전체 depth의 갯수
🏷️ 주요 속성
insertNode(value): 트리에 노드를 추가contains(value): 트리에 해당 노드가 존재하는지 여부를 반환
🏷️ Tree와 Graph의 차이점
Tree
- 계층 모델이다.
- 노드간에 반드시 한 개만의 경로를 가진다.
- loop의 개념이 없다.
- 부모-자식 관계이므로 흐름은 Top-Bottom 혹은 Bottom-Top으로 이루어진다.
- 순회는 전위/중위/후위로 할 수 있으며 이 세 가지 모두 DFS/BFS에 속한다.
- 여러 종류가 있다. (이진트리, 이진탐색트리, AVL트리, 힙트리 등)
Graph
- 네트워크 모델이다.
- 두 개 이상의 경로가 가능하며, 무방향에서 양방향으로도 가능하다.
- self-loop 및 loop가 가능하다.
- 루트 노드라는 개념과 부모-자식 개념이 없다.
- 순회는 DFS(Depth-First-Search) 혹은 BFS(Breadth-First-Search)로 이루어진다.
📎 Binary Search Tree
Binary Search Tree(이진 탐색 트리)에서는 모든 노드가 특정 순서를 따른다. 여기서 특정 순서란, 트리의 모든 왼쪽 자식 노드들은 루트(상위 노드)보다 작은 값이어야 하며, 모든 오른쪽 자식 노드들은 루트보다 큰 값을 가져야 한다.
🏷️ Binary Search Tree의 종류
- 정 이진 트리 (Full Binary tree)
트리의 모든 노드가 0개 혹은 2개의 자식 노드를 가지고 있어야 한다.
- 완전 이진 트리 (Complete Binary Tree)
트리의 모든 레벨에서 노드가 다 차 있는 트리를 말한다. 마지막 레벨의 노드를 제외한 모든 노드들이 전부 두 개씩 채워져 있어야 한다. 마지막 레벨에서는 왼쪽 노드가 채워져 있어야 한다.
- 포화 이진 트리 (Perfect Binary Tree)
완전이진트리와 정이진트리를 합친 개념이 포화이진트리이다. 즉, 트리의 모든 레벨에서 노드가 꽉 차 있어야 하면서, 마지막 레벨을 제외한 모든 노드가 두 개의 자식 노드를 가져야 한다.
🏷️ Binary Search Tree의 순회 방법
- 전위 순회 (Pre-order)
전위 순회는 루트를 시작으로 하여 루트 - 왼쪽 - 오른쪽 순서로 노드를 순회한다.
- 중위 순회 (In-order)
중위 순회는 가장 왼쪽 노드를 시작으로 왼쪽 - 루트 - 오른쪽 순서로 노드를 순회한다.
- 후위 순회 (Post-order)
후위 순회는 가장 왼쪽 노드를 시작으로 왼쪽 - 오른쪽 - 루트 순서로 노드를 순회한다.
👉 현재 루트가 어디에 위치한지에 따라 순회 방법을 알 수 있다.
🏷️ 주요 속성
insert(value): 이진 탐색 트리에 노드를 추가contains(value): 이진 탐색 트리에 해당 노드가 존재하는지 여부를 반환inorder(callback): 이진 탐색 트리를 중위순회 (left-root-right)
참고한 글
https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/
http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/
