[자료구조] 트리와 그래프

트리

트리란 단방향 그래프의 한 구조로, 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 붙은 이름이다.

데이터가 바로 아래의 하나 이상의 데이터에 하나의 경로와 방향으로 연결된 구조이다. 즉, 나의 데이터 아래에 여러개의 데이터가 존재할 수 있는 비선형 구조이다.

• 루트라는 꼭지점을 시작으로 여러 데이터를 간선(edge)로 연결
• 각 데이터는 노드라고 부름
• 자식이 없는 노드는 리프 노드라고 부름

특징

• 깊이

  • 말 그대로 루트에서 하위계층의 특정 노드까지의 깊이
  • 루트노드의 깊이는 당연히 0부터 시작하고, 3과 2의 깊이는 1, 그 자식들의 깊이는 2 이다.

• 레벨

  • 같은 깊이를 가지고 있는 노드를 레벨로 표현할 수 있다. 같은 레벨에 있는 노드들을 형제 노드라고 한다.

• 높이

  • 리프~노드까지 높이를 표현할 수 있다. 이때의 기준은 리프 노드로 0의 높이를 가진다. 깊이와 반대되는 개념으로 이해하면 쉽다.

• 서브트리

  • 전체트리의 내부에 트리구조를 갖춘 작은 트리 (위에서는 3,4,5와 2,6,7)

이진 트리

이진트리는 자식 노드가 최대 두개인 노드들로 구성된 트리이다.

종류가 다양하지만, 여기서는 정 이진 트리 (Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)만 설명한다.

• 정 이진 트리: 각 노드가 0개 혹은 2개의 자식 노드를 가짐

• 완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 찼고, 마지막 레벨의 노드는 적어도 왼쪽이 차 있는 트리

• 포화 이진 트리: 정 이진 트리와 완전 이진 트리의 조건을 모두 만족한 경우.

이진 탐색 트리

이진 탐색 트리란 이진 탐색과 연결 리스트를 결함한 이진트리를 말한다.

이진 탐색 트리의 특징은 다음과 같다.

• 각 노드에 중복되지 않는 키가 있다.
• 루트노드의 왼쪽 서브트리는 루트의 키보다 작은 키를 가진 노드들로 구성된다.
• 루트노드의 오른쪽 서브트리는 루트의 키보다 큰 키를 가진 노드들로 구성된다.

= 루트의 왼쪽은 루트보다 키 값이 작고 오른쪽은 루트보다 크다.

특징

일단 기존 이진 트리보다 탐색이 빠르다.

탐색 과정은 다음과 같다.

1. 루트의 키와 찾고싶은 값을 비교.(이때 일치하면 탐색 종료)
2. 찾고싶은 값이 루트보다 작으면 왼쪽으로 탐색 진행
3. 찾고싶은 값이 루트보다 크면 오른쪽으로 탐색 진행

이 과정을 답을 찾을 때까지 반복해서 진행.

트리 순회(Tree Traversal)

특정 목적을 달성하기 위해 모든 노드를 한번씩 방문하는 것

• 전위 순회
• 중위 순회
• 후위 순회

전위 순회

1. 가장 먼저 루트를 방문
2. 루트의 왼쪽 노드를 순차적으로 방문한 후, 왼쪽이 끝나면 오른쪽을 탐색

부모노드가 먼저 생성되어야 하는 트리를 복사할 때 사용

중위 순회

1. 제일 왼쪽 끝의 노드부터 방문해 루트기준 왼쪽의 노드들을 모두 순회
2. 왼쪽의 순회가 끝나면 루트 노드를 방문한 뒤, 오른쪽의 노드를 순회함

부모 노드가 서브트리 방문 중간에 방문됨. 이진 탐색 트리의 오름차순으로 값을 가져올때 사용한다.

후위 순회

1. 제일 왼쪽 끝의 노드부터 순회 시작
2. 끝나고 나면 오른쪽으로 이동해 순회하고 제일 마지막에 루트를 방문

트리를 삭제할 때 사용되는 방식

---

그래프

여러개의 점들이 서로 복잡하게 연결된 관계를 표현한 자료구조

구조

• 직접적 관계가 있으면 두 점을 이어주는 선이 있음

• 간접적 관계면 몇개의 점과 선에 걸쳐 이어짐

• 하나의 점을 정점(vertex)라고 부르고 선은 간선(edge)라고 부름

표현 방식

인접 행렬

두 정점을 바로 이어주는 간선이 있으면 이는 인접하다고 표현한다.

• 서로다른 정점들이 인접한지 표시한 행렬로 2차원 배열의 형태로 나타낸다.
• 이어졌다면 true(1), 아니라면(false)라고 표시한다.(가중치 그래프에서는 1 대신 관계에서 의미있는 값을 저장한다. 예를 들어 거리)
  
  위의 경우
• A의 진출차수는 2개이다. (B, D)
  • [0][1] === 1
  • [0][3] === 1
• B의 진출차수는 1개이다. (D)
  • [1][3] === 1
• C의 진출차수는 1개이다. (B)
  • [2][1] === 1
• D의 진출차수는 0개이다.
• E의 진출차수는 1개이다. (D)
  • [4][3] === 1

인접 행렬은 두 정점 사이에 관계의 유무를 확인하기에 좋다. 이를 통해 가장 빠른 경로를 파악한다.

인접 리스트

각 정점이 어떤 정점과 인접하는지 리스트의 형태로 표현한 것.
정점마다 하나씩 리스트를 가지고 있고, 리스트에는 인접한 정점이 담겨져 있다.

A - B - D - Null
B - D - Null
C - B - Null
D - Null
E - D - Null

이때 간선이 여러개 있어도 이를 표현하는 순서는 중요하지 않다. 때문에 우선순위를 고려해 구현할 수 있다.
주로 메모리를 효율적으로 사용하고 싶을 때 인접리스트를 사용한다.

알아둬야 할 용어들

• 가중치 그래프: 연결의 강도(추가적인 정보. 예를들면 서울-수원까지의 거리 등)가 얼마나 되는지 적혀있는 그래프

• 무방향 그래프: 정점끼리 서로간 순회가 가능한 그래프(<--> 단방향 그래프)

• 자기 루프: 한 정점의 간선이 바로 자기 자신에게 진입하는 경우를 말함.