[Java 풀스택 과정 강의] 3월 10일

※ TIL와는 별개로 적는 개인 개발 일지라서 말은 좀 편하게하는 페이지입니다.
일지이기 때문에 일기의 성격이 더 강합니다.

 

 

몸이 안 좋아서 강의 일지 정리가 늦어지고 있다. 지금도 솔직히 상태가 좋진 않지만 밀리면 손해 보는 건 나니까…ㅠㅠ 머리도 아프고 계속 그러는데 왜 이러는걸까…

강의 일지 정리가 코테런보다 빠르고 코테런이 문제 푸는것보다 느리는 통에 고생중…

 

 

Tree 개념

Tree는 계층적 비선형 구조로 부모와 자식을 가지며, 순회하지 않는다. 이 부분은 HTML에서 DOM TREE에 대해서 알고 있으면 이해가 편하다. 부모와 자식을 가지고 있기 때문에 경로가 하나 뿐이며(돌아갈 수가 없으므로), N개의 노드를 가진 트리들은 N - 1개의 간선을 가지게 된다.

 

Tree의 사용처는 DOM Tree의 이점과 비슷한데, 바로 찾아가기 쉽다는 것. 부모와 자식을 명백히 함으로써 구조적인 파악이 쉬우며, 탐색 또한 쉬워진다. 그리고 부모와 자식이라는 개념이 존재함으로써 부모에 대한 조작을 하면 자식 또한 제어가 가능하기도 한다.

 

Tree에는 다음과 같은 용어를 사용한다.

 

• 노드Node
  트리를 구성하는 기본 요소. 각 노드들은 데이터와 다른 노드를 가리키는 참조- 가지(Branch)를 가진다.
• 루트Root
  트리의 최상위에 있는 시작 노드. HTML의 경우 HTML이 최상위 노드가 된다.
• 부모/자식
  간선으로 연결된 두 노드를 이야기한다. 상위를 부모, 하위를 자식.
• 형제Siblings
  같은 노드를 공유하는 자식 노드들을 의미한다.
• 잎Leaf
  자식 노드가 없는 노드. 트리 가장 끝에 위치한다.
  차수Degree가 0이며, 단말 노드(Terminal Node)라고도 불린다.
• 간선Edge
  노드와 노드를 연결하며, 자식과 부모를 연결한다.
  N개의 노드를 가진 트리는 정확히 N-1개의 간선을 가진다.
• 차수Degree
  특정 노드가 가지고 있는 자식 노드의 개수를 이야기한다. 아래에서 다룬 이진트리는 모든 노드는 차수가 2를 넘지 않는다.
• 깊이/레벨
  루트에서 해당 노드까지의 경로 길이를 의미. 루트 본인의 깊이는 당연히 0. 노드들의 집합은 레벨이라고 한다.
• 높이
  해당 노드에서 가장 먼 잎(Leaf) 노드까지의 경로 길이. 트리의 높이는 루트 노드의 높이와 같다.

 

Binary Tree(이진 트리)

위에서 말했듯 차수는 2를 넘지 않는 트리를 의미한다. 자식은 최대 둘이며, 왼쪽 자식과 오른쪽 자식으로 나뉜다. 없거나 하나의 자식만 가지는 경우도 있다. 균형 트리일 경우 모든 자식이 있는 노드들은 왼쪽과 오른쪽 자식을 가져야 한다.

 

이진트리의 최대 노드 수는 높이가 h일 때, 2^(h+1) - 1개가 된다. n개 노드의 최소 높이는 log₂ n이 된다.

이러한 이진 트리에도 종류가 존재한다.

 

포화 이진트리Perfect Binary Tree

모든 레벨이 노드로 가득찬 이진트리로, 마지막 레벨까지 빈 자리가 없다.

내부 노드는 모두 2개의 자식을 가지며, 모든 잎은 같은 깊이에 존재한다. 총 노드 개수는 N = 2ʰ⁺¹ - 1개이다.

 

정 이진트리Full Binary Tree

모든 노드는 자식이 없거나, 정확히 2개만 가질 수 있다. 잎 노드의 개수(L)는 내부 노드의 개수(I)보다 항상 1개 더 많다.

 

완전 이진트리Complete Binary Tree

마지막 레벨의 노드들은 왼쪽부터 차례대로 빈틈없이 채워진다.  마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. 배열 인덱스(1, 2i, 2i+1)로 효율적인 매핑이 가능하다. 만약 불완전 이진트리라면 불가능.

 

편향 이진트리Skewed Binary Tree

모든 노드가 오직 하나의 자식만 가지며, 한쪽 방향으로만 치우쳐 있다. 연결 리스트와 비슷한 형태. 트리의 높이(h)가 노드의 수(n)와 동일하다.

 

균형 이진탐색트리

왼쪽 자식은 부모보다 작고, 오른쪽은 부모보다 큰 이진탐색 트리이다. 중위 순회에 특화되어 있다.

 

 

Tree 표현

Tree의 표현은 배열 인덱스 표현과 연결 리스트 표현으로 나눌 수 있다. 배열 인덱스의 경우 위에서 보여준 완전 이진트리나 포화 이진트리에서 사용하고, 연결 리스트는 트리 형태가 불규칙할 때 사용한다(불완전 이진트리 등).

 

배열 인덱스에 관해서는 아래와 같은 공식을 사용할 수 있다.

Parent(i) = i / 2
Left(i) = 2 * i
Right(i) = 2 * i + 1

 

반면 연결 리스트는 특별한 공식은 없기 때문에 구조 파악만 해두면 된다.(나의 경우는 그냥 이것도 배열을 사용하는 편…)

 

Tree 순회

Tree 순회는 DFS와 BFS 방법이 있다. DFS에서는 전위/중위/후위 순회가 존재하는데, 이번 수업에서 제일 중요한 부분이라 할 수 있다.

 

전위 순회 (Preorder Traversal)

V L R 순서로 방문한다. 여기서 V는 현재 노드를 가장 먼저 처리 및 출력한다. 그리고 L은 왼쪽 서브트리로의 이동, R은 오른쪽 서브 트리로의 이동이다.

 

ABDECFG 순서로 나타난다.

 

한번 방문한 노드는 다시 방문하지 않기 때문에 이렇게 뜬다. 아래는 구현에 대한 코드.

 

public void preorder(Object[] arr, int n, int i) {	
    // Base Case: 인덱스 범위를 벗어나거나 값이 null인 경우
    if (i > n || arr[i] == null) {
    	return;
    }
    
	// 1. Visit Root (V)
    System.out.print(arr[i] + " ");
    
	// 2. Visit Left Child (L) -> 2 * i
    preorder(arr, n, 2 * i);
    
	// 3. Visit Right Child (R) -> 2 * i + 1
    preorder(arr, n, 2 * i + 1);
}

 

보다시피 위에서 사용한 왼쪽은 2 * i, 오른쪽은 2 * i + 1 공식을 사용하고 있다. 전위는 VLR이다, 이렇게 외워두면 편하다.

 

 

중위 순회 (Inorder Traversal)

LVR 순서로 방문한다. 현재 노드 처리 전에 왼쪽부터 방문하는 느낌이다.

 

D B E A F G

 

노란색이 출력으로 보이는 경로, 보라색이 실제 경로이다. 왼쪽을 먼저 본 다음에 출력한다는 지점에 유의하면 된다.

 

public void inorder(Object[] arr, int n, int i) {	
    // Base Case: 인덱스 범위를 벗어나거나 값이 null인 경우
    if (i > n || arr[i] == null) {
    	return;
    }
    
	// 1. Visit Left Child (L) -> 2 * i
    preorder(arr, n, 2 * i);

	// 2. Visit Root (V)
    System.out.print(arr[i] + " ");
    
	// 3. Visit Right Child (R) -> 2 * i + 1
    preorder(arr, n, 2 * i + 1);
}

 

코드도 보다시피 전위에서 L V R로 수정된 것에 가깝다.

 

 

후위 순회 (Postorder Traversal)

자식을 먼저 처리하고 부모를 처리하는 형태로, L R V가 된다.

 

 

 

public void postorder(Object[] arr, int n, int i) {	
    // Base Case: 인덱스 범위를 벗어나거나 값이 null인 경우
    if (i > n || arr[i] == null) {
    	return;
    }
    
	// 1. Visit Left Child (L) -> 2 * i
    preorder(arr, n, 2 * i);
    
	// 2. Visit Right Child (R) -> 2 * i + 1
    preorder(arr, n, 2 * i + 1);
    

	// 3. Visit Root (V)
    System.out.print(arr[i] + " ");    
}

 

위와 별 차이 없이, LRV임에 유의하면 된다.

 

기타 사항으로 주의점은 빈 트리와 인덱스 범위를 벗어나는 경우를 먼저 처리하고 순회를 할 것. 그 다음으로 단일 노드나 Leaf 처리가 제대로 되어있는지 확인할 것이 있다. 삽입 정렬에 대해서도 배웠는데, 이 부분은 후에 실전 문제에서 다뤄볼까 싶다.