이번 스프린트 자료구조의 마지막 파트인 graph, tree, BST 를 배웠다. 생긴게 마인드 맵 같기도 했고 포도 같기도 하였다. 여튼 내 마음처럼 복잡했다. 오늘도 어김없이 이 세가지를 코드로 구현해 보는 시간을 가졌다. 각 자료구의 특징과 여러가지 연산법 참조법 등등을 머릿속으로 생각하는 것도 어려운데 이걸 자바스크립트로 구현 하려고 하니 머리가 아팠다. 그러나 이번 페어 팀원분이 상당이 훌륭하셔서 난 지켜보기만 한것 같은데 뚝딱 구현을 성공했다. 먼저 세 자료구조의 간단한 특징을 설명 해보겠다.
1.graph
그래프의 두가지 형태 방향 그래프와 무방향 그래프 그리고 두가지의 그래프 구현 방식 인접 행렬 인접 리스트에 대해서 설명하겠다.
먼저 간단한 용어에대해서 설명 하겠다.
- 정점: 위치(노드라고도 한다.)
- 간선: 정점과 정점을 연결하는 선.
- 차수: 정점에 연결된 간선의 수.
(1) 방향 그래프와 인접 행렬
방향그래프로 정점의 간선이 방향성을 가지고 있는 걸 볼 수있다. 표시된 방향으로만 갈 수 있으며, 옆의 표는 인접 행렬의 그래프 구현 방식인데 간선의 방향에 따라 진입 진출이 결정된다. 방향그래프의 특징은 각 정점이 진입차수와 진출차수를 가지는 것을 알수있다.
(2) 무방향 그래프와 인접 리스트
무방향 그래프는 말 그대로 간선의 방향이 없는 것이다. 간선으로 연결된 두 정점은 서로의 방향으로 갈 수 있다. 옆의 표는 인접 리스트로 그래프를 구현 하였는데 이를 방향 그래프에도 적용해 볼 수있다. 반대로 무방향 그래프를 인접 행렬에도 적용해 볼 수 있으며 자기 자신을 기준으로 대칭을 이룬다.
2. Tree
트리 구조는 하나의 루트가 반드시 존재하며 루트는 0개 이상의 자식 노드를 가질수 있다. 자식 또한 마찬가지로 노드를 0개 이상 가질수 있으며 위 사진 처럼 뻗어 나가는 구조이다.
- Root: 최상위에 있는 노드.
- Parent: 부모 노드로 B는 C,E의 부모 노드이며 C는 I,H의 부모 노드이다.
- Child: 자식 노드로 C와 E는 B의 자식 노드이며 B는 D(Root)의 자식 노드이다.
- Siblings: 형제 노드로 같은 부모를 가진 노드이다. F, G, K는 D를 부모로 두고 있는 형재 노드.
- Leaf: 자식 노드가 없는 최하위의 노드이다.
- Depth: 루트에서 현재 노드 사이의 간선 개수이다. B의 Depth는 1, C는 2.
- Height: 트리중 가장 긴 경로의 간선 개수. 위 트리의 Heigth는 3.
- Level: 루트 노드부터의 깊이. 위 트리의 Level은 4 (Height + 1).
3. BST(Binary Search Tree)
이진탐색트리는 자식 노드를 최대 2개 까지만 가질수 있는 자료 구조로 일반 트리와는 달리 규칙성을 가질 수 있다. 여러 가지의 형태가 있으며 탐색하는 방법에도 여러 종류가 있다.
(1) 이진트리 탐색의 종류.
- 전위 순회: 뿌리를 먼저 탐색 하는 방법으로 왼쪽의 자식으로 먼저 내려간다.(15-7-5-3-8-13-2-16-1-18)
- 중위 순회: 왼쪽의 최하위 Leaf를 먼저 탐색 후 부모 노드를 방문.(3-5-8-7-2-13-15-1-16-18)
- 후위 순회: 하위의 노드를 모두 탐생 후 부모 노드를 방문. (3-8-5-2-13-7-1-18-16-15)
(2) 이진트리의 여러 형태.
- 정 이진트리(Full binary tree): 모든 노드가 0개 또는 2개의 자식노드를 가지는 트리.
- 완전 이진트리(Complete binary tree): 왼쪽 자식 노드부터 채워지는 트리.
- 포화 이진트리(Perfect binary tree): 트리에 노드가 꽉 차있는 형태.
여러 가지의 자료구조를 배우면서 느꼈던 것은 평소에 내가 무의식 중에 써오던 것들에 이러한 자료 형태들이 많이 적용 되어 있다는 것을 알게 되었다. 조금은 얕게 공부 했지만 알게된 것들로인해 조금 더 흥미로운 시선으로 세상을 바라볼 수 있다고 생각했다. 이러한 자료구조를 구현 해보면서 자바스크립트에 조금더 익숙 해질 수 있었다는 것도 굉장히 큰 성과이다. 지금 잡은 이 두 가지를 먼 훗날에도 잊지 않게 꾸준히 노력 해야겠다..
