C언어 응용 제 10 주 트리.

Presentation on theme: "C언어 응용 제 10 주 트리."— Presentation transcript:

1 C언어 응용 제 10 주 트리

2 다음 주 과제 9장 읽어오기 숙제 해서 제출하기

3 트리 트리 이진 트리 이진 트리의 구현 이진 트리의 순회 이진 탐색 트리 히프

4 트리의 개념을 이해한다. 이진 트리의 자료구조를 알아본다. 이진 트리에서의 순회를 이해한다. 이진 탐색 트리의 개념을 이해하고 연산 방법을 이해한다. 히프의 자료구조를 이해한다.

5 트리(tree) 트리 자료구조의 예 – 가계도 원소들 간에 1:多 관계를 가지는 비선형 자료구조
원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조 트리 자료구조의 예 – 가계도 가계도의 자료 : 가족 구성원자료를 연결하는 선 : 부모-자식 관계 표현 [그림 8-1] 가계도_트리 자료구조의 예

6 조상 – 현재 위치에서 연결된 선을 따라 올라가면서 만나는 사람들
철수의 자식 – 성호, 영주, 진호 성호, 영주, 진호의 부모 – 철수 같은 부모의 자식들끼리는 형제관계 성호, 영주, 진호는 형제관계 조상 – 현재 위치에서 연결된 선을 따라 올라가면서 만나는 사람들 수영의 조상 : 승완, 성호, 철수 자손 - 현재 위치에서 연결된 선을 따라 내려가면서 만나는 사람들 성호의 자손 : 승우, 승완, 수영, 수철 선을 따라 내려가면서 다음 세대로 확장 가족 구성원 누구든지 자기의 가족을 데리고 분가하여 독립된 가계를 이룰 수 있다

7 트리 A [그림 8-2] 트리 A

8 간선 – 노드를 연결하는 선. 부모 노드와 자식 노드를 연결 형제 노드 – 같은 부모 노드의 자식 노드들
노드 – 트리의 원소 트리 A의 노드 - A,B,C,D,E,F,G,H,I,J,K,L 루트 노드 – 트리의 시작 노드 트리 A의 루트노드 – A 간선 – 노드를 연결하는 선. 부모 노드와 자식 노드를 연결 형제 노드 – 같은 부모 노드의 자식 노드들 B,C,D는 형제 노드 조상 노드 – 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 K의 조상 노드 : F, B, A 서브 트리 – 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 각 노드는 자식 노드의 개수 만큼 서브 트리를 가진다. 자손 노드 – 서브 트리에 있는 하위 레벨의 노드들 B의 자손 노드 – E,F,K,L

9 차수 높이 노드의 차수 : 노드에 연결된 자식 노드의 수. 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
A의 차수=3, B의 차수=2, C의 차수=1 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 트리 A의 차수=3 단말 노드(리프 노드) : 차수가 0인 노드. 자식 노드가 없는 노드 높이 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨 B의 높이=1, F의 높이=2 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨 트리 A의 높이=3

10 포리스트 : 서브트리의 집합 트리A에서 노드 A를 제거하면, A의 자식 노드 B, C, D에 대한 서브 트리가 생기고, 이들의 집합은 포리스트가 된다. [그림 8-3] 노드 A를 제거하여 만든 포리스트

11 이진트리 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 만 가진다
트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 만 가진다 부모 노드와 자식 노드 수와의 관계 ☞ 1:2 공백 노드도 자식 노드로 취급한다. 0 ≤ 노드의 차수 ≤ 2 [그림 8-4] 이진 트리의 기본 구조

12 이진트리는 순환적 구성 노드의 왼쪽 자식 노드를 루트로 하는 왼쪽 서브트리도 이진 트리
노드의 오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리도 이진 트리 [그림 8-5] 이진 트리의 서브 트리

13 추상 자료형 이진트리 ADT BinaryTree 데이터 : 공백이거나 루트 노드, 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된
    데이터 :  공백이거나 루트 노드, 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된               노드들의 유한 집합     연산 :           bt, bt1, bt2∈BinaryTree; item∈Element;           createBT() ∷= create an empty binary tree;                 // 공백 이진 트리를 생성하는 연산                  isEmpty(bt) ∷= if (bt is empty) then return true                          else return false;                 // 이진 트리가 공백인지 아닌지를 확인하는 연산           makeBT(bt1, item, bt2) ∷= return {item을 루트로 하고 bt1을 왼쪽 서브 트리,                                              bt2를 오른쪽 서브 트리로 하는 이진 트리}                 // 두개의 이진 서브 트리를 연결하여 하나의 이진 트리를 만드는 연산           leftSubtree(bt) ∷= if (isEmpty(bt)) then return null                              else return left subtree of bt;                 // 이진 트리의 왼쪽 서브 트리를 구하는 연산           rightSubtree(bt) ∷= if (isEmpty(bt)) then return null                               else return right subtree of bt;                 // 이진 트리의 오른쪽 서브 트리를 구하는 연산           data(bt) ∷= if (isEmpty(bt)) then return null                       else return the item in the root node of bt;                 // 이진 트리에서 루트 노드의 데이터(item)를 구하는 연산 End  BinaryTree

14 이진트리의 특성 정의1) n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가진다.
정의2) 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 ( 2 ℎ+1 −1)개가 된다. 이진 트리의 높이가 h가 되려면 한 레벨에 최소한 한 개의 노드가 있어야 하므로 높이가 h인 이진 트리의 최소 노드의 개수는 (h+1)개 하나의 노드는 최대 2개의 자식노드를 가질 수 있으므로 레벨 i에서의 노드의 최대 개수는 2 𝑖 개 이므로 높이가 h인 이진 트리 전체의 노드 개수는 𝑖=0 ℎ 2 𝑖 = 2 ℎ+1 −1 2−1 = 2 ℎ+1 −1

15 높이가 3이면서 최소의 노드를 갖는 이진트리와 최대의 노드를 갖는 이진트리
[그림 8-6] 높이가 3이면서 최소의 노드를 갖는 이진 트리와 최대의 노드를 갖는 이진 트리

16 이진 트리의 종류 포화 이진 트리 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
높이가 h일 때, 최대의 노드 개수인 ( 2 ℎ+1 −1)개의 노드를 가진 이진 트리 루트를 1번으로 하여 2 ℎ+1 −1 까지 정해진 위치에 대한 노드 번호를 가진다. [그림 8-7] 높이가 3인 포화 이진 트리

17 완전 이진 트리 높이가 h이고 노드 수가 n개일 때 (단, h+1 ≤ n < 2 ℎ+1 −1 ),
[그림 8-8] 높이가 3인 완전 이진 트리

18 편향 이진 트리 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리 왼쪽 편향 이진 트리
모든 노드가 왼쪽 자식 노드만을 가진 편향 이진 트리 오른쪽 편향 이진 트리 모든 노드가 오른쪽 자식 노드만을 가진 편향 이진 트리 [그림 8-9] 높이가 3인 편향 이진 트리

19 순차 자료구조를 이용한 이진 트리의 구현 1차원 배열의 순차 자료구조 사용
높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용 인덱스 0번 : 실제로 사용하지 않고 비워둔다. 인덱스 1번 : 루트 저장

20 순차 자료구조를 이용한 이진 트리의 구현 [그림 8-10] 완전 이진 트리의 배열 표현

21 왼쪽 편향 이진 트리의 1차원 배열 표현 [그림 8-11] 편향 이진 트리의 배열 표현

22 이진 트리의 1차원 배열에서의 인덱스 관계 이진 트리의 순차 자료구조 표현의 단점
편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생 트리의 원소 삽입/삭제에 대한 배열의 크기 변경 어려움 [표 8-1] 이진 트리를 표현한 1차원 배열에서의 인덱스 관계

23 연결 자료구조를 이용한 이진트리의 구현 단순 연결 리스트를 사용하여 구현
이진 트리의 모든 노드는 2개의 자식 노드를 가지므로 일정한 구조의 노드를 사용할 수 있다. 이진 트리의 노드 구조에 대한 C 구조체 정의 typedef struct tag_TreeNode {           char data;           struct tag_TreeNode *left;            struct tag_TreeNode *right;    } treeNode; [그림 8-12] 이진 트리의 노드 구조

24 완전 이진 트리의 단순 연결 리스트 표현 [그림 8-13] 이진 트리의 연결 자료구조 표현

25 이진 트리의 순회(traversal) 순회를 위해 수행할 수 있는 작업 정의
계층적 구조로 저장되어있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산 순회를 위해 수행할 수 있는 작업 정의 ⑴ 현재 노드를 방문하여 데이터를 읽는 작업 D ⑵ 현재 노드의 왼쪽 서브트리로 이동하는 작업 L ⑶ 현재 노드의 오른쪽 서브트리로 이동하는 작업 R 이진 트리가 순환적으로 정의되어 구성되어있으므로, 순회작업도 서브트리에 대해서 순환적으로 반복하여 완성한다. 왼쪽 서브트리에 대한 순회를 오른쪽 서브트리 보다 먼저 수행한다. 순회의 종류 전위 순회 중위 순회 후위 순회

26 전위 순회(preorder traversal)
수행 방법 ① 현재 노드 n을 방문하여 처리한다. : D ② 현재 노드 n의 왼쪽 서브트리로 이동한다. : L ③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R 전위 순회 알고리즘 preorder(T)     if (T≠null) then {           visit T.data;           preorder(T.left);                 preorder(T.right);      } end preorder()

27 전위 순회의 예 [그림 8-14] 이진 트리의 전위 순회 경로_A-B-D-H-E-I-J-C-F-G-K

28 전위 순회 과정 >> A-B-D-H-E-I-J-C-F-G-K
① 루트 A에서 시작하여 현재 노드 A의 데이터를 읽고, 왼쪽 서브트리 B로 이동 ② 현재 노드 B의 데이터를 읽고, 왼쪽 서브트리 D로 이동한다. ③ 현재 노드 D의 데이터를 읽는다. ④ 현재 노드 D의 왼쪽 단말노드 H의 데이터를 읽고, 오른쪽 노드인 공백 노드를 읽는 것으로 노드 D에 대한 순회가 끝난다. 이제 현재 노드 D의 이전 경로인 노드 B의 오른쪽 서브트리 E로 이동한다. ⑤ 현재 노드 E의 데이터를 읽는다. ⑥ 현재 노드 E의 왼쪽 단말노드 I의 데이터를 읽는다. ⑦ 현재 노드 E의 오른쪽 단말노드 J의 데이터를 읽는 것으로 노드 E에 대한 순회가 끝난다. 노드 E의 이전 경로인 노드 B의 오른쪽 서브트리의 순회가 끝난다. ⑧ 다시 노드 B의 이전 경로인 노드 A로 돌아가서 노드 A의 오른쪽 서브트리 C로 이동하여 현재 노드 C의 데이터를 읽는다. ⑨ 현재 노드 C의 왼쪽 단말노드 F의 데이터를 읽고, 오른쪽 서브트리 G로 이동 ⑩ 현재 노드 G의 데이터를 읽는다. ⑪ 공백노드인 왼쪽 단말노드를 읽고, 현재 노드 G의 오른쪽 단말노드 K의 데이터를 읽는다.

29 수식 이진 트리에 대한 전위 순회 수식을 이진 트리로 구성한 수식 이진 트리를 전위 순회하면, 수식에 대한 전위 표기식을 구할 수 있다. [그림 8-15] 수식에 대한 이진 트리의 전위 순회 경로_-*AB/CD

30 중위 순회(inorder traversal)
수행 방법 ① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L ② 현재 노드 n을 방문하여 처리한다. : D ③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R 중위 순회 알고리즘 inorder(T)     if (T≠null) then {           inorder(T.left);           visit T.data;           inorder(T.right);      } end inorder()

31 중위 순회의 예 [그림 8-16] 이진 트리의 중위 순회 경로_H-D-B-I-E-J-A-F-C-G-K

32 중위 순회 과정 >> H-D-B-I-E-J-A-F-C-G-K
① 루트 A에서 시작하여 노드 A의 왼쪽 서브트리 B로 이동한다. 현재 노드 B의 왼쪽 서브트리 D로 이동한다. 현재 노드 D의 왼쪽 단말노드 H의 데이터를 읽는다. ② 현재 노드 D의 데이터를 읽고, 오른쪽 단말노드인 공백노드를 읽고 이전 경로인 노드 B로 돌아간다. ③ 현재 노드 B의 왼쪽 서브트리 순회가 끝났으므로, 현재 노드 B의 데이터를 읽고, 오른쪽 서브트리 E로 이동한다. ④ 현재 노드 E의 왼쪽 단말노드 I의 데이터를 읽는다. ⑤ 현재 노드 E의 데이터를 읽는다. ⑥ 현재 노드 E의 오른쪽 단말노드 J의 데이터를 읽고, 이전 경로인 노드 B로 이동한다. ⑦ 노드 B는 이미 방문했으므로 다시 이전 경로인 노드 A로 이동한다. 이로써 현재 노드 A의 왼쪽 서브트리에 대한 순회가 끝났으므로 현재 노드 A의 데이터를 읽고, 오른쪽 서브트리 C로 이동한다. ⑧ 현재 노드 C의 왼쪽 단말노드 F의 데이터를 읽는다. ⑨ 현재 노드 C의 데이터를 읽고, 오른쪽 서브트리 G로 이동한다. ⑩ 현재 노드 G의 왼쪽 단말노드인 공백노드를 읽고, 현재 노드 G의 데이터를 읽는다. ⑪ 현재 노드 G의 오른쪽 단말노드 K의 데이터를 읽는다.

33 수식 이진 트리에 대한 중위 순회 수식 이진 트리를 중위 순회하면, 수식에 대한 중위 표기식을 구할 수 있다.
[그림 8-17] 수식에 대한 이진 트리의 중위 순회 경로_A*B-C/D

34 후위 순회(postorder traversal)
수행 방법 ① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L ② 현재 노드 n의 오른쪽 서브트리로 이동한다. : R ③ 현재 노드 n을 방문하여 처리한다. : D 후위 순회 알고리즘 postorder(T)     if (T≠null) then {           postorder(T.left);                postorder(T.right);           visit T.data;      } end postorder()

35 후위 순회의 예 [그림 8-18] 이진 트리의 후위 순회 경로_H-D-I-J-E-B-F-K-G-C-A

36 후위 순회 과정 >> H-D-I-J-E-B-F-K-G-C-A
①루트 A에서 시작하여 노드 A의 왼쪽 서브트리 B로 이동한다. 현재 노드 B에서 왼쪽 서브트리 D로 이동. 현재 노드 D의 왼쪽 단말노드 H의 데이터를 읽는다. ② 현재 노드 D의 오른쪽 단말노드인 공백노드를 읽는다. 현재 노드 D의 데이터를 읽고, 이전 경로인 노드 B로 이동한다. ③ 현재 노드 B의 왼쪽 서브트리에 대한 순회가 끝났으므로 현재 노드 B의 오른쪽 서브트리 E로 이동한다. 현재 노드 E의 왼쪽 단말노드 I의 데이터를 읽는다. ④ 현재 노드 E의 오른쪽 단말노드 J의 데이터를 읽는다. ⑤ 이제 현재 노드 E의 데이터를 읽고, 이전 경로인 노드 B로 이동한다. ⑥ 현재 노드 B의 오른쪽 서브트리에 대한 순회가 끝났으므로, 현재 노드 B의 데이터를 읽고, 이전 경로인 노드 A로 이동한다. ⑦ 현재 노드 A의 왼쪽 서브트리에 대한 순회가 끝났으므로, 오른쪽 서브트리 C로 이동한다. 현재 노드 C의 왼쪽 단말노드 F의 데이터를 읽는다. ⑧ 현재 노드 C의 오른쪽 서브트리 G로 이동한다. 현재 노드 G의 왼쪽 단말노드인 공백노드를 읽고, 오른쪽 단말노드 K의 데이터를 읽는다.  ⑨ 이제 현재 노드 G의 데이터를 읽고, 이전 경로인 노드 C로 이동한다. ⑩ 현재 노드 C의 오른쪽 서브트리에 대한 순회가 끝났으므로, 현재 노드 C의 데이터를 읽고, 이전 경로인 노드 A로 이동한다. ⑪ 루트노드 A에 대한 오른쪽 서브트리에 대한 순회가 끝났으므로, 현재 노드 A의 데이터를 읽는다.

37 수식 이진 트리에 대한 후위 순회 수식 이진 트리를 후위 순회하면, 수식에 대한 후위 표기식을 구할 수 있다.
[그림 8-19] 수식에 대한 이진 트리의 후위 순회 경로_AB*CD/-

38 연결 자료구조로 표현된 이진 트리의 순회 방법 구현
연결 자료구조로 구현한 이진 트리에서의 순회 C 프로그램 수식 (A*B-C/D)에 대한 수식 이진 트리를 단순 연결 리스트로 구현 전위 순회, 중위 순회, 후위 순회를 차례로 수행하면서 순회경로를 출력하는 프로그램 실행 결과

39 폴더 계산 C 프로그램 컴퓨터의 폴더 구조가 이진 트리 구조인 경우에 이진 트리 순회를 응용하여 폴더의 용량을 계산하는 프로그램 폴더의 이진 트리 구조 [그림 8-20] 내 컴퓨터의 폴더 구조

40 이진 트리에서의 순회 방법을 응용한 프로그램 하위 폴더의 용량을 계산하여 상위 폴더의 용량과 더해서 전체 용량을 계산해야 하므로 후위 순회를 이용 프로그램 폴더의 전체 용량 = 프로그램 폴더(2M) + 하위 폴더의 용량{C프로그램 폴더(200M) + Java프로그램 폴더(100M)} = 302M C:\ 의 전체 용량 = C:\ 의 용량(0M) + 하위 폴더의 용량{프로그램 폴더의 전체 용량(302M) + 자료 폴더(15M)} = 317M 그림 폴더의 전체 용량 =  그림 폴더(68M) + 하위 폴더의 용량{사진 폴더(55M) + 동영상 폴더(120M)} = 243M D:\ 의 전체 용량 = D:\ 의 용량(10M) + 하위 폴더의 용량{음악 폴더의 용량(40M) + 그림 폴더의 전체 용량(243M)} = 293M 내 컴퓨터의 전체 용량 = 내 컴퓨터의 용량(0M) + 하위 폴더의 용량{C:\ 폴더의 전체 용량(317M) + D:\ 폴더의 전체 용량(293M)} = 610M

41 실행 결과

42 이진 탐색 트리(binary search tree)
이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조 이진 탐색 트리의 정의 ⑴ 모든 원소는 서로 다른 유일한 키를 갖는다. ⑵ 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다  작다. ⑶ 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다. ⑷ 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다. [그림 8-21] 이진 탐색 트리의 구조

43 이진 탐색 트리의 탐색 연산 탐색할 키값 x를 루트 노드의 키값과 비교한다.
루트에서 시작한다. 탐색할 키값 x를 루트 노드의 키값과 비교한다. (키 값 x = 루트노드의 키 값)인 경우 : 원하는 원소를 찾았으므로 탐색연산 성공 (키 값 x < 루트노드의 키 값)인 경우 : 루트노드의 왼쪽 서브트리에 대해서 탐색연산 수행 (키 값 x > 루트노드의 키 값)인 경우 : 루트노드의 오른쪽 서브트리에 대해서 탐색연산 수행 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.

44 탐색 연산 알고리즘 searchBST(bsT, x) p ← bsT; if (p=null) then return null;
        if (x = p.key) then             return p;         if (x < p.key) then             return searchBST(p.left, x);         else return searchBST(p.right, x); end searchBST()

45 탐색 연산 예) 원소 11 탐색하기 ① 찾는 키 값 11을 루트노드의 키 값 8과 비교
(찾는 키 값 11 > 노드의 키 값 8) 이므로 오른쪽 서브트리를 탐색 ② (찾는 키 값 11 > 노드의 키 값 10) 이므로, 다시 오른쪽 서브트리를 탐색 ③ (찾는 키 값 11 < 노드의 키 값 14) 이므로, 왼쪽 서브트리를 탐색 ④ (찾는 키 값 11 = 노드의 키 값 11) 이므로, 탐색 성공! (연산 종료) [그림 8-22] 이진 탐색 트리에서의 탐색 과정

46 이진 탐색 트리의 삽입 연산 탐색 연산을 수행 탐색 실패한 위치에 원소를 삽입한다.
삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다. 탐색에서 탐색 실패가 결정되는 위치가 삽입 원소의 자리가 된다. 탐색 실패한 위치에 원소를 삽입한다.

47 이진 탐색 트리에서의 삽입 연산 알고리즘 insertBST(bsT, x) p ← bsT; while (p≠null) do {
                if (x = p.key) then return;                 q ← p;                 if (x < p.key) then  p ← p.left;                 else p ← p.right;         }         new ← getNode();         new.key ← x;         new.left ← null;         new.right ← null;         if (bsT = null) then bsT←new;         else if (x < q.key) then     q.left ← new;              else      q.right ← new;         return; end insertBST() 삽입할 자리 탐색 삽입할 노드 만들기 탐색한 자리에 노드연결

48 이진 탐색 트리에서의 삽입 연산 예) 원소 4 삽입하기
① 찾는 키 값 4를 루트노드의 키 값 8과 비교하여, (찾는 키 값 4 < 노드의 키 값 8) 이므로, 왼쪽 서브트리를 탐색한다. ② (찾는 키 값 4 > 노드의 키 값 3) 이므로, 오른쪽 서브트리를 탐색한다. ③ (찾는 키 값 4 < 노드의 키 값 5) 이므로, 왼쪽 서브트리를 탐색해야하는데 왼쪽 자식노드가 없으므로 탐색 실패! 이때, 탐색 실패가 결정된 위치 즉, 왼쪽 자식노드의 위치가 삽입할 자리가 된다. ④ 탐색작업으로 찾은 자리 즉, 노드 5의 왼쪽 자식노드 자리에 노드 4를 삽입한다.

49

50 단순 연결 리스트로 표현한 이진트리에서의 원소 4 삽입하기
[그림 8-23] 이진 탐색 트리에 원소 4를 삽입하는 과정

51 이진 탐색 트리의 삭제 연산 탐색 연산을 수행 탐색하여 찾은 노드를 삭제한다.
삭제할 노드의 위치를 알아야하므로 트리를 탐색한다. 탐색하여 찾은 노드를 삭제한다. 삭제 노드의 경우 삭제할 노드가 단말노드인 경우 : 차수가 0인 경우 삭제할 노드가 하나의 자식노드를 가진 경우 : 차수가 1인 경우 삭제할 노드가 두개의 자식노드를 가진 경우 : 차수가 2인 경우 노드의 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리(이진 탐색 트리의 재구성 작업)가 필요하다.

52 단말 노드의 삭제 연산 노드 4를 삭제하는 경우

53 노드 4를 삭제하는 경우에 대한 단순 연결 리스트 표현
노드를 삭제하고, 삭제한 노드의 부모 노드의 링크 필드에 null 설정 [그림 8-24] 이진 탐색 트리에서 단말 노드 4를 삭제하는 경우

54 자식 노드가 하나인 노드, 즉 차수가 1인 노드의 삭제 연산
노드를 삭제하면, 자식 노드는 트리에서 연결이 끊어져서 고아가 된다. 후속 처리 : 이진 탐색 트리의 재구성 삭제한 부모 노드의 자리를 자식 노드에게 물려준다. 예) 노드 10을 삭제하는 경우

55 노드 10을 삭제하는 경우에 대한 단순 연결 리스트 표현
[그림 8-25] 이진 탐색 트리에서 자식 노드가 하나인 노드 10을 삭제하는 경우

56 자식 노드가 둘인 노드, 즉 차수가 2인 노드의 삭제 연산
노드를 삭제하면, 자식 노드들은 트리에서 연결이 끊어져서 고아가 된다. 후속 처리 : 이진 탐색 트리의 재구성 삭제한 노드의 자리를 자손 노드들 중에서 선택한 후계자에게 물려준다. 후계자 선택 방법 방법1) 왼쪽 서브트리에서 가장 큰 자손 노드 선택 왼쪽 서브트리의 오른쪽 링크를 따라 계속 이동하여 오른쪽 링크 필드가 NULL인 노드 즉, 가장 오른쪽에 있는 노드가 후계자가 된다. 방법2) 오른쪽 서브트리에서 가장 작은 자손 노드 선택 오른쪽 서브트리에서 왼쪽 링크를 따라 계속 이동하여 왼쪽 링크 필드가 NULL인 노드 즉, 가장 왼쪽에 있는 노드가 후계자가 된다.

57 삭제한 노드의 자리를 물려받을 수 있는 후계자 노드
[그림 8-26] 삭제할 노드의 자리를 물려받을 수 있는 자손 노드

58 예) 노드 8을 삭제하는 경우 [그림 8-27] 이진 탐색 트리에서 자식 노드가 둘인 노드 8을 삭제하는 경우

59 노드 5를 후계자로 선택한 경우 노드 10을 후계자로 선택한 경우
① 후계자 노드 5를 원래 자리에서 삭제하여, 삭제 노드 8의 자리를 물려준다. ② 후계자 노드 5의 원래 자리는 자식 노드 4에게 물려주어 이진 탐색 트리를 재구성한다. 자식 노드가 하나인 노드 삭제연산의 후속처리 수행  노드 10을 후계자로 선택한 경우 ① 후계자 노드 10을 원래 자리에서 삭제하여, 삭제 노드 8의 자리를 물려준다. ② 후계자 노드 10의 원래 자리는 자식 노드 14에게 물려줘 이진 탐색 트리를 재구성한다.

60 이진 탐색 트리에서의 삭제 연산 알고리즘 deleteBST(bsT, x) p ← 삭제할 노드;
        parent ← 삭제할 노드의 부모 노드;               if (p = null) then return;         if (p.left = null and p.right = null) then { // (1) 단말노드의 삭제             if (parent.left = p) then parent.left ← null;             else parent.right ← null;         }         else if (p.left = null or p.right = null) then { // (2) 차수가 1인 노드의 삭제                 if (p.left ≠ null) then { // 왼쪽자식노드를 가진 경우                     if (parent.left = p) then parent.left ← p.left;                     else parent.right ← p.left;                 }                 else { // 오른쪽자식노드를 가진 경우                     if (parent.left = p) then parent.left ← p.right;                     else parent.right ← p.right; }         else if (p.left ≠ null and p.right ≠ null) then { // (3) 차수가 2인 노드의 삭제                 q ← maxNode(p.left);                 p.key ← q.key;                 deleteBST(p.left, p.key);         } end deleteBST()

61 연결 자료구조를 이용한 이진 탐색의 C 프로그램
이진 탐색 트리를 단순 연결 리스트로 구현하고, 탐색 연산을 수행하는 프로그램 실행 결과

62 히프(heap) 최대 히프(max heap) 최소 히프(min heap)
완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 히프(max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 ≥ 자식 노드의 키 값} 루트 노드 : 키 값이 가장 큰 노드 최소 히프(min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 ≤ 자식 노드의 키 값} 루트 노드 : 키 값이 가장 작은 노드

63 히프의 예 히프가 아닌 이진 트리의 예 [그림 8-28] 히프의 예 [그림 8-29] 히프가 아닌 이진 트리의 예

64 히프의 추상 자료형 ADT Heap 데이터 : n개의 원소로 구성된 완전 이진 트리로서 각 노드의 키값은
            그의 자식 노드의 키값보다 크거나 같다.             (부모 노드의 키값 ≥ 자식 노드의 키값)    연산 :         heap∈Heap; item∈Element;         createHeap() ∷= create an empty heap;                 // 공백 히프의 생성 연산         isEmpty(heap) ∷= if (heap is empty) then return true;                          else return false;                 // 히프가 공백인지를 검사하는 연산         insertHeap(heap, item) ∷= insert item into heap;                 // 히프의 적당한 위치에 원소(item)를 삽입하는 연산         deleteHeap(heap) ∷= if (isEmpty(heap)) then return error;                              else {                                  item ← 히프에서  가장 큰 원소;                                  remove {히프에서 가장 큰 원소};                                  return  item;                              }                 // 히프에서 키값이 가장 큰 원소를 삭제하고 반환하는 연산 End Heap()

65 히프에서의 삽입 연산 1단계 : 완전 이진 트리를 유지하면서 노드를 확장하여, 삽입할 원소를 임시 저장
노드가 n개인 완전 이진 트리에서 다음 노드의 확장 자리는 n+1번의 노드가 된다. n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장한다. 2단계 : 만들어진 완전 이진 트리 내에서 삽입 원소의 제자리를 찾는다. 현재 위치에서 부모노드와 비교하여 크기 관계를 확인한다. {현재부모노드의 키 값 ≥ 삽입 원소의 키 값}의 관계가 성립하지 않으면, 현재부모노드의 원소와 삽입 원소의 자리를 서로 바꾼다.

66 히프에서의 삽입 연산 예1) 17을 삽입하는 경우 임시로 저장한 위치에서 부모노드와 크기를 비교하여 히프의 크기관계가 성립하므로, 현재 위치를 삽입 원소의 자리로 확정 [그림 8-30] 히프에서의 원소 삽입 예

67 히프에서의 삽입 연산 예2) 23을 삽입하는 경우 [그림 8-31] 히프에서의 원소 삽입 예

68 히프에서의 삽입 연산 알고리즘 ① 현재 히프의 크기를 하나 증가시켜서 노드 위치를 확장하고, 확장한 노드 번호가 현재의 삽입 위치 i가 된다. ② 삽입할 원소 item과 부모 노드 heap[i/2]를 비교하여 item이 부모 노드 보다 작거나 같으면  현재의 삽입 위치 i를 삽입 원소의 위치로 확정한다. ③ 만약 삽입할 원소item이 부모 노드 보다 크면, 부모 노드와 자식 노드의 자리를 바꾸어 최대 히프의 관계를 만들어야 하므로 부모 노드 heap[i/2]를 현재의 삽입 위치 heap[i]에 저장하고, ④ i/2를 삽입 위치 i로 하여, ②~④를 반복하면서 item을 삽입할 위치를 찾는다. ⑤ 찾은 위치에 삽입할 노드 item을 저장하면, 최대 히프의 재구성 작업이 완성되므로 삽입 연산을 종료한다. insertHeap(heap, item)                   if (n = heapSize) then heapFull();         n ← n+1;                                // ①         for (i ← n; ;) do {             if (i = 1) then exit;                            if (item ≤ heap[ i/2 ]) then exit;  // ②             heap[i] ← heap[ i/2 ];             // ③             i ←  i/2                         // ④        }         heap[i] ← item;                         // ⑤ end insertHeap()

69 히프에서의 삭제 연산 1단계 : 루트 노드의 원소를 삭제하여 반환한다.
히프에서는 루트 노드의 원소만을 삭제 할 수 있다. 1단계 : 루트 노드의 원소를 삭제하여 반환한다. 2단계 : 원소의 개수가 n-1개로 줄었으므로, 노드의 수가 n-1인 완전 이진 트리로 조정한다. 노드가 n개인 완전 이진 트리에서 노드 수 n-1개의 완전 이진 트리가 되기 위해서 마지막 노드, 즉 n번 노드를 삭제한다. 삭제된 n번 노드에 있던 원소는 비어있는 루트 노드에 임시 저장한다. 3단계 : 완전 이진 트리 내에서 임시 저장된 원소의 제자리를 찾는다. 현재 위치에서 자식 노드와 비교하여 크기 관계를 확인한다. {임시저장 원소의 키 값 ≥ 현재 자식 노드의 키 값 }의 관계가 성립하지 않으면, 현재 자식 노드의 원소와 임시저장 원소의 자리를 서로 바꾼다.

70 히프에서의 삭제 연산 예) [그림 8-32] 히프에서의 원소 삭제 예

71 히프에서의 삭제 연산 알고리즘 deleteHeap(heap) if (n = 0) then return error;
        item ← heap[1];                 // ① 루트노드의 원소를 item에 저장         temp ← heap[n];                // ② 마지막노드의 원소를 teml에 보관         n ← n-1;                        // ③ 히프의 노드개수 1감소         i ← 1;                         // ④ i: temp원소가 저장될 노드번호 저장변수         j ← 2; // j : i의 자식노드 번호         while (j ≤ n) do {             if (j < n) then                 if (heap[j] < heap[j+1]) then j ← j+1; // 키값이 큰 자식노드 찾기             if (temp ≥ heap[j]) then exit;     // ⑤ 자식노드가 작으면, 자리 확정             heap[i] ← heap[j];                  // ⑥ 자식노드가 크면, 자리 교환             i ← j;             j ← j*2;         }         heap[i] ← temp;                        // ⑦         return item;                             // ⑧ end deleteHeap()

72 ① 루트 노드 heap[1]을 item에 저장하고,
② 마지막 노드의 원소 heap[n]을 temp에 임시 저장한 후에, ③ 마지막 노드를 삭제한다. ④ 마지막 노드의 원소였던 temp의 임시 저장위치 i는 루트 노드 자리인 1번이 된다. ⑤ 현재 저장위치에서 자식 노드 heap[j]와 heap[j+1]이 있을 때, 둘 중에서 키 값이 큰 자식 노드의 키 값과 temp를 비교하여, temp가 크거나 같으면 현재 위치가 temp의 자리로 확정된다. ⑥ 만약 temp가 자식 노드보다 작으면, 자식 노드와 자리를 바꾸고 다시 ⑤~⑥을 반복하면서 temp의 자리를 찾는다. ⑦ 찾은 위치에 temp를 저장하여 최대 히프의 재구성 작업을 완성하고 ⑧ 루트 노드를 저장한 item을 반환하는 것으로 삭제 연산을 종료한다.

73 순차 자료구조를 이용한 히프의 구현 부모노드와 자식노드를 찾기 쉬운 1차원 배열의 순차 자료구조 이용
1차원 배열을 이용한 히프의 표현 예 [그림 8-33] 순차 자료구조를 이용한 히프의 표현 예

74 순차 자료구조를 이용한 히프 C 프로그램 공백 히프에 원소 10, 45, 19, 11, 96을 차례로 삽입하면서 최대 히프를 구성하고, 삭제연산을 수행하여 삭제된 원소를 출력하는 프로그램 최대 히프의 루트 노드는 히프에서 가장 큰 노드가 되므로, 원소 개수 만큼 삭제 연산을 수행하여 출력하면 큰 값부터 작은 값의 내림차순으로 출력되는 것을 확인할 수 있다. [그림 8-34] 원소 10, 45, 19, 11, 96을 삽입하여 완성한 최대 히프

75 순차 자료구조를 이용한 히프 C 프로그램 실행 결과