트리
1. 비선형구조와 트리
- 선형 구조는 자료가 순서를 가지고 연속되어있음
비선형 구조는 선형 구조에 해당하지 않는 자료구조(ex 트리, 그래프) - 그런데 사실 그래프 > 트리로 그래프가 포괄하는 개념임
- 경로란 어떤 정점에서 다른 정점으로 이동하기 위해 거치는 모든 정점을 경로라고 한다.
- 유향 그래프 : 간선에 방향성을 띄고 있는 그래프
- 사이클 : 처음 시작한 정점으로 다시 되돌아 노는 경로를 사이클이라 한다.
- 가장 위에 있는 (어떠한 정점도 가르키지 않는 정점)정점은 루트노드라고 함.
- 그리고 루트 노드로부터의 거리를 "깊이"라고 함.
- 그 반대의 제일 끝의 자식 노드를 리프노드라고 함.
- 이진트리 : 자식노드를 최대 2개가지만 갖는 트리
- 포화 이진트리 : 모든 리프노드의 깊이가 같은 트리
- 포화 이진트리의 높이를 h라고 할 때, 정점의 개수는 항상 (2의 h승 -1)이다.
- 완전 이진트리 : 리프노드를 제외하고 모든 정점이 완전히 채워져 있으며, 리프노드들은 가능한 한 왼쪽에 있는 트리를 완전 이진 트리라고 한다.
즉, 포화 이진트리 < 완전 이진트리가 더 큰 개념 - 완전 이진트리의 높이를 h라고 할 때, 정점의 개수는 (2의 h-1승 ~ 2의 h승 -1)개의 개수이다.
- 정 이진트리 : 리프 노드를 제외한 모든 노드들의 두 개의 자식 노드를 갖고있는 이진 트리이다. 즉, 모든 정점은 0개 또는 2개의 자식 노드를 갖는다. 즉, 자식이 1개인 경우는 없다.
2. 트리의 표현방법
- 완전 이진 트리의 경우 배열을 이용하여 간단하게 구현이 가능하다.
- 또한 트리는 그래프의 일종이므로 그래프를 표현할 때 사용하는 인접행렬, 인접 리스트, 간선 리스트를 사용할 수도 있다.
3. 트리 순회하기
- 순회 : 트리의 모든 노드를 방문한는 순서 배열, 연결리스트등 선형 구조는 각 자료가 순서를 갖지만 비선형 구조에 해당하는 트리는 정해진 순서가 없다.
- 순회 순서는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)
- DFS는 재귀호출을 사용하는 알고리즘으로, DFS를 이해하기 위해서는 트리의 재귀적 특성을 알아야 한다. 재귀 호출은 스택의 특성을 이용하므로 Stack을 이용한다고 불 수 있다.
- DFS는 정점을 언제 방문하는지 순서가 달라지며 재귀호출을 사용한다는 개념 자체는 동일하다.
- BFS는 현재 정점과 이웃한 정점일 수록 먼저 방문해야하므로 선입선출의 자료구조인 Queue를 이용해야한다.
4. 트리의 활용
- 컴퓨터에서 트리를 활용하는 예시는 대표적으로 이진탐색 트리가 있다.
- 임의의 자료들을 담고있는 자료구조 A가 있다고 가정할 때, A는 항상 정렬된 상태를 유지해야 한다고 생각해보자.
만약 A가 배열이라면 자료의 추가, 삭제, 탐색은 다음과 같다. 1장에서 배운 배열의 연산을 다시 복습해보자. - 배열구조에서 탐색의 시간복잡도가 logn을 갖는 이유
- 이진탐색 : 정렬된 배열의 중간값과 찾는 값의 크기를 비교하고, 중간값보다 작은 경우에는 중간값을 기준으로 좌측, 중간값보다 큰 경우에는 중간값을 기준으로 우측을 대상으로 다시 탐색한다.
- 이진 탐색 트리는 항상 정렬된 상태를 유지하는 자료구조이며, 어떤 정점의 왼쪽 서브트리는 그 정점보다 같거나 작은 정점들로만, 오르쪽 서브트리는 그 정점의 값보다 큰 정점들로만 이루어져있다.
- 정렬된 상태를 유지해야 하는 자료구조가 A가 트리로 구현되어있다면 더 효율적으로 연산이 가능하다.
- 단 이때 편향이진 트리가 되어버리면 배열과 같은 구조가 되므로 장점을 살릴 수 없다. 그래서 나온 것이 자가 균형 이진 탐색 트리중 하나인 "레드블랙 트리"이다.
智(지)! 德(덕)! 體(체)!