Chapter4 Trees and Graph

How to Approach

트리와 그래프는 상당히 중요하다. 트리 중에서도 이진트리는 굉장히 많이 쓰이며 여러 알고리즘 문제나 인터뷰에서 출제가 되는 영역이다. 때문에 이진 트리의 각 순회 알고리즘과 삽입/삭제 알고리즘 정도는 언제든지 작성할 수 있어야한다. 그래프 탐색에서는 DFS(깊이 우선 탐색), BFS(넓이 우선 탐색) 알고리즘을 작성할 수 있어야 한다.

Binary Trees - "Must Know" Algorithms

중위순회, 전위순회, 후위순회에서 이름이 뜻하는것의 기준 노드는 "부모 노드"이다.

때문에 전위는 부모를 제일먼저 중위는 2번째 후위는 부모를 가장 마지막에 방문하는 탐색 방법이다.

* In-Order(중위순회) : 왼쪽 서브트리 ->부모 노드 -> 오른쪽 서브트리

* Pre-Order(전위순회) : 부모 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리

* Post-Order(후위순회) : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 부모 노드

Graph Traversal - "Must Know" Algorithms

 - Depth First Search : 깊이 우선 탐색은 형제 노드로 가기 전에 자신의 자식 노드를 먼저 방문하는 방법이다.

 - Breadth First Search :  넓이 우선 탐색은 자식 노드로 방문하기 이전에 형제 노드를 먼저 방문하는 방법이다.

Difference between Tree and Graph

그래프
1) 2개 이상의 경로가 가능하다. 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
2) self-loop 뿐 아니라 loop/circuit 모두 가능하다.
3) 루트 노드라는 개념이 없다.
4) 부모-자식 관계라는 개념이 없다.
5) 그래프의 순회는 DFS나 BFS로 이루어진다.
6) 그래프는 Cyclic 혹은 Acyclic이다.
7) 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
8) 간선의 유무는 그래프에 따라 다르다.
9) 그래프는 네트워크 모델이다.

트리
1) 트리는 그래프의 특별한 케이스이며 "최소 연결 트리"라고도 불린다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
2) loop나 circuit이 없다. 당연히 self-loop도 없다.
3) 한 개의 루트 노드만이 존재하며 모든 자식노드는 한 개의 부모노드만을 가진다.
4) 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
5) 트리의 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.
6) 트리는 DAG(Directed Acyclic Graphs)의 한 종류이다. DAG는 사이클이 없는 방향 그래프를 말한다.
7) 트리는 이진트리, 이진탐색트리, AVL 트리, 힙이 있다.
8) 간선은 항상 정점의개수-1 만큼을 가진다.
9) 트리는 계층 모델이다.

출처 [ Difference between tree and graph ]

Interview Questions

4.1 주어진 트리가 균형 트리인지 검사하는 함수를 작성하라.

public static int minDepth(TreeNode root) {
		if(root==null) {
			return 0;
		}
		return 1 + Math.min(minDepth(root.left), minDepth(root.right));
	}
	
	public static int maxDepth(TreeNode root) {
		if(root==null) {
			return 0;
		}
		return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
	}
	
	public static boolean isBalanced(TreeNode root) {
		return maxDepth(root) - minDepth(root) <= 1; 
	}

아이디어는 매우 간단하다. 균형 트리에서는 가장 깊이가 큰 노드와 가장 깊이가 작은 노드간의 레벨 차이가 1이하 여야한다. 때문에 가장 깊이가 큰 노드의 레벨과 깊이가 가장 낮은 노드의 레벨의 차이를 이용하여 균형 트리인지의 여부를 쉽게 확인 할 수 있다.

4.2 유향 그래프가 주어졌을때 두 노드 사이에 경로가 있는지 없는지를 알아내는 알고리즘을 설계하라.

4.3 오름차순으로 정렬된 1차원 배열이 주어졌을때,  이진 탐색 트리를 생성하는 알고리즘을 작성하시오.

4.4 이진 탐색 트리가 주어졌을 때, 같은 레벨의 노드들을 LinkedList로 연결하여 구조화 하시오.

출처

[Cracking the coding interview]