Algorithm 7일차

알고리즘에서 트리를 활용할 수 있다.

트리는 상위 원소에서 하위 원소로 내려가며 확장되는 계층형 자료구조이다.

트리에서 알아야 할 정의는 아래와 같다.

1. 트리의 원소는 노드라고 하고, 노드와 노드를 연결하는 선을 간선이라 한다.
2. 트리의 하위 트리를 부 트리라고 한다.
   
3. 최상위 노드는 루트노드, 최하위 노드는 단말노드라고 한다.
   루트노드는 단 한 개이며, 단말노드는 다수일 수 있다.
4. 같은 부모 노드의 나와 다른 자식 노드를 형제 노드라고 한다.
5. 간선을 따라 루트 노드까지 만나는 모든 노드를 조상 노드라고 한다.
6. 서브 트리에 있는 하위 레벨의 모든 노드를 자손 노드라고 한다.
7. 노드에 연결된 자식 노드의 수를 노드의 차수, 노드의 차수 중 가장 큰 값을
   트리의 차수라고 한다.
8. 루트에서 노드에 이르는 간선의 수를 노드의 높이, 노드의 높이 중 가장 큰 값을
   트리의 높이라고 한다.

알고리즘에서 이진 트리를 활용할 수 있다.

이진 트리란 모든 노드의 최대 차수가 2인 트리이다.
따라서 높이가 h인 이진 트리의 최소 노드 개수는 (h+1), 최대 노드 개수는 (2^(h+1) - 1) 이다.

이진 트리는 아래와 같이 나뉜다.

1. 포화 이진 트리 : 최대 노드 개수를 가진 이진 트리이다.
   
2. 완전 이진 트리 : 포화 이진 트리 1부터 n번까지 빈 자리가 없는 이진 트리이다.
   
3. 편향 이진 트리 : 최소 노드 개수를 가졌으며, 한 방향으로 치우친 이진 트리이다.
   

이진 트리는 아래와 같이 순차적으로 번호를 부여한다.

각 레벨의 시작 노드는 2^n의 번호를 가진다. 이를 배열로 표시하면 아래와 같다.

이진 트리 번호의 성질은 아래와 같다.

1. 부모 노드의 번호는 i / 2 이다.
2. 왼쪽 자식 노드의 번호는 2 * i 이다.
3. 오른쪽 자식 노드의 번호는 2 * i + 1 이다.

배열로 이진 트리를 표현하면 편향 이진 트리에서 메모리 공간이 낭비될 수 있고,
배열의 크기 변경이 어렵다는 단점이 있다.

알고리즘에서 비선형 자료구조를 완전탐색할 수 있다.

선형 자료구조와 달리 비선형 자료구조를 완전탐색할 때는 BFS, DFS를 사용한다.

아래는 이진 트리를 BFS로 완전탐색하는 코드이다.
1) 이진 트리

package live07.dist;

import java.util.ArrayDeque;
import java.util.Queue;

public class CompleteBinaryTree<T> {
	private static int SIZE;
	private static Object[] nodes;
	private int lastIndex;
	
	public CompleteBinaryTree (int size) {
		SIZE = size;
		nodes = new Object[size+1];
	}
	
	private boolean isFull() {
		return lastIndex == SIZE;
	}
	
	public void add(T e) {
		if (isFull()) {
			return;
		}
		nodes[++lastIndex] = e;
	}
	
	public void bfs() {
		Queue<Integer> queue = new ArrayDeque<>();
		queue.offer(1);
		
		int current = 0;
		while (!queue.isEmpty()) {
			current = queue.poll();
			System.out.print(nodes[current] + " ");
			
			if (current * 2 <= lastIndex) {
				queue.offer(current * 2);
			}
			
			if ((current * 2 + 1) <= lastIndex) {
				queue.offer((current * 2 + 1));
			}
		}
	}
}

2) 메인 함수

package live07.dist;

public class CompleteBinaryTreeTest {

	public static void main(String[] args) {
		int size = 9;
		
		CompleteBinaryTree<Character> tree = new CompleteBinaryTree<> (size);
		
		for (int i = 0; i < size; ++i) {
			tree.add((char)(65 + i));
		}
		
		tree.bfs();
	}
 }

이때, queue의 변화는 아래와 같다.

1 -> 2, 3 -> 3, 4, 5 -> 4, 5, 6, 7 -> 5, 6, 7, 8, 9 -> 6, 7, 8, 9 -> 7, 8, 9 -> 8, 9 -> 9

출력은 아래와 같다.

A B C D E F G H I