5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경 ptr right_child = NULL 일경우, ptr right_child 를 ptr 의 inorder successor 를가리키도록변경 5 장. 트리 (Page 36)
노드의구조 struct thread_tree { short int left_thread; // true or false struct thread_tree *left_child; // left_thread = true: thread // left_thread = false: left child char data; struct thread_tree *right_child; // right_thread에따라결정 short int right_thread; // true or false }; root A thread child B C D E F G H I 5 장. 트리 (Page 37)
Threaded Binary Tree 의 Head Node Head Node 의역할 가장왼쪽노드의 inorder predecessor 가장오른쪽노드의 inorder successor An Empty Threaded Binary Tree left_thread left_child data right_child right_thread TRUE FALSE 5 장. 트리 (Page 38)
Threaded Binary Tree 의예 root f - f f A f f B f f C f f D f t E t t F t t G t t H t t I t f = FALSE t = TRUE 5 장. 트리 (Page 39)
Threaded Binary Tree 에서 Inorder Traversal ptr 이현재노드를가리킨다고가정 If ptr right_thread == TRUE Inorder successor of ptr = ptr right_child Otherwise ptr 의 right_child 로간다음, left_child 를따라계속내려간다. 언제까지? left_thread == TRUE 인노드를만날때까지 Program 5.10 & Program 5.11: Complexity = O(n) Exercise 4/5: preorder/postorder traversal with threads 5 장. 트리 (Page 40)
Program 5.10: 한노드의 inorder successor 발견 struct thread_tree *insucc(struct thread_tree *ptr) { /* Threaded binary tree 에서 ptr 이가리키는노드의 inorder successor 를 return */ struct thread_tree *temp = ptr right_child; } if (!ptr right_thread) // right_child 가 child pointer while (!temp left_thread) // 왼쪽끝까지가자 temp = temp left_child; return temp; 5 장. 트리 (Page 41)
Program 5.11: Inorder Traversal void tinorder (struct thread_tree *tree) { // Threaded binary tree 를 inorder traversal struct thread_tree *temp = tree; } for ( ; ; ) { temp = insucc(temp); if (temp == tree) break; printf("%3c", temp data); 5 장. 트리 (Page 42)
Threaded Binary Tree 에서노드추가 문제정의 새로운노드를 parent 노드의 right child 로추가 parent right_thread 값이 true/false 일경우고려 그림 5.24 와 Program 5.12 root root A A parent B parent B C D child C D child before after 그림 5.24: 첫번째경우 (parent right_thread == TRUE) 5 장. 트리 (Page 43)
그림 5.24: parent right_thread == FALSE root root A parent A parent B B child C D C X E F D child X E F before after 5 장. 트리 (Page 44)
Program 5.12: Parent 의오른쪽에추가 void insert_right(struct thread_tree *parent, struct thread_tree *child) { // Threaded binary tree 에서 parent 의오른쪽에 child 추가 struct thread_tree *temp; child right_child = parent right_child; // child의 child right_thread = parent right_thread; // 정보부터 child left_child = parent; // 변경 child left_thread = TRUE; // 하자. parent right_child = child; parent right_thread = FALSE; // child가존재하므로 thread는 false if (!child right_thread) { temp = insucc(child); // parent의원래 successor를찾아서 temp left_child = child; // 새로운 predecessor로변경 } } Exercise 3: Insert a new node as a left child of a parent? 5 장. 트리 (Page 45)
6. Heaps Heap 의정의 우선순위큐 (Priority Queues) Max Heap 에노드추가 Max Heap 에서노드삭제 5 장. 트리 (Page 46)
6.1 Heap 의정의 Max tree 와 max heap 의정의 Max tree: key value of a node key values of its children Max heap: Max tree 이면서 complete binary tree Min tree 와 min heap 의정의 Min tree: key value of a node key values of its children Min heap: Min tree 이면서 complete binary tree 5 장. 트리 (Page 47)
Max Heap 과 Min Heap 의예 14 9 30 [2] 12 [3] 7 [2] 6 [3] 3 [2] 25 10 8 [6] 6 [4] [5] [4] 5 Max Heap 2 10 11 [2] 7 [3] 4 [2] 20 [3] 83 [2] 21 10 8 [6] 6 [4] [5] [4] 50 Min Heap 5 장. 트리 (Page 48)
ADT 5.2: MaxHeap ADT ADT MaxHeap 객체 : 각노드의값이 children 의것들보다작지않도록조직된 n > 0 인노드들의 complete binary tree 함수 : for all heap MaxHeap, item Element, n, max_size integer MaxHeap Create(max_size) ::= 최대 max_size 만큼의노드를저장할수있는 empty heap 을생성 Boolean HeapFull(heap, n) ::= if (n == max_size) return TRUE else return FALSE MaxHeap Insert(heap, item, n) ::= if (!HeapFull(heap, n)) item 을 heap 에저장한후, heap return. else return error. Boolean HeapEmpty(heap, n) ::= if (n > 0) return FALSE else return TRUE Element Delete(heap, n) ::= if (!HeapEmpty(heap, n)) heap 에서가장큰값을갖는원소를삭제한후그값을 return. else return error 5 장. 트리 (Page 49)
6.2 우선순위큐 (Priority Queues) Priority queue의정의 우선순위의순서대로삭제되는큐 Priority Queue의구현방법비교 Representation Insertion Deletion Unordered array Θ(1) Θ(n) Unordered linked list Θ(1) Θ(n) Sorted array O(n) Θ(1) Sorted linked list O(n) Θ(1) Max heap O(log 2 n) O(log 2 n) 5 장. 트리 (Page 50)
6.3 Max Heap 에노드추가 Max heap 은배열로구현 ( 왜?) 배열의끝에새로운노드추가 추가된위치의 parent 부터 root 노드까지기존노드들의값과비교하면서 max heap 을재구성 C 언어를이용한자료구조선언 #define MAX_ELEMENTS 200 // maximum heap size+1 #define HEAP_FULL(n) (n == MAX_ELEMENTS-1) #define HEAP_EMPTY(n) (!n) typedef struct { int key; /* other fields */ } element; element heap[max_elements]; int n = 0; 그림 5.28 & Program 5.13: Complexity = O(log 2 n) 5 장. 트리 (Page 51)
그림 5.28: Max Heap 에삽입의예 20 20 [2] 15 [3] 2 [2] 15 [3] 2 [6] [4] 14 [5] 10 [4] 14 [5] 10 (a) heap before insertion (b) Initial location of new node 20 21 [2] 15 [3] 5 [2] 15 [3] 20 [6] [6] [4] 14 [5] 10 2 [4] 14 [5] 10 2 (c) Insert 5 into heap (a) (d) Insert 21 into heap (a) 5 장. 트리 (Page 52)
Program 5.13: insert_max_heap() void insert_max_heap(element item, int *n) { // 노드수가 *n 인 max heap 에 item 값을추가 int i; if (HEAP_FULL(*n)) { fprintf(stderr, "The heap is full. \ n"); exit(1); } i = ++(*n); while ((i!= 1) && (item.key > heap[i/2].key)) { } heap[i] = heap[i/2]; // parent의값을아래로이동 i /= 2; // 한레벨위로이동 } heap[i] = item; 5 장. 트리 (Page 53)