CHAP 8 트리(2)
2021. 6. 3
순천향대학교 컴퓨터공학과
목차
트리, 이진 트리의 개념
이진 트리 표현
이진 트리 순회
이진 트리의 성질
이진트리 응용: 수식 트리
트리 연산
스레드 이진트리
이진탐색트리2
이진트리 연산 (1)
트리에 포함된 노드의 개수는?get_node_count(T) {
}
이진트리 연산 (2)
트리에 포함된 잎노드의 개수는?4
get_leaf_count(T) {
}
이진트리 연산 (3)
트리의 높이는?get_height(T) {
}
스레드 이진트리
트리 순회시 순환 호출은 비효율적
이진 트리의 null 링크를 이용하면 순환 호 출 없이 트리 순회 가능
트리에 포함된 노드 개수가 n이면, 총 링크의 개수는?
null 링크의 개수는?
6
스레드 이진트리 (2)
Null 링크에 중위 순회시에 중위 후속자(inorder successor)를 저장시켜 두면 비순환 호출 트리 순회 가능 (여기서는 중위 순회 고 려)
이러한 트리를 스레드 이진트리(threaded binary tree)라 한다.right 링크가 중위 후속자를 가리킨다
스레드 이진트리 표현
링크가 자식을 가리키는지 스레드를 가리키 는지를 구분하는 것이 필요 => is_thread 필 드 추가8
typedef struct TreeNode { int data;
struct TreeNode *left, *right;
int
is_thread;
//오른쪽 링크가 스레드이면 TRUE } TreeNode;예제: 스레드 이진트리
다음 이진트리를 스레드 이진트리로 구성하 라.B
A
C
D E F G
H I
스레드 이진트리 중위 순회
10
thread_inorder(T) { p <- T;
while
(p->left != null) do // 왼쪽 끝으로 이동p <- p->left;
repeat do
visit(p); // p를 방문
p <- inorder_sucessor(p);
// 중위 후속자 방문
while
(p!= null);}
inorder_successor(T) { // T의 중위 후속자 반환
}
B
A
C
D E F G
H I
이진 탐색트리
이진트리 기반의 효율적 탐색을 위한 자료구조
정의 모든 원소의 키는 유일하다.
Key(왼쪽 서브트리상의 노드) < key (루트 노드)
Key(오른쪽 서브트리상의 노드) > key (루트 노드)
탐색 알고리듬 분석
탐색 키: key Key = key(root) => 탐색 성공
Key < key(root) =>
Key > key(root) =>
12
탐색 알고리듬
search(T, key)
{ // T: 트리, key: 탐색 키
// 탐색 성공시 해당 노드를, 실패시는 NULL을 반환
탐색 알고리듬: 반복적 버전
14
search(T, key)
{ // T: 트리, key: 탐색 키
// 탐색 성공시 해당 노드를, 실패시는 NULL을 반환
}
이진 탐색트리 방문
이진탐색트리의 노드들을 오름차순으로 방문 하고자 한다면?2
5
7
1 4 6 8
3 9
삽입 연산
먼저 이진탐색트리를 탐색하고, 실패이면 해 당 위치에 삽입 탐색 성공 => 반환
탐색 실패 => 탐색이 실패하는 위치에 새로운 노 드 삽입
16
삽입 연산 알고리즘
TreeNode * insert_node(TreeNode * root, int key) {
if (root == NULL) // 트리가 공백이면 새로운 노드를 생성하고 반환 return new_node(key);
// 그렇지 않으면 순환적으로 트리를 내려간다.
if (key < root->key)
root->left = insert_node(root->left, key);
else if (key > root->key)
root->right = insert_node(root->right, key);
return root; // 루트를 반환 }
예제
다음 순서로 자료가 이진탐색트리에 입력된 다고 가정하여 이진 탐색트리를 구성하라. 5, 3, 7, 2, 4, 6, 9, 1, 8, 10
18
삭제 연산
삭제 대상 노드의 자식 노드가 0, 1, 2개인 경우로 구분2
5
7
1 4 6 8
3 9
삭제 연산
삭제 대상 노드의 자식 노드가 없는 경우 부모노드의 해당 링크를 null로 만들고,
해당 노드를 삭제/반환
20
삭제 연산
삭제 대상 노드가 하나의 서브트리만을 갖고 있는 경우 삭제되는 노드의 자리에 서브 트리를 위치시킨다.
삭제 연산
삭제 대상 노드가 두 개의 서브트리를 갖는 경우 삭제 노드를 왼쪽 서브트리의 최대 노드로 대체 하거나 오른쪽 서브트리의 최소 노드로 대체
22
삭제 연산 알고리즘
TreeNode * delete_node(TreeNode * root, int key) {// 키를 포함한 노드 삭제 후 반환
if (root == NULL) return root;
if (key < root->key)
root->left = delete_node(root->left, key);
else if (key > root->key)
root->right = delete_node(root->right, key);
else { // 탐색 성공: 노드(root) 삭제
// 삭제 대상 노드(root)의 자식이 없거나 한 개, 또는 2개인 경우 고려
}
return root;
삭제 연산
24
TreeNode * delete_node(TreeNode * root, int key) {// 키를 포함한 노드 삭제 후 반환 if (root == NULL) return root;
if (key < root->key)
root->left = delete_node(root->left, key);
else if (key > root->key)
root->right = delete_node(root->right, key);
else { // 탐색 성공
// 삭제 대상 노드(root)의 자식이 없거나 한 개인 경우
if (root->left == NULL) { // 우측 서브 트리 반환 (자식 없는 경우 포함) TreeNode * temp = root->right;
free(root); // 해당 노드 삭제 return temp;
} else if (root->right == NULL) { // 좌측 서브트리 반환 TreeNode * temp = root->left;
free(root);
return temp;
}
// 세 번째 경우: 우측서브트리에서 가장 작은 값을 갖는 노드로 대체 TreeNode * temp = min_value_node(root->right);
// 우측 서브트리에서 가장 작은 값을 갖는 노드를 찾고,
root->key = temp->key; // 루트 노드 값을 가장 작은 값 노드 값으로 대체하고, root->right = delete_node(root->right, temp->key); // 해당 노드를 삭제
}
return root;
}
삭제 연산 알고리즘 (2)
TreeNode * min_value_node(TreeNode * node) {
TreeNode * current = node;
// 맨 왼쪽 단말 노드를 찾으러 내려감 while (current->left != NULL)
current = current->left;
return current;
}
예제
앞서 다음의 순서로 자료가 입력되어 이진 탐색트리가 구성되었다고 가정한다. 5, 3, 7, 2, 4, 6, 9, 1, 8, 10
위의 이진 탐색트리에 대해서 다음 노드를 순서대로 삭제하라. 1
7
5
26
이진 탐색트리 성능
탐색, 삽입, 삭제 알고리즘의 복잡도는? 최선의 경우
최악의 경우
이진탐색트리의 성능분석
이진 탐색 트리에서의 탐색, 삽입, 삭제 연산 의 시간 복잡도는 트리의 높이를 h라고 했을 때 h에 비례한다Next (데이터 구조2)
8장 우선순위 큐 (히프 정렬)
10장 그래프
그래프 개념 / 탐색
최소비용신장트리
최단경로
9장 정렬
선택, 삽입, 버블, 셀 정렬
합병, 퀵, 히프, 기수 정렬
12장 탐색
선형, 이진탐색
균형이진탐색트리(AVL 트리)
