제 4장 트리.

Presentation on theme: "제 4장 트리."— Presentation transcript:

1 제 4장 트리

2 트리 배열이나 연결리스트: 데이터를 일렬로 저장하기 때문에 탐색 연산이 순차적으로 수행되는 단점
배열이나 연결리스트: 데이터를 일렬로 저장하기 때문에 탐색 연산이 순차적으로 수행되는 단점 배열은 미리 정렬해 놓으면 이진탐색을 통해 효율적인 탐색이 가능하지만, 삽입이나 삭제 후에도 정렬 상태를 유지해야 하므로 삽입이나 삭제하는데 O(N) 시간 소요

3 응용 조직이나 기관의 계층구조 컴퓨터 운영체제의 파일 시스템 자바 클래스 계층구조 등
트리는 일반적인 트리와 이진트리(Binary Tree)로 구분 다양한 탐색트리(Search Tree), 힙(Heap) 자료구조, 컴파일러의 수식을 위한 구문트리(Syntax Tree) 등의 기본이 되는 자료구조로서 광범위하게 응용

4 4.1 트리 일반적인 트리(General Tree)는 실제 트리를 거꾸로 세워 놓은 형태의 자료구조
HTML과 XML 의 문서 트리, 자바 클래스 계층구조, 운영체제의 파일시스템, 탐색트리, 이항(Binomial)힙, 피보나치(Fibonacci)힙과 같은 우선순위큐(7장)에서 사용 일반적인 트리의 정의 트리는 empty이거나, empty가 아니면 루트노드 R과 트리의 집합으로 구성되는데 각 트리의 루트노드는 R의 자식노드이다. 단, 트리의 집합은 공집합일 수도 있다

5 용어 루트(Root)노드 – 트리의 최상위에 있는 노드 자식(Child)노드 – 노드 하위에 연결된 노드
차수(Degree) – 자식노드 수 부모(Parent)노드 – 노드의 상위에 연결된 노드 이파리(Leaf)노드 – 자식이 없는 노드 형제(Sibling)노드 – 동일한 부모를 가지는 노드 조상(Ancestor)노드 – 루트노드까지의 경로상에 있는 모든 노드들의 집합 후손(Descendant)노드 –노드 아래로 매달린 모든 노드들의 집합 서브트리(Subtree) – 노드 자신과 후손노드로 구성된 트리

6 레벨(Level) – 루트노드는 레벨 1, 아래 층으로 내려가며 레벨이 1씩 증가
- 레벨은 깊이(Depth)와 같다. 높이(Height) – 트리의 최대 레벨 키(Key) – 탐색에 사용되는 노드에 저장된 정보

7 A B E G D J C H I N P F 레벨 1 레벨 2 레벨 3 레벨 4 높이 4 루트 노드 M O K L

8 A: 트리의 루트노드 B, C, D: 각각 A의 자식노드 A의 차수: 3 B, C, D의 부모노드: A K, L, F, M, N, I, O, P: 이파리 노드들 E, F, G의 부모가 B로 모두 같으므로 이들은 서로 형제노드 {B, C, D}, {H, I}, {K, L}, {O, P}도 각각 서로 형제노드들 C의 자손: {H, I, N} C를 루트노드로 하는 서브트리는 C와 C의 자손노드들로 구성된 트리 P의 조상노드: {J, D, A} 트리 높이: 4

9 이파리 노드: 단말(Terminal)노드 또는 외부(External)노드
내부(Internal)노드 또는 비 단말(Non-Terminal)노드: 이파리가 아닌 노드 일반적인 트리를 메모리에 저장하려면 각 노드에 키와 자식 수만큼의 레퍼런스 저장 필요 노드의 최대 차수가 k라면, k개의 레퍼런스 필드를 다음과 같이 선언해야

10 null 레퍼런스 수 = Nk – (N-1) = N(k-1) + 1
k가 클수록 메모리의 낭비가 심해지는 것은 물론 트리를 탐색하는 과정에서 null 레퍼런스를 확인해야 하므로 시간적으로도 매우 비효율적

11 왼쪽자식–오른쪽형제(Left Child-Right Sibling) 표현
노드의 왼쪽 자식과 왼쪽 자식의 오른쪽 형제노드를 가리키는 2개의 레퍼런스만을 사용

12 [예제] (a)의 트리를 왼쪽자식-오른쪽형제 표현으로 변환하면, (b)의 트리를 얻으며, (c)는 (b)의 트리를 45 시계 방향으로 회전시킨 것

13 4.2 이진트리 이진트리(Binary Tree): 각 노드의 자식 수가 2 이하인 트리
컴퓨터 분야에서 널리 활용되는 기본적인 자료구조 이진트리가 데이터의 구조적인 관계를 잘 반영하고, 효율적인 삽입과 탐색을 가능하게 하며, 이진트리의 서브트리를 다른 이진트리의 서브트리와 교환하는 것이 쉽기 때문 이진트리에 대한 용어는 일반적인 트리에 대한 용어와 동일

14 (c) 루트노드의 오른쪽 서브트리가 없는(empty) 이진트리 (d) 루트노드의 왼쪽 서브트리가 없는 이진트리
[정의] 이진트리는empty이거나, empty가 아니면, 루트노드와 2개의 이진트리인 왼쪽 서브트리와 오른쪽 서브트리로 구성된다. (a) empty 트리 (b) 루트노드만 있는 이진트리 (c) 루트노드의 오른쪽 서브트리가 없는(empty) 이진트리 (d) 루트노드의 왼쪽 서브트리가 없는 이진트리 null (a) (b) (c) (d)

15 특별한 형태의 이진트리 포화이진트리(Full Binary Tree): 각 내부노드가 2개의 자식노드를 가지는 트리
완전이진트리(Complete Binary Tree): 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리 - 포화이진트리는 완전이진트리이다. (a) 포화이진트리 (b) 완전이진트리 (c) 불완전한 이진트리 (d) 불완전한 이진트리

16 이진트리의 속성 레벨 k에 있는 최대 노드 수 = 2k-1 , k = 1, 2, 3, 
높이가 h인 포화이진트리에 있는 노드 수 = 2h - 1 N개의 노드를 가진 완전이진트리의 높이 = log2(N+1)

17 즉, 한 층에 존재할 수 있는 최대 노드 수는 이전 층에 있는 최대 노드 수의 2배
레벨 1에 20 = 1개, 레벨 2에 21 = 2개, , 레벨 k에 최대 2k-1개의 노드 즉, 한 층에 존재할 수 있는 최대 노드 수는 이전 층에 있는 최대 노드 수의 2배 - 이전 층에 있는 각 노드가 최대 2개의 자식노드가지므로 높이가 h인 포화이진트리에 있는 노드 수  + 2h-1 = 2h - 1 노드 수가 N이면, h = log2(N+1)

18 N개의 노드를 가진 완전이진트리에서 N이 2h – 1보다 클 수 없으므로,
높이 h = log2(N+1) 높이가 h인 완전이진트리에 존재 할 수 있는 최대 노드 수 2h-1∼2h-1 노드 수가 2h-1보다 작으면 높이 = (h – 1) 2h-1보다 크면 높이 = (h + 1)

19 A B C I D J E F K G H 배열에 저장된 이진트리 1 2 3 4 5 6 7 8 9 10 11 12 a A B C D E F G H I J K 배열에 저장하면 노드의 부모노드와 자식노드가 배열의 어디에 저장되어 있는지를 다음과 같은 규칙을 통해 쉽게 알 수 있다. 단, 트리에 N개의 노드가 있다고 가정

20 a[i]의 부모노드는 a[i/2]에 있다. 단, i > 1이다.
a[i]의 왼쪽 자식노드는 a[2i]에 있다. 단, 2i ≤ N이다. a[i]의 오른쪽 자식노드는 a[2i+1]에 있다. 단, 2i + 1 ≤ N이다. E의 부모노드는 a[5/2] = a[2]에 있는 B E의 왼쪽과 오른쪽 자식은 각각 a[2x5] = a[10]과 a[2x5+1] = a[11]에 저장된 J와 K

21 편향(Skewed)이진트리를 배열에 저장하는 경우, 트리의 높이가 커질 수록 메모리 낭비가 심화됨
편향이진트리 A B C D E A B C D E 1 2 3 4 5 6 7 8 15 31 A B C D E 1 2 3 4 5 6 7 8 16 A B C D E 편향(Skewed)이진트리를 배열에 저장하는 경우, 트리의 높이가 커질 수록 메모리 낭비가 심화됨

22 일반적인 경우의 이진트리의 노드는 키와 2개의 레퍼런스 필드, 즉, left와 right를 가진다.
- 키와 관련된 정보도 노드에 저장되나 생략한다.

23 이진트리를 위한 Node 클래스

24 Line 01: Key를 generic 타입으로 사용하여 데이터를 노드에 저장하고, Comparable 인터페이스는 compareTo() 메소드를 통해 2개의 키를 비교하기 위해
Line 05∼06: Node 객체를 위한 생성자 Line 07∼12: Node 객체에 대한 get, set 메소드들

25 BinaryTree 클래스

26 BinaryTree 클래스의 생성자: Node 객체인 root만을 가지는 BinaryTree 객체를 line 04에서 생성
Line 05: root를 리턴하는 메소드 Line 06: 트리의 루트노드인 newRoot를 root가 가리키게 함 Line 07: 트리가 empty인지를 체크하는 메소드 이 후는 이진트리를 4종류의 방식으로 순회하는 메소드들과 기타 기본 연산들을 위한 메소드들을 선언 각 메소드를 완성시킨 프로그램은 부록 V 참조

27 4.3 이진트리의 연산 이진트리에서 수행되는 기본 연산들은 트리를 순회(Traversal)하며 이루어진다.
이진트리의 4가지 순회하는 방식 방식은 각각 다르지만 순회는 항상 트리의 루트노드부터 시작 전위순회(Preorder Traversal) 중위순회(Inorder Traversal) 후위순회(Postorder Traversal) 레벨순회(Levelorder Traversal)

28 전위, 중위, 후위순회는 트리를 순회하는 중에 노드를 방문하는 시점에 따라 구분된다.
전위, 중위, 후위순회는 모두 루트노드로부터 동일한 순서로 이진트리의 노드들을 지나가는데, 특정 노드에 도착하자마자 그 노드를 방문하는지, 일단 지나치고 나중에 방문하는지에 따라 구분됨

29 집을 노드라고 하면, 노드를 방문하는 것은 문을 열고 집안에 들어가는 것
사람이 노드(집)에는 도착했으나 집을 방문하는 것을 나중으로 미루고 왼쪽이나 오른쪽 길로 다른 집을 찾아 나설 수도 있음 모든 순회 방식은 루트노드로부터 순회를 시작하여 트리의 각 노드를 반드시 1 번씩 방문해야 순회가 종료됨

30 전위순회 전위순회는 노드 x에 도착했을 때 x를 먼저 방문 그 다음에 x의 왼쪽 자식노드로 순회를 계속
전위순회의 방문 규칙

31 각 서브트리의 방문은 동일한 방식으로 전위순회 순서를 NLR 또는 VLR로 표현
여기서 N은 노드(Node)를 방문한다는 뜻이고, V는 Visit(방문)을 의미 L은 왼쪽, R은 오른쪽 서브트리로 순회를 진행한다는 뜻

32 실선 화살표를 따라서A, B, D, G, E, H, C, F 순으로 방문
점선 화살표는 노드의 서브트리에 있는 모든 노드들을 방문한 후에 부모노드로 복귀 복귀하는 것은 프로그램에서 메소드 호출이 완료된 후에 리턴하는 것과 같음 단, 노드를 방문 하는 것은 노드의 key를 출력 

33 preorder(): 트리의 루트노드를 인자로 전달하여 호출
Line 02: 노드 n이 null 인지를 검사하고 null이면 이전 호출된 곳으로 돌아가고, null이 아니면 line 03 에서 노드 n을 방문 Line 04: 노드 n의 왼쪽 자식노드로 재귀호출하여 왼쪽 서브트리의 모든 노드들을 방문한 후 Line 05: 노드 n의 오른쪽 자식노드로 재귀호출하고 오른쪽 서브트리의 모든 노드들을 방문

34 중위순회 중위순회는 노드 x에 도착하면 x의 방문을 보류하고 x의 왼쪽 서브트리로 순회를 진행
중위순회 순서를 LNR 또는 LVR로 표현

35    중위순회: D, G, B, H, E, A, C, F 순으로 방문 ③ ① ⑤ ② ④ A A B C B C D E F

36 inorder() 메소드: 트리의 루트노드를 인자로 전달하여 호출
Line 02: 노드 n이 null 인지를 검사하고, null이면 이전 호출된 곳으로 돌아가고, null이 아니면 Line 03: 노드 n의 왼쪽 자식노드로 재귀호출하여 왼쪽 서브트리의 모든 노드들을 방문한 후에 Line 04: 노드 n을 방문 Line 05: 노드 n의 오른쪽 자식노드로 재귀호출하고 오른쪽 서브트리의 모든 노드들을 방문 

37 후위순회 후위순회는 노드 x에 도착하면 x의 방문을 보류하고 x의 왼쪽 서브트리로 순회를 진행
후위순회 순서를 LRN 또는 LRV로 표현

38    후위순회: G, D, H, E, B, F, C, A 순으로 방문 ⑤ ④ ② ① ③ A A B C B C D E F

39 postorder() 메소드: 트리의 루트노드를 인자로 전달하여 호출
Line 02: 노드 n이 null 인지를 검사하고, null이면 이전 호출된 곳으로 돌아가고, null이 아니면 Line 03: 노드 n의 왼쪽 자식노드로 재귀호출하여 왼쪽 서브트리의 모든 노드들을 방문한 후에 Line 04: 노드 n의 오른쪽 자식노드로 재귀호출하고 오른쪽 서브트리의 모든 노드들을 방문 끝으로line 05에서 노드 n을 방문

40 레벨순회 레벨순회는 루트노드가 있는 최상위 레벨부터 시작하여 각 레벨마다 좌에서 우로 노드들을 방문

41 levelorder() 메소드: 큐 자료구조를 활용
Line 02: 자바 라이브러리의 LinkedList를 사용해 구현한 Queue 사용 Line 03: q에서 삭제된 노드를 참조하기 위해 Node 타입의 지역변수를 선언

42 Line 04: 트리의 루트노드인 root를 q에 추가한 후
Line 05의 while-루프를 수행 루프 내에서는 line 06에서 q의 가장 앞에 있는 노드를 삭제하고 t가 이 노드를 참조하 Line 07: q에서 삭제된 노드를 방문하고, Line 08∼11: t의 왼쪽 자식과 오른쪽 자식을 q에 차례로 삽입 자식이 null인 경우, 삽입 과정을 건너뛴다.

43 기타 이진트리 연산 size(): 트리의 노드 수 계산 height(): 트리의 높이 계산
isEqual(): 2개의 이진트리에 대한 동일성 검사 size()와 height()는 후위순회에 기반하고, isEqual()은 전위순회에 기반

44 트리의 노드 수 트리의 노드 수를 계산하는 것은 트리의 아래에서 위로 각 자식의 후손노드 수를 합하며 올라가는 과정을 통해 수행되며, 최종적으로 루트노드에서 총 합을 구함 트리의 높이도 아래에서 위로 두 자식을 각각 루트노드로 하는 서브트리의 높이를 비교하여 보다 큰 높이에 1을 더하는 것으로 자신의 높이를 계산하며, 최종적으로 루트노드의 높이가 트리의 높이가 됨 2개의 이진트리를 비교하는 것은 다른 부분을 발견하는 즉시 비교 연산을 멈추기 위해 전위순회 방법을 사용

45 (루트노드의 왼쪽 서브트리에 있는 노드 수) +
[핵심 아이디어] 트리의 노드 수 = 1 + (루트노드의 왼쪽 서브트리에 있는 노드 수) + (루트노드의 오른쪽 서브트리에 있는 노드 수) 1은 루트노드 자신을 계산에 반영하는 것

46 size() 메소드: 루트노드를 인자로 전달하여 호출
Line 02: 노드가 null이면 line 03에서 0을 리턴하고, null이 아니면 line 05에서 왼쪽 자식노드를 루트노드로 하는 서브트리의 노드 수와 오른쪽 자식노드를 루트노드로 하는 서브트리의 노드 수를 더한 결과에 1을 더한 값을 리턴

47 트리의 높이 [핵심 아이디어] max (루트의 왼쪽 서브트리의 높이, 루트의 오른쪽 서브트리의 높이) 트리의 높이 = 1 +
1은 루트노드 자신을 계산에 반영 왼쪽과 오른쪽 서브트리의 높이는 같은 방식으로 계산

48 height() 메소드: 루트노드를 인자로 전달하여 호출
Line 02: 노드가 null이면, line 03에서 0을 리턴하고, null이 아니면 line 05에서 왼쪽 자식노드를 루트노드로 하는 서브트리 높이와 오른쪽 자식노드를 루트노드로 하는 서브트리의 높이 중에서 보다 큰 높이에 1을 더한 값을 리턴

49 이진트리 비교 [핵심 아이디어] 전위순회 과정에서 다른 점이 발견되는 순간 false를 리턴
isEqual() 메소드: 비교하려는 두 트리의 루트노드들을 인자로 전달하여 호출 Line 02: 노드 n과 m 둘 중에 하나가 null인 경우 만일 둘 다 null이면 true를 리턴하고 한 쪽만 null이면 트리가 다른 것이므로 false를 리턴

50 Line 05 (만일 둘 다 null이 아니면): 두 노드의 키를 비교하여 다르면 (1 또는 -1인 경우) false를 리턴
0이면 같은 key값을 갖는 경우이므로 line 08∼09에서 각 트리의 왼쪽 자식노드와 오른쪽 자식노드를 인자로 하여 isEqual() 메소드를 재귀호출

51 수행시간 앞서 설명된 각 연산은 트리의 각 노드를 한 번씩만 방문하므로 O(N) 시간이 소요

52 스레드 이진트리 이진트리의 기본 연산들은 레벨순회를 제외하고 모두 스택 자료구조를 사용: 메소드의 재귀호출은 시스템 스택을 사용하므로 스택 자료구조를 사용한 것으로 간주 스택에 사용되는 메모리 공간의 크기는 트리의 높이에 비례 스택 없이 이진트리의 연산을 구현하는 2 가지 방법 [1] Node 객체에 부모노드를 가리키는 레퍼런스 필드를 추가로 선언하여 순회에 사용하는 방법 [2] 노드의 null 레퍼런스들을 활용하는 것 (스레드 이진트리 (Threaded Binary Tree)

53 null 레퍼런스 공간에 다음에 방문할 노드의 레퍼런스를 저장
스레드는 운영체제에서 스케줄러가 운영하는 독립적인 수행 단위인 스레드와는 전혀 관계 없는 단어

54 N개의 노드가 있는 이진트리의 null 레퍼런스 필드 수 = (N+1)
왜냐하면 각 노드마다 2개의 레퍼런스 필드(left와 right)가 있으므로 총 2N개의 레퍼런스 필드가 존재하고, 이 중에서 부모 자식을 연결하는 레퍼런스는 N-1개이기 때문 부모 자식을 연결하는 레퍼런스가 N-1개인 이유는 루트노드를 제외한 각 노드가 1개의 부모노드를 갖기 때문 스레드 이진트리: N+1개의 null 레퍼런스를 활용하여, 이전에 방문한 노드와 다음에 방문할 노드를 가리키도록 만들어 순회 연산이 스택 없이도 수행될 수 있도록 만든 트리

55 스레드 이진트리는 대부분의 경우 중위순회에 기반하여 구현되나, 전위순회이나 후위순회에 기반하여 스레드 트리를 구현할 수도 있음
스레드 이진트리는 스택을 사용하는 순회보다 빠르고 메모리 공간도 적게 차지한다는 장점을 갖지만 데이터의 삽입과 삭제가 잦은 경우 그 구현이 비교적 복잡한 편이므로 좋은 성능을 보여주지 못한다는 문제점 Node 객체에 2개의 boolean 필드를 사용하여 레퍼런스가 스레드(다음 방문할 노드를 가리키는)로 사용되는 것인지 아니면 left나 right가 트리의 부모 자식 사이의 레퍼런스인지를 각각 true 와 false로 표시해주어야 함

56 중위순회 스레드 이진트리 점선 화살표는 직전 방문 노드를 가리키는 스레드이고, 실선 화살표는 다음에 방문 노드를 가리키는 스레드

57 4.4 상호배타적 집합을 위한 트리 연산 집합에 관련된 연산:
합집합(union) 연산 주어진 원소에 대해 어느 집합에 속해 있는지를 계산하는 find 연산 상호배타적 집합(Disjoint Set): 어느 두 집합도 중복된 원소를 갖지 않는 집합들 상호배타적 집합의 union과 find연산은 9.4절의 Kruskal의 최소신장트리 알고리즘을 구현하는데 활용

58 상호배타적 집합들을 메모리에 저장하기 위해 1차원 배열 사용
원소를 0, 1, 2, , N-1로 놓으면 이를 배열의 인덱스로 활용 집합에 속한 원소들 사이에 특정한 순서가 없고, 또 중복된 원소도 없음

59 2개의 상호배타적 집합을 일반적인 트리로 표현하여 1차원 배열에 저장
각 집합은 루트가 대표하고, 루트의 배열 원소에는 루트 자신이 저장되며, 루트가 아닌 노드의 원소에는 부모노드를 저장

60 상호배타적 집합에 대한 연산 union 연산: 2개의 집합을 하나의 집합으로 만드는 연산
find 연산: 인자로 주어지는 x가 속한 집합의 대표 노드, 즉, 루트를 찾는 연산 find(6)은 a[6] = 2를 통해 6의 부모노드인 2를 찾고, a[2] = 7으로 2의 부모노드를 찾으며, 마지막으로 a[7] = 7이기 때문에 7를 리턴 즉, “6은 7이 대표 노드인 집합에 속해 있다”는 것을 리턴 find(3) = 7이므로, 6과 3은 동일한 집합에 속함 find(9) = 4이므로, 6과 9는 서로 다른 집합에 속함

61 Union 연산 [핵심 아이디어] 먼저 union 연산은 rank에 기반하여 (union-by-rank) rank가 높은 루트가 union 후에도 승자(합쳐진 트리의 루트)가 되도록 한다. 트리의 노드 수에 기반(즉, 노드 수가 많은 트리의 루트가 승자가 되도록)하여 union 을 수행해도 rank 기반 union과 동등한 성능을 보임 루트의 rank는 트리의 높이와 일단은 같다고 생각해도 됨 rank가 높은 루트를 승자로 만드는 이유는 합쳐진 트리가 더 커지지 않게 만일 두 트리의 높이가 같은 경우에는 둘 중 하나의 루트가 승자가 되고 합쳐진 트리의 높이는 1 증가

62 (c) 비효율적인 union 연산: 합쳐진 트리의 높이가 1 증가하므로 비효율적인 union
(a) union 수행 전 (b) union 수행 후 (c) 비효율적인 union rank를 기반한 union 연산

63 rank에 기반한 union연산의 목적은 두 트리가 하나로 합쳐진 후에 트리의 높이가 커지는 것을 방지하기 위함
find 연산을 수행할 때 루트노드까지 올라가야 하므로 트리의 높이가 낮을 수록 find의 수행시간을 줄일 수 있기 때문 단, 두 트리의 루트노드들의 rank가 같으면 어쩔 수 없이 하나의 루트노드가 승자가 되고 승자의 rank도 1 증가시켜야 함

64 [예제] (a) union(7,4) 수행 (b) 수행 결과 a[4] =7로 갱신되었고 트리도 하나로 합쳐짐
각 노드 옆의 숫자는 노드의 rank로서 두 루트의 rank가 다르므로 union 수행 후에도 승자인 7의 rank 값도 변하지 않음 (a) union 수행 전 (b) union 수행 후

65 Find 연산 [핵심 아이디어] find 연산을 수행하면서 루트노드까지 올라가는 경로 상의 각 노드의 부모노드를 루트로 갱신한다. 이를 경로압축(Path Compression)이라고 한다. (a) find (1) 연산 수행 전 (b) find 연산 수행 후

66 경로압축은 당장 find(1) 연산의 수행시간을 줄이지 않으나, 추후의 find(1)과 find(2)연산의 수행시간을 단축함
(a) find(1)을 수행하면 루트인 10까지 올라가는 경로 상의 모든 노드 1, 2, 7의 부모노드를 10으로 갱신하여 (b)와 같은 트리를 만든다. 경로압축은 당장 find(1) 연산의 수행시간을 줄이지 않으나, 추후의 find(1)과 find(2)연산의 수행시간을 단축함 경로압축으로 인해 루트의 rank는 트리의 높이와 달라질 수 있음 그림(a)의 트리 높이는 4인데, 경로압축 후에 트리의 높이는 3이다. 하지만 경로압축으로 인해 루트나 그 밖의 노드들의 rank 값은 변하지 않음 rank 를 사용하여 union 연산을 수행하는 이유는 집합들 전체에 대한 총괄적인 상각분석을 위함

67 상호배타적 집합을 위한 Node 클래스

68 Node 객체는 int 타입의 parent와 rank 를 가짐
- 초기에는 자기 자신을 부모노드로 초기화 - rank는 0으로 초기화 Line 04∼07: Node 객체의 생성자 Line 08∼11: Node 객체에 대한 get, set 메소드들

69 상호배타적 집합을 위한 UnionFind 클래스

70 Line 03∼05: UnionFind 객체의 생성자
객체는 Node 객체를 원소로 하는 1차원 배열을 가짐 Line 07∼11: find() 메소드로 i가 속한 트리의 루트를 리턴하는 동시에 노드 i에서 루트까지의 경로 상의 모든 노드들에 대한 부모노드를 루트로 갱신하는 경로압축 수행 경로압축은 line 09에서 수행: find(a[i].getParent())의 값이 계속 루트노드로 리턴되면서 경로 상의 각 노드 i의 parent가 동일한 루트로 갱신 Line 12∼26: union() 메소드로 i가 속한 트리와 j가 속한 트리의 루트를 각각 line 13과 14에서 찾고, 만일 두 루트가 같으면 line 15에서 union을 수행하지 않고 리턴

71 Line 21∼25: 두 루트의 rank가 같은 경우로, 둘 중에 하나가 승자가 됨
두 루트가 다르면, line 17∼20에서 두 루트의 rank를 비교하여 큰 rank를 가진 루트(승자)가 작은 rank를 가진 루트의 부모노드로 대체 승자가 합쳐진 트리의 루트로 남게 됨 일련의 과정에서 승자의 rank는 변하지 않음에 주목 Line 21∼25: 두 루트의 rank가 같은 경우로, 둘 중에 하나가 승자가 됨 프로그램에서는 임의로 i가 속한 트리의 루트가 승자가 되도록 함. 마지막으로 승자의 rank를 1 증가시킴

72 main 클래스

73 [프로그램의 수행 결과

74 2 1 1 a union(9, 1) 연산 수행 전 집합 {7, 2, 8, 3, 1, 6} 집합 {4, 0, 5, 8} 4 2
8 3 1 4 1 6 5 9 집합 {7, 2, 8, 3, 1, 6} 집합 {4, 0, 5, 8} 1 2 3 4 5 6 7 8 9 a 4 2 7 union(9, 1) 연산 수행 전

75 2 7 1 1 2 8 3 1 4 6 5 9 집합 {7, 2, 8, 3, 1, 6, 4, 0, 5, 8} 1 2 3 4 5 6 7 8 9 a 4 7 2 union(9, 1) 연산 수행 후

76 수행시간 union 연산: 두 루트노드들을 각각 찾는 find 연산을 수행한 후에, rank를 비교하여 승자가 합쳐진 트리의 루트노드로 남음 rank가 같은 경우엔 둘 중에 하나가 승자가 되고 승자의 rank를 1 증가 시킴. 그러므로 find 연산을 제외한 순수 union 연산의 수행시간은 O(1) 시간 find 연산의 수행시간: 최대 트리의 높이만큼 올라가야 하므로 트리의 높이에 비례 find 연산을 수행하며 경로압축을 하므로, 경로상의 노드에 대해 추후에 수행되는 find 연산의 수행시간은 트리의 높이보다는 적게 소요

77 상각분석: O(N)번의 find와 union 연산들을 수행하여 걸린 총 시간을 연산 횟수로 나누어 1회의 연산 수행시간을 계산
상각분석 결과: 1회의 find 연산의 수행시간이 O(log*N) log*N = 1이하의 값을 얻기 위해 N에다가 log연산을 연속적으로 수행해야 하는 횟수 N = 2, 4, 16, 65536, 일 때 log*N의 값

78 응용 9.4절의 Kruskal의 최소신장트리 알고리즘
트리에서 가장 가까운 공통 조상노드(Least Common Ancestor) 찾기 네트워크의 연결 검사 퍼콜레이션(Percolation) 이미지 처리(Image Processing) 조각그림 맞추기(Jigsaw Puzzle) 바둑 같은 게임 등에 활용

79 요약 트리는 계층적 자료구조로서 배열이나 연결리스트의 단점을 보완하는 자료구조
트리는 계층적 자료구조로서 배열이나 연결리스트의 단점을 보완하는 자료구조 왼쪽자식–오른쪽형제 표현은 노드의 차수가 일정하지 않은 일반적인 트리를 구현하는 매우 효율적인 자료구조 포화이진트리는 각 내부노드가 2개의 자식 노드를 가지는 트리 완전이진트리는 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리이다. 포화이진트리는 완전이진트리이다.

80 이진트리의 순회 방법 - 전위순회(NLR) - 중위순회(LNR) - 후위순회(LRN)
- 레벨순회-레벨순회는 큐 자료구조를 사용해서 구현 이진트리 높이 계산과 노드 수의 계산에는 후위순회가 적합, 이진트리의 비교에는 전위순회가 적합 스택 없이 이진트리를 순회하기 위해 노드의 null 레퍼런스 대신 다음에 방문할 노드의 레퍼런스를 저장한 이진트리를 스레드 이진트리라고 함 이진트리의 높이 및 노드 수의 계산, 각 트리 순회, 동일성 검사는 트리의 모든 노드들을 방문해야 하므로 각각 O(N) 시간이 소요

81 상호배타적 집합의 union과 find연산을 효율적으로 수행하기 위해, union 은 rank기반 연산을 수행하고, find 연산은 경로압축을 수행
union연산의 수행시간: O(1) 시간 find 연산의 수행시간: O(log*N)