자료구조: CHAP 7 이진 탐색 트리 2016. 9. 6 순천향대학교 컴퓨터공학과 하 상 호

목차 이진탐색트리

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

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

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

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

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

삽입 연산 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

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

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

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

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

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

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

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

삭제 연산 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) ; // 삭제 대상 노드 반환 탐색 삭제

삭제 연산 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에 위치하는지? // p의 차수가 2인 경우 } free(p);

삭제 연산 삭제 대상 노드 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

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

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

삭제 연산 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; // 삭제 대상 노드 삭제

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

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

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

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