트리

스택 응용 문제

• 후위 표기법으로 표현된 수식 풀기

• 괄호 포함 문제도 포함

트리

• 비선형 구조
• 원소들 간 일대다 관계(그래프는 다대다)
• 원소들 간 계층 관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조
• 노드: 트리의 원소
• 한 개 이상의 노드로 이루어진 유한 집합
• 노드 중 최상위 노드는 루트(Root)
• 나머지 노드들은 각각의 트리가 될 수 있음
• 간선(Edge): 노드와 노드 사이를 연결하는 선
• 형제 노드(Sibling): 같은 부모의 자식 노드들
• 조상 노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들(부모 노드 ~ 루트 노드)
• 자손 노드: 단말 노드까지 타고 갈 때의 모든 노드
• 차수
  • 노드의 차수: 노드에 연결된 간선의 수
  • 트리의 차수: 노드 차수 중 최댓값
• 높이
  • 노드의 높이: 루트에서 노드에 이르는 간선의 수(레벨)
  • 트리의 높이: 노드 높이 중 최댓값
• 이진 트리: 차수가 2인 트리 - 배열로 표현이 쉬움
• 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리
• 모든 노드들이 최대 2개의 서브 트리를 갖는 특별한 형태의 트리
• 해당 높이에서 최대 노드의 개수는 2^높이(ex. 높이 3인 경우 최대 8개 노드로 구성
• 높이가 h인 이진 트리가 가질 수 있는 최소 노드는 h + 1개(h는 0부터 시작)
• 최대 노드의 수는 2^(h + 1) - 1 (ex. 높이 3인 경우, 15번 노드까지 있을 수 있음)
• 포화 이진 트리: 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리(노드의 수가 2^(h + 1) - 1개
• 완전 이진 트리: 노드의 수가 h + 1 ≤ n < 2^(h + 1) 1번부터 n번까지 빈 자리가 없는 이진 트리
• 편향 이진 트리: 최소 노드 개수를 가지면서 한쪽 방향의 자식 노드만을 가짐
• 배열을 이용한 트리
  • 노드 번호가 i일 때 부모의 인덱스: i / 2
  • 왼쪽 자식: 2 * i
  • 오른쪽 자식: 2 * i + 1
  • 각 레벨 시작 노드: 레벨이 n 일 때 $`2^n`$번
• 비선형 자료구조 완전탐색: 너비 우선 탐색(Breadth First Search, BFS), 깊이 우선 탐색(Depth First Search, DFS)

BFS(Breadth First Search)

• 너비 우선 탐색
• 루트 노드의 자식 노드들을 먼저 차례로 방문한 후, 각 자식 노드들을 기준으로 다시 차례로 방문
• 인접한 노드들에 대해 탐색한 후, 차례로 다시 너비우선탐색을 진행해야 하므로 큐를 사용

• 큐에 offer() 했다가 poll() 하여 나온 값을 탐색 처리하고, 그 값의 자식들을 offer() 함.
• 큐가 빌 때까지 반복

public void bfs() {
		if (isEmpty()) return;
		
		// 이진트리의 탐색 순서!!
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(1); // 처음 값(루트 노드)
		
		while (!queue.isEmpty()) {
			int current = queue.poll(); // 탐색 순서
			System.out.println(nodes[current]);
			
			// 현재 노드의 자식 노드들의 인덱스 추가
			// 왼쪽 자식 노드
			if (current * 2 <= lastIndex) queue.offer(current * 2);
			// 오른쪽 자식 노드
			if (current * 2 + 1 <= lastIndex) queue.offer(current * 2 + 1);
		}
	}

DFS(Depth First Search)

• 깊이 우선 탐색
• 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가능한 이전 노드로 계속 이동한 후 다른 방향의 노드로 탐색을 반복
• 다시 돌아와 반복하는 작업이 필요하므로 재귀 함수로 구현하거나 스택을 통해 구현

// 전위 순회: VLR
	private void dfsByPreOrder(int current) {
		if (current > lastIndex) return;
		
		System.out.print(nodes[current] + "\t");
		
		dfsByPreOrder(current * 2);
		dfsByPreOrder(current * 2 + 1);
	}
	
	// 중위 순회: LVR
	private void dfsByInOrder(int current) {
		if (current > lastIndex) return;
		
		dfsByInOrder(current * 2);
		System.out.print(nodes[current] + "\t");
		dfsByInOrder(current * 2 + 1);
	}
		
	// 후위 순회: LRV
	private void dfsByPostOrder(int current) {
		if (current > lastIndex) return;
		
		dfsByPostOrder(current * 2);
		dfsByPostOrder(current * 2 + 1);
		System.out.print(nodes[current] + "\t");
	}

힙

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조
• 최대 힙: 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 > 자식 노드의 키 값
  • 루트 노드: 키 값이 가장 큰 노드
• 최소 힙: 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 < 자식 노드의 키 값
  • 루트 노드: 키 값이 가장 작은 노드
• 힙에서는 루트 노드의 원소만을 삭제할 수 있음
• 루트 노드의 원소를 삭제하여 반환
• 힙의 종류에 따라 최댓값 또는 최솟값을 구할 수 있음

우선순위 큐(Priority Queue)

• 노드 하나의 추가·삭제의 시간 복잡도가 O(logN)이고 최댓값·최솟값을 O(1)에 구할 수 있음

• 배열을 통해 트리 형태를 쉽게 구현할 수 있음
• 우선순위를 가진 항목들을 저장
• 우선순위가 높은 순서대로 먼저 나감
• java.util.PriorityQueue
  • 두 개의 생성자를 가짐: 빈 생성자 → Comparable 인터페이스 구현 필요, Comparator를 매개변수로 가지는 생성자 → Comparator 외부 구현 필요
  • Comparable: int compareTo(T other) → 자신과 인자로 전달 받는 타 원소와 비교하여 정수 리턴. 음수 → 현재 객체가 작음, 0 → 같음, 양수 → 현재 객체가 큼
  • Comparator: int compare(T o1, T o2) → 외부 비교자