11. 트리.

Presentation on theme: "11. 트리."— Presentation transcript:

1 11. 트리

2 Java Collections Framework 클래스

3 가계도

4 11.1 트리 경로 : 인접 노드의 시이퀀스 트리의 크기 : 노드의 개수 서브트리와 슈퍼트리
루트 경로 : 루트로부터 해당 노드까지의 유일한 경로 루트-리프 경로 : 리프 노드에 이르는 루트 경로 경로의 길이 : 부모-자식 쌍의 개수. 노드의 개수보다는 하나 적음 트리의 크기 : 노드의 개수 공백 트리 : 크기가 0인 유일한 트리 단독 트리 : 크기가 1인 트리 서브트리와 슈퍼트리 T1의 모든 노드가 T2의 노드이고, T1에 있는 y의 부모인 x가 동시에 T2에 있는 y의 부모일 때, T1은 T2의 서브트리가 됨 T2은 T1의 슈퍼트리라고 함

5 노드, node, vertex 가지, edge 레벨 A 1 B C D E F G H I 2 J 3

6 11.2 트리의 특성 (1) 트리의 높이 노드의 깊이 레벨 트리의 경로 길이 트리의 너비 노드의 차수 트리의 차수
최장 루트 경로의 길이이며, 최장 루트-리프 경로의 길이와 같음 노드의 깊이 노드의 루트 경로의 길이 레벨 주어진 깊이에 있는 모든 노드로 구성됨 트리의 경로 길이 트리에 있는 모든 노드에 대한 깊이의 합 트리의 너비 최대 레벨 크기 노드의 차수 자식들의 개수 트리의 차수 노드들의 차수 중에서 최대 차수

7 트리의 특성 (2) d: 차수, h: 높이 포화 트리 (full tree)
모든 리프가 같은 레벨에 있고, 모든 노드가 동일한 차수를 가지고 있음 각 노드의 차수는 트리의 차수와 같음 각각의 차수와 높이를 가지는 포화 트리는 유일함 포화 트리의 크기 포화 트리의 높이 트리의 크기에 대한 범위 d: 차수, h: 높이

8 트리의 특성 (3) 내부 노드 외부 노드 내부 경로 길이 외부 경로 길이 경로 길이의 예 : 허프만 코드 트리
리프가 아닌 노드 어떤 응용에서는 내부 노드가 리프 노드와는 다른 데이터 타입을 사용하여 구현됨 외부 노드 리프 노드가 데이터가 없는 더미 노드로 사용될 경우 외부 노드라고 부름 어떤 응용에서는 모든 외부 노드를 표현하는데 하나의 더미 노드만을 사용함 내부 경로 길이 내부 노드에만 적용되는 경로 길이 외부 경로 길이 어떤 레벨에서 외부 노드의 개수와 레벨을 곱한 값으로 주어지는 가중치의 합계 경로 길이의 예 : 허프만 코드 트리

9 추상 트리

10 경로 길이가 32인 트리 레벨 1 2 3 4 5

11 포화(full) 트리 d = 2, h = 4, w = 16, n = 31 d = 5, h = 2, w = 25, n = 31

12 차수가 2이고 높이가 4인 트리 d = 2, h = 4, n = 7 d = 2, h = 4, n = 17

13 화일 시스템 트리

14 철자 트리

15 허프만 코드 트리

16 11.3 트리의 순환 정의 정의 트리는 공집합이거나 r이 노드이고 S가 서로 분리된 트리의 집합일 때, 어떤 트리도 r과 r을 포함하지 않는 쌍(r, S)로 표현된다. 노드 r을 트리의 루트라고 부르고 S에 있는 트리를 서브트리 (subtree)라고 부른다.

17 트리의 순환 정의를 검증 = = =

18 동등 무순서 트리 = =

19 무순서 트리 클래스 LISTING 11.1: An UnorderedTree Class
1 class UnorderedTree { 2 private Object root; 3 private Set subtrees; 4 private int size; 5 public UnorderedTree() { // constructs the empty tree 6 } 7 8 public UnorderedTree(Object root) { // constructs a singleton 9 this. root= root; 10 subtrees = new Set(); // constructs the empty set 11 size = 1; 12 } 13

20 14 public UnorderedTree(Object root, Set trees) {
15 this (root); 16 for (Iterator it=trees.iterator(); it.hasNext(); ) { Object object=it.next(); if (object instanceof UnorderedTree) { 19 UnorderedTree tree = (UnorderedTree)object; 20 subtrees.add(tree); 21 size += tree.size(); } 23 } 24 } 26 public int size() { 27 return size; 28 } 29 }

21 무순서 트리 구축 UnorderedTree treeA, treeB, treeD; UnorderedTree treeC = new UnorderedTree(“C”); UnorderedTree treeE = new UnorderedTree(“E”); UnorderedTree treeF = new UnorderedTree(“F”); UnorderedTree treeG = new UnorderedTree(“G”); // build subtree rooted at B: Set subtreesOfB = new Set(); subtreesOfB.add(treeE); subtreesOfB.add(treeF); treeB = new UnorderedTree("B", subtreesOfB); // build subtree rooted at D: Set subtreesOfD = new Set(); subtreesOfD.add(treeG); treeD = new UnorderedTree("D", subtreesOfD); // build subtree rooted at A: Set subtreesOfA = new Set(); subtreesOfA.add(treeB); subtreesOfA.add(treeC); subtreesOfA.add(treeD); treeA = new UnorderedTree("A", subtreesOfA); 결과는 그림

22 그림 11.3 : 구축되는 트리

23 11.4 응용: 결정 트리 결정 트리(decision tree) 여러 가지 대안들의 시이퀀스를 분석하는데 사용되는 무순서 트리
각각의 내부 노드는 결정 과정에서 결정이 내려지는 단계를 표현하고 서브 트리는 그 단계에서의 대안을 표현

24 식사 주문에 사용되는 결정 트리

25 식사 주문에 사용되는 다른 결정 트리

26 11.5 순서 트리 정의 순서 트리(ordered tree)는 공집합이거나 r이 노드이고 S가 서로 분리된 트리의 시이퀀스일 때, 모든 트리가 r과 분리된 쌍 (r, S)이다. 순서 트리와 정렬 트리 순서 트리와 정렬 트리는 같지 않음 “순서”라는 용어는 트리의 구조와 관련 있는 것이지, 그것의 내용과는 관계가 없음

27 동일하지 않은 순서 트리 ≠ ≠

28 호출 트리는 순서 트리임

29 11.6 순서 트리를 위한 순회 알고리즘 레벨 순서(level order) 순회
1. 큐를 초기화한다. 2. 루트를 큐에 삽입한다. 3. 큐가 공백이 될 때까지 단계 4-6을 반복한다. 4. 큐에서 첫 번째 노드 x를 삭제한다. 5. x를 방문한다. 6. x의 모든 자식들을 순서대로 큐에 삽입한다. 전위(preorder) 순회 (루트 노드 우선) 1. 루트를 방문한다. 2. 각 서브트리를 순서대로 전위 순회한다. 후위(postorder) 순회 (루트 노드 나중) 1. 각 서브트리를 순서대로 후위 순회한다. 2. 루트를 방문한다.

30 레벨 순서 순회

31 전위 순회

32 11.7 완전 순서 트리 선형화 또는 직렬화 자연 인덱스 번호 또는 노드 인덱스
트리를 메모리나 디스크에 저장하는 방법 세 가지 순회 알고리즘 중 어떤 것도 트리를 선형화하는데 사용할 수 있음 자연 매핑 : 레벨 순서 순회를 사용하여 선형화하는 과정 자연 인덱스 번호 또는 노드 인덱스 트리의 레벨 순서 순회에 따라 순서적으로 매겨져 있는 번호 완전 순서 트리(complete ordered tree) 최하위 레벨의 노드 중 오른쪽 몇 개의 원소가 없는 것을 제외하고는 포화 트리와 같은 순서 트리 이러한 트리는 미사용 원소가 없이 배열에 저장이 가능하고, 배열의 크기는 트리에 있는 노드의 개수와 같음

33 차수가 3인 순서 트리의 직렬화

34 희소 순서 트리의 노드 인덱스 번호

35 완전 순서 트리