3/15 일일정리 트리/그래프

Tree 자료구조

출처 : 코드스테이츠

Tree처럼 생긴 자료구조라고 해서 tree라는 이름이 붙여졌다고 한다.( 나무보다는 나무뿌리처럼 생긴거 같다.)

 

트리의 구성요소

트리의 각각의 데이터들을 노드(Node)라고 부르며 꼭대기에 있는 노드를 루트 노드(Root Node)라고 한다. 

루트 노드에서부터 밑으로 뻗어 나가는데 상하계층으로 연결되어 있는 노드들을 각각 부모 노드(Parent Node), 자식노드(Child Node)라고 부른다.

루트 노드로부터 거리가 같은 노드들을 형제 노드(Sibling Node)라고 한다.

자식이 없는 노드는 리프 노드(Leaf Node)라고 부른다.

각각의 노드들을 연결하는 선을 간선(Edge)이라고 부른다.

 

트리에서는 깊이(depth)는 루트로부터의 거리를 의미한다. 루트의 깊이는 0이다.

위의 그림에서 B,C는 깊이가 1이고, D,E,F,G는 깊이가 2이다. 이렇게 같은 깊이의 노드들이 존재하는데 같은 깊이의 노드들을 같은 레벨(level)에 있다고 표현하며, 같은레벨에 있는 노드들은 전부 형제 노드이다.

 

트리의 특징

⓵ 비선형 자료구조이다.

⓶ 계층형 자료구조이고, 하나의 노드는 하나의 부모 노드를 가지고있다.

⓷ 순환하지 않고 연결된 무방향 그래프 구조이다.

⓸ 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 구조이다.

 

 

이진 트리(Binary Tree)

이진 트리는 부모 노드 밑에 자식 노드를 최대 2개 까지로 제한하는 트리구조이다. 

이러한 이진 트리는 이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용된다.

 

이진 탐색 트리

출처 : 나무위키

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.

이진 탐색 트리에서는 노드가 현재 값보다 큰지 작은지만 판단하면 되기 때문에 속도가 빠르다. 탐색/삽입/삭제의 시간복잡도 O(log n)을 가지게 된다. (최악의 경우 O(n), 편향트리일 때)

 

트리 순회 방법

트리의 모든 노드들을 한번씩 방문하는 것을 트리 순회라고 한다. 트리 순회 방법에는 3가지가 있다.

 

⓵ 전위 순회

출처 : https://www.crocus.co.kr/348

가장 먼저 루트를 방문하고, 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.

부모 노드가 제일 먼저 방문 되는 순회 방식이다. 전위 순회는 주로 트리를 복사할 때 사용한다.

 

⓶ 중위 순회

출처 : https://www.crocus.co.kr/348

제일 왼쪽 끝에 있는 노드 시작해서 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다. 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식이다. 중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.

 

⓷ 후위 순회

출처 : https://www.crocus.co.kr/348

제일 왼쪽 끝에 있는 노드부터 순회하고 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다. 후위 순회는 트리를 삭제할 때 사용한다. 

 

 

그래프(Graph)

자료구조에서 그래프는 여러 개의 점이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가지고 있다.

출처 : https://velog.io/@hanganda23/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84

그래프는 정점(Vertex)과 정점들을 연결하는 간선(Edge)으로 구성되어 있다. 

 

그래프 표현 방식

⓵ 인접 행렬(Adjacent Matrix)

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다. 이어져 있다면 1, 없다면 0으로 표시하는데, 가중치 그래프라면 1대신 다른값을 사용한다.

출처 : https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84-Graph

인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기 좋다.
가장 빠른 경로를 찾고자 할 때 주로 사용된다.
최단 경로를 구하는 과정(BFS)에서는 그래프 탐색이 빈번하게 발생하는데, 이때 인접행렬이 인접리스트에 비해 조회 성능이 더 좋다. 

 

 

⓶ 인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

출처 : https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84-Graph

인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지하므로 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.

 

 

Reference

- 코드스테이츠

- https://yoongrammer.tistory.com/68

- 나무위키

- https://www.crocus.co.kr/348

- https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84-Graph