자료구조: CHAP 7(3) 트리 2017. 6. 1 순천향대학교 컴퓨터공학과 하 상 호.

Presentation on theme: "자료구조: CHAP 7(3) 트리 2017. 6. 1 순천향대학교 컴퓨터공학과 하 상 호."— Presentation transcript:

1 자료구조: CHAP 7(3) 트리 순천향대학교 컴퓨터공학과 하 상 호

2 목차 트리, 이진 트리의 개념 이진 트리 표현 이진 트리 순회 이진 트리의 성질 트리 연산 이진트리 응용: 수식 트리
스레드 이진트리 이진탐색트리

3 이진 탐색트리 이진트리 기반의 효율적 탐색을 위한 자료구조 정의 모든 원소의 키는 유일하다.
Key(왼쪽 서브트리상의 노드) < key (루트 노드) Key(오른쪽 서브트리상의 노드) > key (루트 노드)

4 탐색 알고리듬 생각(key: 탐색 키) Key = key(root) => 탐색 성공
알고리즘 복잡도는? search(T, key) { }

5 이진 탐색트리 이진탐색트리의 노드들을 오름차순으로 방문하고자 한다면? 2 5 7 1 4 6 8 3 9

6 삽입 연산 먼저, 탐색 키에 대해서 이진탐색트리를 탐색 탐색 성공 => 반환
탐색 실패 => 탐색이 실패하는 위치에 새로운 노드 삽입

7 예제 다음 순서로 자료가 입력되었다고 가정하여 이진 탐색트리를 구성하라. 5, 3, 7, 2, 4, 6, 9, 1, 8, 10

8 삽입 연산 insertBST(T, key) { p, q: node; p = T; // 먼저 탐색을 수행하고,
// 탐색이 성공이면 복귀하고, // 탐색이 실패하면, 노드를 생성하여 적절한 위치에 삽입 // (T가 공백인 경우 고려) }

9 삽입 연산 insertBST(T, key) p, q: node; p = T; while p != null do // 탐색 수행
if (p.key = key) then // 탐색 성공 return ; end if q = p; // 부모 노드 설정 if (p.key > key) then // 다음 수준 노드에 대해서 탐색 p = p.left; else p = p.right; repeat // 탐색이 실패한 경우 End insertBST

10 삭제 연산 삭제 대상 노드의 자식 노드가 0, 1, 2개인 경우로 구분 2 5 7 1 4 6 8 3 9

11 삭제 연산 삭제 대상 노드의 자식 노드가 없는 경우 부모노드의 해당 링크를 null로 만들고, 해당 노드를 삭제/반환

12 삭제 연산 삭제 대상 노드의 자식 노드이 한 개인 경우 삭제되는 노드의 자리에 자식 노드를 위치시킨다.

13 삭제 연산 삭제 대상 노드의 자식 노드이 2개인 경우 삭제 노드를 왼쪽 서브트리의 최대 노드로 대체하거나
오른쪽 서브트리의 최소 노드로 대체한다.

14 예제 다음 순서로 자료가 입력되었다고 가정하여 이진 탐색트리를 구성하라.
5, 3, 7, 2, 4, 6, 9, 1, 8, 10 위에서 구성한 트리에 대해서 다음 노드를 순서대로 삭제하라. 1 7 5

15 삭제 연산 deleteBST(T, key) { p, q: node; p = T; // 먼저 탐색을 수행하고,
// 탐색이 실패이면 복귀하고, // 탐색이 성공이면, 해당 노드 p를 삭제: p의 차수가 0, 1, 2인 경우 고려 }

16 삭제 연산 deleteBST(T, key) { p = T; while (p != null and p.key != key) { // 삭제 대상 노드 탐색 parent = p; if (key < p.key) then p <- p.left; else p <- p.right; } If (p = null) then return; // 탐색 실패 case { p.left = null and p.right = null: // p가 잎노드인 경우 p.left = null or p.right = null: // p의 차수가 1인 경우 p.left != nul and p.right != null: //p의 차수가 2인 경우 free(p) ; // 삭제 대상 노드 반환

17 삭제 연산 deleteBST(T, key) { // … case { p.left = null and p.right = null: // p가 잎노드인 경우 // 고려사항: p가 parent의 left, right에 위치하는지? p.left = null or p.right = null: // p의 차수가 1인 경우 // 고려사항: p의 left, right가 null인지? // p가 parent의 left, right에 위치하는지? //… } free(p);

18 삭제 연산 삭제 대상 노드 p의 차수가 1인 경우 (q는 p의 부모 노드) 다음 4가지 경우 고려 q q p p q q q p
q.left <- p.left q q q p p p q.left <- p.right q.right <- p.left q.right <- p.right

19 삭제 연산 deleteBST(T, key) { // … case { //… p.left != nul and p.right != null: //p의 차수가 2인 경우 // 고려사항: 오른쪽 서브트리에서 가장 작은 노드(후속자) 탐색 // 후속자의 오른쪽 서브트리를 후속자 부모에 연결 } free(p);

20 삭제 연산 삭제 대상 노드 p의 차수가 2인 경우 (p의 우측 서브 트리에서 가장 작은 키 값을 갖는 노드 탐색)
다음 2가지 경우 고려 p p p succParent succParent p succ succ k … succParent … succParent succ succ k succParent.right = succ succParent.left = succ succParent.left <- succ.right p.Key <- succ.key free(succ) succParent.right <- succ.right p.Key <- succ.key free(succ)

21 삭제 연산 deleteBST(T, key) { // … case { //… p.left != nul and p.right != null: //p의 차수가 2인 경우 // 고려사항: 오른쪽 서브트리에서 가장 작은 노드(후속자) 탐색 // 후속자의 오른쪽 서브트리를 후속자 부모에 연결 } // end case free(p); } succParent <- p; succ <- p.right; while (succ.left != null) { // 우측 서브트리에서 최소값 노드 탐색 succParent <- succ; succ <- succ.left; } // 후보자의 자식노드(우측 서브트리) 존재 경우 고려 if (succParent.left = succ) then succParent.left <- succ.right; else // p == succParent 인경우 succParent.right <- succ.right; p.key <- succ.key; // 삭제 대상 노드를 후보자로 대체 p <- succ; // 삭제 대상 노드 삭제

22 삭제 연산 다음 트리에서 5를 삭제하라. 5 3 9 2 4 7 10

23 삭제 연산 다음 트리에서 5를 삭제하라. 5 3 9 2 4 7 10 8

24 이진 탐색트리 성능 탐색, 삽입, 삭제 알고리즘의 복잡도는?

25 예제 다음 순서로 자료가 입력되었다고 가정하여 이진 탐색트리 T를 구성하라.
10, 7, 5, 15, 9, 2, 11, 3, 18, 13, 12, 16, 17 위에서 구성된 T를 다음의 순서로 노드를 삭제하라. 각 삭제 후의 트리를 보여라. 5 18 15

26 문제 다음에서 이진 탐색 트리에 대한 삽입, 삭제 연산을 수행하라.
1~100 범위의 난수 30개를 생성하여 순서대로 이진 탐색 트리 T에 삽입하라. 단, 첫번째 난수는 40~60의 범위에서 발생시켜라. 여러분은 구성된 이진 트리를 그려서 확인하라. 1)에서 구성된 이진 탐색 트리 T에서 노드에 포함된 값들을 정렬된 순서대로 배열 a에 저장하고 출력하라. 2)에서 구성된 배열 a의 인덱스 범위(0~29)에 대한 난수를 20개 발생시켜서 1)에서 구성된 이진 탐색트리에 대해서 탐색하라. 즉, 난수가 3이면 a[3]의 값을 T에 대해서 탐색한다. T의 탐색에 대한 평균 노드 탐색 회수를 구하고, T의 트리 높이와 비교하라. 2)에서 구성된 배열 인덱스 범위(0~29)에 대한 난수를 20개 발생시켜서 순서대로 해당 값을 갖는 노드를 1)에서 구성된 이진 탐색트리 T로부터 삭제하라. 노드의 각 삭제 후 결과 이진 탐색트리를 그려서 확인하라.

27 Next (알고리즘, 2017/2학기) 7장 트리 (이진탐색트리) 8장 우선순위 큐 (히프 정렬) 10장 그래프 9장 정렬
그래프 개념 / 탐색 최소비용신장트리 최단경로 9장 정렬 선택, 삽입, 버블, 셀 정렬 합병, 퀵, 히프, 기수 정렬 12장 탐색 균형이진탐색트리(AVL 트리) 11장 해싱