자료구조 프로그래밍 Lab06) 이항 힙 만들기 (Binomial Heap)
문제
해결
이항 힙은 다음의 과정을 통해 삽입과 삭제가 이루어진다.
이항 힙은 이항 트리들의 모임이다.( 2의 n승 값의 노드 수를 지닌 트리)
이항 힙은 양방향 형제(lsb, rsb)와 자식노드(child), 계층(degree), 값(data)로 이루어진 tree의 집합이다.
삽입
0) 새로운 temp를 삽입하면 우선순위를 비교해 기존의 minHeap에서 가르키고 있는 min pointer 의 바로 lsb(왼쪽 형제)에 값을 둔다
1) temp node의 우선순위가 더 높으면 min이 가르키고 있는 nodePointer를 temp로 옮긴다
2) 병합 과정을 전개(do while) - 최소 한번은 실행, 새로운 데이터와 병합 과정 진행해야함.
2-1) cur라는 node에 가장 루트 노드들의 가장 왼쪽 값을 가르키게 한다
2-2) degree가 같은 트리들이 있는지 체크
2-3) degree가 같은 트리들은 병합을 하는데 이 때, 우선순위를 고려한다, 새로운 값인 temp가 높은지, 탐색 중인 cur가 높은지
2-4) 이 때 우선순위가 높은 tree의 자식 노드가 있는지 체크하는데 없으면 우선순위 low 트리가 우선순위 high 트리의 자식 노드로 넣고 degree 증가 한다.
2-4) 자식 노드가 있다면 우선 순위 low tree는 우선순위 high tree의 맨 왼쪽 첫번 째 자식 노드가 되고 low tree의 rsb에는 원래의 high tree의 자식노드를 연결해준다
2-5) 최소 값이 바뀌었다면 minHeap이 가르키고 있는 treePointer를 바꿔준다
3) 병합할 트리들이 더 있는 지 체크한다
3-1) 맨 왼쪽 루트 노드를 가져온다
3-2) 오른쪽으로 가면서 degree가 같은 것 이 있다면 degreeCheck에 true을 줘서 2번 병합과정을 재시작 하도록 한다.
-----------------------------------------------------------------------------------------------------------------------------------------------------
* 병합과정에서 현재 min이 있는 level에 lsb에다가 new 값을 준다
(min 의 lsb 있을경우 / 아닐경우)
* 병합 check
min이 있는 level의 가장 왼쪽 lsb로 간다(cur)
cur으로 rsb 한번씩 가면서 temp랑 같은 degree가 있는 sb이 있는지 체크
있다면 병합(우선순위 비교, 누가 밑으로 갈건지)
병합 시에는 무조건 child로 보내고 기존의 child를 rsb로 삼기
병합 후에는 new node의 기준을 다시 정립(만약 cur가 root가 되면 cur를 new node로 기준)
* 병합 후에도 new랑 degree가 같아서 다시 병합할 것이 있는지 체크 후 다시 있다면 병합 check 함수 한번 더 돌기(do while)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 | typedef struct node * nodePointer; typedef struct node { int data; int degree; // 자식 개수 nodePointer child; // 자식 노드 nodePointer lsb; // left 형제 노드 nodePointer rsb; // right 형제 노드 }node; nodePointer min = NULL; nodePointer temp = NULL; // 삽입함수 void insertHeap(nodePointer temp) { int degreeCheck; nodePointer cur; // 처음 Tree는 Min if (min == NULL) { min = temp; return; } //만약에 min의 lsb가 NULL 일 경우 if (min->lsb == NULL) { min->lsb = temp; //min lsb에 값 추가 temp->rsb = min; } //min의 왼쪽의 노드가 존재할 경우 else { temp->lsb = min->lsb; temp->rsb = min; min->lsb->rsb = temp; min->lsb = temp; } // data 비교후 값 바꾸기 (새로운 값이 min보다 작을 경우) if (min->data > temp->data) { min = temp; } // do while로 체크하기(후검사) do { // degree Check degreeCheck = 0; cur = min; // lsb 부터 체크 while (1) { // NULL이면 종료 if (cur->lsb == NULL) break; cur = cur->lsb; } // 현재 노드에서 rsb로 가며 체크 while (cur) { // temp와 같을 경우 if (cur == temp) { cur = cur->rsb; continue; } // degree가 같을 경우 병합하기 if (temp->degree == cur->degree ) { // CASE 1. 새로운 데이터가 우선순위가 높을 경우 if (cur->data > temp->data) { // temp 밑에 들어감 //병합하기 전에 병합될 자식노드 관계 처리하기 if (temp->child) { // 자식 이 있으면 if (cur->lsb != NULL && cur->rsb != NULL) { // 위치 재조정하기 cur->rsb->lsb = cur->lsb; cur->lsb->rsb = cur->rsb; cur->lsb = NULL; cur->rsb = NULL; } // 위치 재조정하기(rsb만 있을 경우) else if (cur->lsb == NULL && cur->rsb != NULL) { cur->rsb->lsb = NULL; cur->rsb = NULL; } // 위치 재조정하기(lsb만 있을 경우) else if (cur->lsb != NULL && cur->rsb == NULL) { cur->lsb->rsb = NULL; cur->lsb = NULL; } cur->lsb = NULL;//가장 왼쪽으로 들어간다. cur->rsb = temp->child; temp->child->lsb = cur; } // 자식이 없으면 else { // 위치 재조정하기(lsb rsb 다 있을 경우) if (cur->lsb != NULL && cur->rsb != NULL) { cur->lsb->rsb = cur->rsb; cur->rsb->lsb = cur->lsb; cur->lsb = NULL; cur->rsb = NULL; } // 위치 재조정하기 (rsb만 있을 경우) else if (cur->lsb == NULL && cur->rsb != NULL) { cur->rsb->lsb = NULL; cur->rsb = NULL; } // 위치 재조정하기 (lsb만 있을 경우) else if (cur->lsb != NULL && cur->rsb == NULL) { cur->lsb->rsb = NULL; cur->lsb = NULL; } } // 새로운 data 값 재조정하기 (병합 처리 후) temp->child = cur; temp->degree += 1;// 합쳐졌으므로 // 만약 최소값이 현재였으면 (cur가 temp가 되었으므로) if (min == cur) min = temp; } // CASE 2. CUR가 우선순위가 더 높을 경우 else { // 만약 현재 노드의 자식이 있을 경우 if (cur->child != NULL) { // 위치 재조정(rsb, lsb 둘 다 있을경우) if (temp->lsb != NULL && temp->rsb != NULL) { temp->lsb->rsb = temp->rsb; temp->rsb->lsb = temp->lsb; temp->lsb = NULL; temp->rsb = NULL; } // 위치 재조정(rsb만 있을 경우) else if (temp->lsb == NULL && temp->rsb != NULL) { temp->rsb->lsb = NULL; temp->rsb = NULL; } // 위치 재조정(lsb만 있을 경우) else if (temp->lsb != NULL && temp->rsb == NULL) { temp->lsb->rsb = NULL; temp->lsb = NULL; } // lsb rsb 처리하기 temp->lsb = NULL; temp->rsb = cur->child; cur->child->lsb = temp; } // 그외 else { // 새로운 데이터 lsb, rsb 둘 다 있을경우 if (temp->lsb != NULL && temp->rsb != NULL) { temp->lsb->rsb = temp->rsb; temp->rsb->lsb = temp->lsb; temp->lsb = NULL; temp->rsb = NULL; } // rsb만 있을 경우 else if (temp->lsb == NULL && temp->rsb != NULL) { temp->rsb->lsb = NULL; temp->rsb = NULL; } // lsb만 있을 경우 else if (temp->lsb != NULL && temp->rsb == NULL) { temp->lsb->rsb = NULL; temp->lsb = NULL; } } // 합쳐진 후에 degree 1 추가 cur->child = temp; // 병합 cur->degree += 1; // 최소값이 temp였으면 최소 값 변경 되었으므로 재조정 if (min == temp) min = cur; // 한번 더 탐색을 위해 현재 값 재조정 temp = cur; } // 병합 후 다시 탐색 break; } // 오른쪽 형제로 탐색 cur = cur->rsb; } // degree 재검사 cur = min; // 왼쪽부터 검사 while (1) { if (cur->lsb == NULL) break; cur = cur->lsb; } // NULL이 아닐 동안 while (cur) { //같으면 if (cur == temp) { cur = cur->rsb; // 오른쪽 형제 주고 계속 continue; } // degree 같을 경우 else if (cur->degree == temp->degree) { degreeCheck = 1; // 같은 것 찾음 다시 병합 cur = cur->rsb; } // 그 외 else cur = cur->rsb; } } while (degreeCheck); // 같은 것 있을 동안 재검사 } | cs |
삭제
0) 삭제는 minHeap이 가르키고 있는 최소값을 pop하는 과정이다
CASE 1.
1) 삭제할 min의 자식 노드가 있을 경우
1-1) scrsb와 cur에다가 min의 자식노드를 가르키게 한다
1-2) 그리고 min이 연결된 형제들의 위치를 재조정한다(min 삭제), 이 때 min의 자식노드들에다가 min의 형제노드들을 연결한다
1-3) 병합과정을 진행한다(min의 자식노드들이 가르키고 있는 것들을 병합)
1-4) 루트 노드들의 가장 왼쪽으로 cur를 이동 시킴
1-5) 그리고 가장 작은 값을 찾아서 min이 가르키는 값 변경
1-6) 병합 과정 전개
CASE 2.
2) 삭제할 min의 자식 노드가 없을 경우
2-1) min 노드의 양 옆 연결 상태에 따라 min을 빼준다(lsb rsb 둘다 있거나, 둘 중 한개만 있거나)
2-2) cur node에다가 삭제할 min의 형제 값을 가져온다(병합 과정을 위해)
2-3) 루트 노드들의 가장 왼쪽으로 cur를 이동 시킴
2-4) 그리고 가장 작은 값을 찾아서 min이 가르키는 값 변경
2-5) 그리고 병합과정 전개
3) 병합 과정을 전개(do while) - 최소 한번은 실행, 새로운 데이터와 병합 과정 진행해야함.
3-1) cur라는 node에 가장 루트 노드들의 가장 왼쪽 값을 가르키게 한다
3-2) degree가 같은 트리들이 있는지 체크
3-3) degree가 같은 트리들은 병합을 하는데 이 때, 우선순위를 고려한다, 새로운 값인 temp가 높은지, 탐색 중인 cur가 높은지
3-4) 이 때 우선순위가 높은 tree의 자식 노드가 있는지 체크하는데 없으면 우선순위 low 트리가 우선순위 high 트리의 자식 노드로 넣고 degree 증가 한다.
3-4) 자식 노드가 있다면 우선 순위 low tree는 우선순위 high tree의 맨 왼쪽 첫번 째 자식 노드가 되고 low tree의 rsb에는 원래의 high tree의 자식노드를 연결해준다
3-5) 최소 값이 바뀌었다면 minHeap이 가르키고 있는 treePointer를 바꿔준다
4) 병합할 트리들이 더 있는 지 체크한다
4-1) 맨 왼쪽 루트 노드를 가져온다
4-2) 오른쪽으로 가면서 degree가 같은 것 이 있다면 degreeCheck에 true을 줘서 3번 병합과정을 재시작 하도록 한다.
-----------------------------------------------------------------------------------------------------------------------------------------------------
* min 삭제 후 자식 노드가 없을 경우 min의 형제 노드 관계 처리
min 삭제 후 자식 노드가 있을 경우 자식노드의 가장 rsb를 가져와서
min의 형제들과 연결(어디 연결할지는 위치 보고)
* 병합 과정 전 변수 재조정
min의 level에서 가장 작은 값 찾아서 min 할당
새로온 노드 new에는 갈라진 자식노드의 lsb를 할당
* 병합 check
<병합체크 전 삭제노드는 추가 된 노드가 min의 자식노드 들이므로 new는 자식노드들의 lsb~rsb가 된다, 따라서 while 또는 for문으로묶어서 level 전체를 병합 대상으로 체크한다>
min이 있는 level의 가장 왼쪽 lsb로 간다(cur)
cur으로 rsb 한번씩 가면서 temp랑 같은 degree가 있는 sb이 있는지 체크
있다면 병합(우선순위 비교, 누가 밑으로 갈건지)
병합 시에는 무조건 child로 보내고 기존의 child를 rsb로 삼기
병합 후에는 new node의 기준을 다시 정립(만약 cur가 root가 되면 cur를 new node로 기준)
* 병합 후에도 new랑 degree가 같아서 다시 병합할 것이 있는지 체크 후 다시 있다면 병합 check 함수 한번 더 돌기(do while)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 | typedef struct node * nodePointer; typedef struct node { int data; int degree; // 자식 개수 nodePointer child; // 자식 노드 nodePointer lsb; // left 형제 노드 nodePointer rsb; // right 형제 노드 }node; nodePointer min = NULL; nodePointer temp = NULL; // 삭제 함수(최소값 pop) void popHeap() { nodePointer cur, scrsb, minTemp; int degreeCheck; // 현재 노드의 최소 노드의 자식 노드 주기 cur = min->child; // 자식노드 없을 경우 if (cur == NULL) { // 왼쪽 형제 있을 경우 if (min->lsb) cur = min->lsb; // 현재 노드에 최소의 lsb 주기 // 오른쪽 형제 있을 경우 else if (min->rsb) cur = min->rsb;// 현재 노드에 최소의 rsb 주기 } // CASE 1. 자식 노드 있을 경우 if (min->child) { scrsb = min->child; // 최소노드 자식 노드 가져오기 // 자식노드의 rsb로 가서 체크(자식노드의 rsb NULL 일경우 까지 가기) while (scrsb->rsb) scrsb = scrsb->rsb; // 삭제할 노드의 rsb lsb가 다 없을 경우 if (min->lsb == NULL && min->rsb == NULL) { min = min->child; // 자식노드값 주면 끝 } // 삭제 노드의 rsb만 있을 경우 else if (min->lsb == NULL && min->rsb != NULL) { min->rsb->lsb = scrsb; // rsb 연결 scrsb->rsb = min->rsb; } // 삭제 노드의 lsb만 있을 경우 else if (min->lsb != NULL && min->rsb == NULL) { min->lsb->rsb = min->child; // lsb 연결 min->child->lsb = min->lsb; } // 그 외의 경우 둘 다 있을 경우 else { // 위치 재조정하기( 뛰어넘고 연결하기) 양방향 min->rsb->lsb = scrsb; scrsb->rsb = min->rsb; min->lsb->rsb = min->child; min->child->lsb = min->lsb; } } // CASE 2. 자식노드가 없을 경우 else { //삭제 노드의 rsb만 있을 경우 if (min->lsb == NULL && min->rsb != NULL) { min->rsb->lsb = NULL; } // 삭제 노드의 lsb만 있을 경우 else if (min->lsb != NULL && min->rsb == NULL) { min->lsb->rsb = NULL; } // 삭제 노드가 둘 다 있을 경우 else if (min->lsb != NULL && min->rsb != NULL) { min->rsb->lsb = min->lsb; min->lsb->rsb = min->rsb; } } // lsb 부터 체크 while (1) { // NULL check if (cur == NULL) break; // lsb 까지 체크 if (cur->lsb == NULL) break; // 이동 cur = cur->lsb; } // 삭제 후 min 노드 변경하기 minTemp = cur; // 위치 찾아가서 while (cur) { // 가장 작은 값 찾아내기 if (cur->data < minTemp->data) minTemp = cur; cur = cur->rsb; // 이동 } // 값 할당하기 min = minTemp; // 병합 과정 // do while 체크 do { // NULL 이면 종료 if (min == NULL) break; // degree 같은 것 있는지 check degreeCheck = 0; cur = min; // lsb 부터 체크하기 while (1) { // lsb NULL 일 경우 if (cur->lsb == NULL) break; cur = cur->lsb; } // 오른쪽으로 가면서 check while (cur) { // 같으면 if (cur == temp) { cur = cur->rsb; continue; } // 들어온 node와 degree 같을 경우 if (cur->degree == temp->degree) { // CASE 1. TEMP의 우선순위가 높을 경우 if (cur->data > temp->data) { // 자식노드 있으면 if (temp->child != NULL) { // 위치 재조정, 현재 노드의 lsb rsb 둘 다 있을 경우 if (cur->lsb != NULL && cur->rsb != NULL) { cur->lsb->rsb = cur->rsb; cur->rsb->lsb = cur->lsb; cur->lsb = NULL; cur->rsb = NULL; } // 위치 재조정, rsb만 있을 경우 else if (cur->lsb == NULL && cur->rsb != NULL) { cur->rsb->lsb = NULL; cur->rsb = NULL; } // 위치 재조정 lsb만 있을 경우 else if (cur->lsb != NULL && cur->rsb == NULL) { cur->lsb->rsb = NULL; cur->lsb = NULL; } // 왼쪽 NULL 값 처리 cur->lsb = NULL; cur->rsb = temp->child; temp->child->lsb = cur; } // 자식 노드 없을 경우 else { // 위치 재조정, 현재 노드의 lsb rsb 둘 다 있을 경우 if (cur->lsb != NULL && cur->rsb != NULL) { cur->lsb->rsb = cur->rsb; cur->rsb->lsb = cur->lsb; cur->lsb = NULL; cur->rsb = NULL; } // 위치 재조정, rsb만 있을 경우 else if (cur->lsb == NULL && cur->rsb != NULL) { cur->rsb->lsb = NULL; cur->rsb = NULL; } // 위치 재조정, lsb만 있을 경우 else if (cur->lsb != NULL && cur->rsb == NULL) { cur->lsb->rsb = NULL; cur->lsb = NULL; } } // temp의 child 로 연결 하기 temp->child = cur; temp->degree += 1;//degree 증가 // min 지정 값 바꾸기 if (min == cur) min = temp; } // CASE 2. CUR 의 우선순위 가 높을 경우 else { // 자식 노드 있을 경우 if (cur->child != NULL) { // 위치 재조정, 노드의 lsb rsb 둘 다 있을 경우 if (temp->lsb != NULL && temp->rsb != NULL) { temp->lsb->rsb = temp->rsb; temp->rsb->lsb = temp->lsb; temp->lsb = NULL; temp->rsb = NULL; } // 위치 재조정, 노드의 rsb만 있을 경우 else if (temp->lsb == NULL && temp->rsb != NULL) { temp->rsb->lsb = NULL; temp->rsb = NULL; } // 위치 재조정, lsb만 있을 경우 else if (temp->lsb != NULL && temp->rsb == NULL) { temp->lsb->rsb = NULL; temp->lsb = NULL; } // 값 조정 temp->lsb = NULL; temp->rsb = cur->child; cur->child->lsb = temp; } // 자식 노드 없을 경우 else { // 위치 재조정, 노드의 lsb rsb 둘 다 있을 경우 if (temp->lsb != NULL && temp->rsb != NULL) { temp->lsb->rsb = temp->rsb; temp->rsb->lsb = temp->lsb; temp->lsb = NULL; temp->rsb = NULL; } // 위치 재조정, 노드의 rsb만 있을 경우 else if (temp->lsb == NULL && temp->rsb != NULL) { temp->rsb->lsb = NULL; temp->rsb = NULL; } // 위치 재조정, 노드의 lsb만 있을 경우 else if (temp->lsb != NULL && temp->rsb == NULL) { temp->lsb->rsb = NULL; temp->lsb = NULL; } } // 합쳐주기 cur->child = temp; cur->degree += 1; // degree 증가 // 지정 값 바꿔주기 if (min == temp) min = cur; temp = cur;//다음 탐색 체크 } // 병합 후 재 체크 break; } // rsb로 가면서 탐색 cur = cur->rsb; } // degree 체크하기 cur = min; // 제일 왼쪽lsb 부터 체크하기 while (1) { // NULL 까지 가면 탈출 if (cur->lsb == NULL) break; // 왼쪽 이동 cur = cur->lsb; } // NULL이 아닐 동안 while (cur) { // 같을 경우 다음 rsb로 이동 if (cur == temp) { cur = cur->rsb; continue; } // 그 외 degree 같은 것 찾을 경우 else if (cur->degree == temp->degree) { degreeCheck = 1; cur = cur->rsb; } // 그외에는 rsb 로 이동 else cur = cur->rsb; } } while (degreeCheck); // degree 같은 것 있을 동안 확인 } | cs |
'Archived(CSE Programming) > 자료구조(C++)' 카테고리의 다른 글
| 자료구조 프로그래밍 Lab08) BTree (2-3 Tree) 만들기 (3) | 2018.11.26 |
|---|---|
| 자료구조 프로그래밍 Lab07) AVL Tree 만들기 (0) | 2018.11.18 |
| 자료구조 프로그래밍 Lab05) 최소 좌향 트리 만들기(Leftist Min Tree, Heap) (0) | 2018.11.03 |
| 자료구조 프로그래밍 Lab04) 그래프 모든 경로 찾기 C (두 vertex 사이) (0) | 2018.10.25 |
| 자료구조 프로그래밍 Lab03) 최소힙(Min Heap) 만들기! (2) | 2018.10.24 |
