자료구조 과제 풀이(6,7,8차) Yong-hwan Kim

Presentation on theme: "자료구조 과제 풀이(6,7,8차) Yong-hwan Kim"— Presentation transcript:

1 자료구조 과제 풀이(6,7,8차) Yong-hwan Kim cherish@kut.ac.kr
Korea University of Technology and Education Laboratory of Intelligent Networks

2 6차 과제 풀이

3 6차 과제 풀이 Problem 2. In Figure 6-25 find the: A B F G H J I K L C D E
a. root : A b. leaves : D, E, H, L, J c. internal nodes : B, C, F, G, I, K d. ancestors of H : A, F, G e. descendents of F : G, H, I, J, K, L A B F G H J I K L C D E

4 1. Basic Tree Concepts Definitions
자매노드 (Sibling Node): nodes with the same parent 같은 부모 아래 자식 사이에 서로를 자매노드 (Sibling Node)라 함. B, C, D는 서로 자매노드이며, E, F도 서로 자매노드임. 부모가 없는 노드 즉, 원조격인 노드를 루트 노드 (Root Node)라 함. C, D, E, F처럼 자식이 없는 노드를 리프노드 (Leaf Node)라 함. 리프노드를 터미널 노드 (Terminal Node)라고도 함. node with out-degree zero 리프노드 및 루트노드를 제외한 모든 노드를 내부노드 (Internal Node)라 함 B

5 1. Basic Tree Concepts Definitions
트리의 구성 요소에 해당하는 A, B, C, ..., F를 노드 (Node)라 함. A node is child of its predecessor B의 바로 아래 있는 E, F를 B의 자식노드 (Child Node)라 함. A node is parent of its successor nodes B는 E, F의 부모노드 (Parent Node) A는 B, C, D의 부모노드 (Parent Node)임. 어떤 노드의 하위에 있는 노드를 후손노드 (Descendant Node)라 함. B, E, F, C, D는 A의 후손노드임. 주어진 노드의 상위에 있는 노드들을 조상노드 (Ancestor Node)라 함. B, A는 F의 조상노드임. Path a sequence of nodes in which each node is adjacent to the next one

6 6차 과제 풀이 Problem 4. In Figure 6-25 find the: A B F G H J I K L C D E
a. height of the tree : 6 b. height of subtree G : 4 c. level of node G : level 2 d. level of node A : level 0 e. height of subtree E : 1 A B F G H J I K L C D E

7 1. Basic Tree Concepts Definitions 트리의 레벨(Level)
distance from the root 루트노드를 레벨 0으로 하고 아래로 내려오면서 증가 트리의 높이(Height or Depth) level of the leaf in the longest path from the root + 1 (트리의 최대 레벨 수 + 1) = 트리의 높이(Height) 루트만 있는 트리의 높이는 1 비어있는 트리 (empty tree)의 높이는 0 (=4)

8 6차 과제 풀이 Exercises 8. Find a binary tree whose preorder and inorder travels create the same result. void preOrder(root) { if (root == NULL) return; printf("%s", root->data); preOrder(root->left); preOrder(root->right); } ≒ void inOrder(root) { inOrder(root->left); inOrder(root->right);

9 6차 과제 풀이 Exercises 10. In a binary tree, what is the maximum number of nodes that can be found in level 3? In level4? In level 12? The Maximum number of nodes in level 3 is 2^4 - 1 = 15 The Maximum number of nodes in level 4 is 2^5 - 1 = 31 The Maximum number of nodes in level 12 is 2^ = 8191

10 2. Binary Tree Properties of Binary Tree 트리 내의 노드의 수를 이라 가정했을 때
트리 내의 노드의 수를 이라 가정했을 때 Maximum Height Ex] Given N=3 in a binary tree, what is the maximum height? Minimum Height Ex] Given N=3 in a binary tree, what is the minimum height? 트리의 높이를 라고 가정했을 때 Maximum Number of Nodes Ex] Given H=3 in a binary tree, what is the maximum number of nodes? Minimum Number of Nodes Ex] Given H=3 in a binary tree, what is the minimum number of nodes?

11 6차 과제 풀이 Exercises 16. Find the root of each of the following binary trees: a. tree with postorder traversal: FCBDG root : G b. tree with preorder traversal: IBCDFEN root : I c. tree with inorder traversal: CBIDFGE root : 모든 노드 가능

12 6차 과제 풀이 Exercises 18. A binary tree has eight nodes. The postorder and inorder traversals of the tree are given below. Draw the tree. Postorder : FECHGDBA Inorder : FCEABHDG Postorder : root가 뒤에 있음을 알 수 있다. Inorder : root를 중심으로 왼쪽의 노드들로 왼쪽의 서브트리, 오른쪽 노드들로 오른쪽 서브트리가 구성됨을 알 수 있다. Ex) 1. postorder를 통해 A가 최상위 root, inorder를 통해 좌우 서브 트리를 2. 왼쪽 서브 트리 FEC만 따질 경우 root C(postorder), F는 좌 E는 우(by Inorder) 3. 오른쪽서브트리 HGDB의 경우 root B, 좌는 없고 우는 HDG(by Inorder) 등등…

13 6차 과제 풀이 Exercises 30. Show the result of the recursive function in Algorithm 6-9 using the tree in Figure 6-26. Algorithm treeTraversal (tree) if tree is null print "Null" else treeTraversal (right subtree) print "right is done" treeTraversal (left subtree) print (tree data) end if end treeTraversal Null right is done K J I H G F E D C B A

14 7차 과제 풀이

15 1. Basic Concepts Binary search tree (BST): binary tree that is
All items in left subtree are less than the root All items in right subtree are greater than the root Each subtree itself is a binary search tree BST의 예

16 7차 과제 풀이 Exercises 2. Create a binary search tree using the following data entered as a sequential set :

17 7차 과제 풀이 Exercises 6. Insert 44 and 50 into the tree created in Exercise 3. Insert 44 and 50

18 7차 과제 풀이 Exercises 10. The binary search tree in Figure 7-19 was created by starting with a null tree and entering data from the keyboard. In what sequence were the data entered? If there is more than one possible sequence, identify the alternatives. 1 : 2 :

19 7차 과제 풀이 Exercises 13. Delete the node containing 60 from the binary search tree in Figure 7-22. 중위선행자 중위후속자

20 2. BST Operations Deletion
Case 4: the node has both left and right children 노드 G를 삭제  우왕 복잡하다~~~~ 이진 탐색트리를 중위순회(In-order Traversal)한 결과를 생각 : A < B < D < F < G < H < K < L G가 삭제된 후에도 정렬된 순서를 그대로 유지하려면 G의 자리에는 G의 바로 오른쪽 H나, 아니면 G의 바로 왼쪽 F가 들어가야 함. G 바로 다음에 나오는 H를 G의 중위 후속자(In-order Successor)라 하고, G 바로 직전에 나오는 F를 G의 중위 선행자(In-order Predecessor)라고 함. 그래서, 결론적으로 G에 대한 중위 후속자나 중위 선행자가 G의 자리로 옮겨져야 한다. data copy

21 8차 과제 풀이

22 2. Balancing Tree - Insert
LL Rotation 원리 – Single Right Rotation After rotation, BF(x) = 0, BF(r) = 0,-1,1 * r: nearest ancestor of the new node whose BF(r) is +2 or -2

23 2. Balancing Tree - Insert
Case II: Right of Right 경우  “RR Rotation” 으로 해결 불균형 노드 r의 오른쪽 서브트리의 오른쪽 서브트리에 새 노드 Y가 삽입된 경우 RR Rotation 원리 – Single Left Rotation After rotation, BF(x) = 0, BF(r) = 0,-1,1

24 8차 과제 풀이 Exercises 2. Balance the AVL tree in Figure Show the balance factors in the result. LR L(루트의 왼쪽 서브 트리에서 균형 깨짐) R(균형을 깨는 노드가 서브 트리의 오른쪽에 존재) L(서브트리의 Root를 L) -> R(트리의 Root를 R)

25 2. Balancing Tree - Insert
LR Rotation Examples

26 2. Balancing Tree - Insert
RL Rotation Examples

27 2. Balancing Tree - Insert
정리 RR – 균형이 깨진 트리의 root를 L(왼쪽)으로 회전 LL – 균형이 깨진 트리의 root를 R(오른쪽)으로 회전 LR L(루트의 왼쪽 서브 트리에서 균형 깨짐) R(균형을 깨는 노드가 서브 트리의 오른쪽에 존재) 이래서 LR 이럴 경우 다음과 같이 L(서브트리의 Root를 L) -> R(트리의 Root를 R) RL R(루트의 오른쪽쪽 서브 트리에서 균형 깨짐) L(균형을 깨는 노드가 서브 트리의 왼쪽에 존재) 이래서 RL 이럴 경우 다음과 같이 R(서브트리의 Root를 R) -> L(트리의 Root를 L)

28 8차 과제 풀이 Exercises 6. Create an AVL tree using the following data entered as a sequential set. Show the balance factors in the resulting tree"

29 8차 과제 풀이 Exercises 7. Create an AVL tree using the following data entered as a sequential set. Show the balance factors in the resulting tree"

30 8차 과제 풀이 Exercises 10. Insert 44 and 50 into the tree created in Exercise 7.

31 1. Basic Concepts Heap의 속성
A heap is a special kind of tree. It has two properties that are not generally true for other trees: [Completeness] - The tree is (nearly) complete, which means that nodes are added from top to bottom, left to right, without leaving any spaces. [Heapness] - The item in the tree with the highest priority is at the top of the tree, and the same is true for every subtree. (nearly)

32 8차 과제 풀이 Exercises 2. Make a heap out of the following data read from the keyboard:

33 2. Maintenance Operations
Inserting a node into heap 효율 O(lgN) 삭제보다 비교 횟수가 적음 [힙의 삽입] “신입사원이 오면 일단 말단 자리에 앉힌 다음, 능력껏 위로 진급시키는 것(進級, Reheap Up, Promotion)”

34 8차 과제 풀이 Exercises 6. Apply the delete operation to the heap in Figure Repair the heap after the deletion.

35 2. Maintenance Operations
Deleting a node from heap 1. Deletion always occurs at the root To preserve 1st condition, the last node should move to the root 2nd condition could be broken 2. Repair the structure so that 2nd condition is satisfied Reheap Down [힙의 삭제] “사장자리가 비면 말단 사원을 그 자리에 앉힌 다음, 바로 아래 부하직원보다는 능력이 좋다고 판단될 때까지 강등시키는 것(降等, Reheap Down, Demotion)”

36 8차 과제 풀이 Exercises 8. Show the left and right children of 32 and 27 in the heap in Figure Also show the left children of 14 and 40. - 32의 왼쪽자식 : 20, 오른쪽자식 : 25 - 27의 왼짝자식 : 15, 오른쪽자식 : 14 - 14의 왼쪽자식 : NULL - 40의 왼쪽자식 : 27

37 8차 과제 풀이 10장의 경우, 요즘 겨를이 없어서 살펴보지 못하였습니다.
확신이 없는 답을 올리지는 못하겠습니다… 한 학기 동안 수고하셨고 끝까지 마무리 잘 하시길 바랍니다.

38 END.