오늘은 마지막 데이터 구조 시간이었다.
각 자료구조를 공부하고 구현하는 시간을 가졌다.
Graph
그래프는 Node(vertex라고도 한다), 그리고 노드를 연결하는 간선(edge)로 구성되어 있다.
그래프를 구현방식 중 인접 행렬과 인접 리스트 방식이 있는데,
-
인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방법이다.
this.nodes[i][j]: 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0
차지하는 메모리 양은 이중 배열이기 때문에 V*V -
인접 리스트는 그래프의 연결 관계를 백터로 나타내는 방법이다.
this.nodes[i]: 노드 i에 연결된 노드들을 원소로 갖는 vector
구현한 그래프는 무방향 그래프에 인접 리스트로 구현하였다.
this.nodes는 객체의 형식이고 그 안에 key와 value의 형식으로 node와 edge로 연결되어 있는 다른 노드를 추가하는 방식으로 구현하였다.
Tree
트리는 노드로 구성된 계층적 자료구조이다.
루트를 기준으로, 다른 노드들로의 접근하기 위한 거리를 depth라고 한다. 노드와 노드를 잇는 선은 graph와 마찬가지로 edge라고 한다. 순환구조를 가질 수 있다.
heigth는 말단 노드 중 루트로부터 가장 멀리 떨어진 노드의 depth라고 알았는데 office hour 시간에 들은 내용과 달라서... 혼동이....
트리의 종류로는 정 이진 트리, 완전 이진 트리, 포화 이진 트리가 있는데 내가 이해한 바로는,
-
정 이진 트리는 자식이 0또는 2개인 트리 구조
-
완전 이진 트리는 왼쪽부터 노드가 차곡차곡 쌓여서 마지막 레벨을 제외하고 모든 자식노드가 채워져 있는 트리 구조
-
포화 이진 트리는 마지막 레벨을 제외하고 모든 노드가 자식을 2개인 트리 구조이다.
구현은 루트(최산위 노드)를 만들고, 루트 노드에 child를 추가하여 그 안에 또 child를 추가하는 방식으로 구현하였다.
Binary Search Tree
이진 탐색 트리는 최대 2개의 자식만 갖는 트리이다.
노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재한다.
깊이 우선 탐색을 이용하여 구현하였다.
이진 탐색트리에 노드를 추가하는데 left, right 을 지정할 수 있게 구현하고 들어오는 노드가 부모보다 작으면 left로 크거나 같으면 right로 지정한다.
트리의 순회는 중위 순회를 이용하였는데 좌-> 부모 -> 우 와 같은 방식으로 구현하였다.
오늘 구현을 다 마쳐서 내일 오전에는 또 한 번 구현해보고 오후에 포스팅을 할 생각이다.
Referencd
