180708.md
August 16, 2018 · View on GitHub
트리와 이진 탐색
관련 문제들
- 트리
- 이진 탐색
[issue]에 대한 정리
[#issue1] 트리의 개념과 적용 사례
* 트리란
* 비선형 자료구조로 계층적 관계를 표현한다.
* 디렉터리 구조
* 조직도
* 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
* 트리 관련 용어
* 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
* 단말 노드(leaf node): 자식이 없는 노드
* 내부(internal) 노드: 단말 노드가 아닌 노드
* 긴선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
* 형제(sibling): 같은 부모를 가지는 노드
* 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
* 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
* 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
* 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
* 트리의 차수(degree of tree): 트리의 최대 차수
* 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
* 트리 특징
* 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
* 루트에서 어떤 노드로 가는 경로는 유일하다.
* 임의의 두 노드 간의 경로도 유일하다.
* 트리의 표현 방법
* 그래프의 한 종류이므로, 그래프 표현 방법을 이용
* 인접 배열 이용
1. 1차원 배열에 자신의 부모 노드만 저장하는 방법
* 트리는 부모 노드를 0개 또는 1개를 가지기 때문
* 부모 노드를 0개: 루트 노드
2. 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법
* 이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문
* Ex) A[i][0]: 왼쪽 자식 노드, A[i][1]: 오른쪽 자식 노드
* 인접 리스트 이용
1. 가중치가 없는 트리의 경우
* ArrayList< ArrayList<Integer> > list = new ArrayList<>();
2. 가중치가 있는 트리의 경우
1) class Node { int num, dist; // 노드 번호, 거리 } 정의
2) ArrayList<Node>[] list = new ArrayList[정점의 수 + 1];
[#issue1-1] 트리의 지름 개념과 구하는 방법
* 트리의 지름: 모든 경로 중에서 가장 긴 것의 길이
* 탐색 2번으로 구할 수 있다.
* 1. root에서 모든 정점까지의 거리를 구한다.
이때, 가장 먼 거리였던 정점을 A라고 한다.
* 2. A를 root라고 하고 다시 모든 정점까지의 거리를 구한다.
이때, 가장 먼거지인 정점과의 거리가 ‘트리의 지름’이다.
[#issue1-2] 트리와 그래프의 차이점
* 트리
* 그래프의 특별한 케이스이며 '최소 연결 트리'라고도 불린다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
* loop나 circuit이 없다. 당연히 self-loop도 없다.
* 한 개의 루트 노드만이 존재하며 모든 자식노드는 한 개의 부모 노드만을 가진다.
* 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
* 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.
* 트리는 DAG(Directed Acyclic Graphs)의 한 종류이다. DAG는 사이클이 없는 방향 그래프를 말한다.
* 트리는 이진트리, 이진탐색트리, AVL 트리, 힙이 있다.
* 간선은 항상 정점의 개수-1 만큼을 가진다.
* 트리는 계층 모델이다.
* 그래프
* 2개 이상의 경로가 가능하다. 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
* self-loop 뿐 아니라 loop/circuit 모두 가능하다.
* 루트 노드라는 개념이 없다.
* 부모-자식 관계라는 개념이 없다.
* 순회는 DFS나 BFS로 이루어진다.
* 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
* 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
* 간선의 유무는 그래프에 따라 다르다.
* 그래프는 네트워크 모델이다.
[#issue1-3] 이진 트리의 순회(전위, 중위, 후위 순회)
- 중위 순회(in-order traversal): 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지
void inOrderTraversal(TreeNode node) {
if(node != null) {
inOrderTraversal(node.left);
visit(node);
inOrderTraversal(node.right);
}
}
- 전위 순회(pre-order traversal): 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지
void preOrderTraversal(TreeNode node) {
if(node != null) {
visit(node);
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
- 후위 순회(post-order traversal): 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드
void postOrderTraversal(TreeNode node) {
if(node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
visit(node);
}
}
[#issue2] 이진 탐색의 개념
* 이진 탐색이란
* 정렬된 자료를 반으로 나누어 탐색하는 방법이다.
* 데이터가 오름차순 으로 정렬되어 있어야 한다.
* 시간복잡도: O(log N)
* 이진 탐색 알고리즘 과정
크기가 n인 리스트 data에서 target 이라는 특정 요소를 찾아낸다고 가정했을 때,
1. low = 0, high = n-1 로 초기화한다.
2. mid = (low + high) / 2 로 초기화한다.
3-1. data[mid] 와 target이 같으면 탐색을 종료한다.
3-2. data[mid] > targer 이면 high = mid-1 로 업데이트 한 후, 2번으로 돌아간다.
3-3. data[mid] < targer 이면 low = mid+1 로 업데이트 한 후, 2번으로 돌아간다.
public int binarySearch(int[] data, int target) {
int low = 0;
int high = data.length - 1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
/* 1. 구체적인 수를 찾는 경우 */
if (target == data[mid])
return mid;
if (target < data[mid])
high = mid - 1;
else
low = mid + 1;
/* 2. 조건을 만족하는 값 중 최댓값을 구하는 경우 */
if (target <= data[mid]) // 부등호 처리
high = mid - 1;
else
low = mid + 1;
}
return -1;
}