Rev 2416 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
2416 | mencl | 1 | /* |
2 | * Copyright (c) 2007 Vojtech Mencl |
||
3 | * All rights reserved. |
||
4 | * |
||
5 | * Redistribution and use in source and binary forms, with or without |
||
6 | * modification, are permitted provided that the following conditions |
||
7 | * are met: |
||
8 | * |
||
9 | * - Redistributions of source code must retain the above copyright |
||
10 | * notice, this list of conditions and the following disclaimer. |
||
11 | * - Redistributions in binary form must reproduce the above copyright |
||
12 | * notice, this list of conditions and the following disclaimer in the |
||
13 | * documentation and/or other materials provided with the distribution. |
||
14 | * - The name of the author may not be used to endorse or promote products |
||
15 | * derived from this software without specific prior written permission. |
||
16 | * |
||
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
||
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
||
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
||
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
||
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
||
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
||
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
||
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
||
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
||
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
||
27 | */ |
||
28 | |||
29 | /** @addtogroup genericadt |
||
30 | * @{ |
||
31 | */ |
||
32 | |||
33 | /** |
||
34 | * @file |
||
35 | * @brief Extended AVL tree with relative keys implementation. |
||
36 | * |
||
37 | * This file implements Extended AVL tree with relative keys type and operations. |
||
38 | * |
||
39 | * Extended AVL tree with relative keys (ExtAvlrel tree) has the following properties: |
||
40 | * @li it is binary search tree with unique real keys |
||
41 | * @li right subtree of every node is Avl tree |
||
42 | * @li height of left subtree of every node is not greater then height of right subtree + 1 |
||
43 | * @li nodes with the same real keys are linked to the tree nodes of the same key, they are not tree nodes |
||
44 | * @li every node is part of doubly linked list with head |
||
45 | * @li nodes are connected in the list ascendentaly according to their real keys, node key is |
||
46 | * only difference between previous real node's key and its real node's key |
||
47 | * @li real key is either equal node key if node is leftmost node in tree or sum of all |
||
48 | * node keys with smaller real key |
||
49 | * |
||
50 | * Be careful of using this tree because node keys are not equal real keys (except leftmost node). |
||
51 | */ |
||
52 | |||
53 | #include <adt/extavlrel.h> |
||
54 | #include <debug.h> |
||
55 | #include <panic.h> |
||
56 | |||
57 | |||
58 | #define AVLTREE_LEFT 0 |
||
59 | #define AVLTREE_RIGHT 1 |
||
60 | |||
61 | |||
62 | /* Returns height of tree -1 */ |
||
2421 | mencl | 63 | #define extavlreltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height)) |
2416 | mencl | 64 | |
65 | /** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree. |
||
66 | * |
||
67 | * @param t ExtAVLrel tree. |
||
68 | * @param key Key to be searched. |
||
69 | * |
||
2421 | mencl | 70 | * @return Pointer to node or NULL if there is no such key. |
2416 | mencl | 71 | */ |
2421 | mencl | 72 | extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key) |
2416 | mencl | 73 | { |
74 | extavlreltree_node_t *cur; |
||
75 | uint64_t sum, s; |
||
76 | |||
77 | /* |
||
78 | * Find right subtree in way up to the root where can be node with given key. |
||
79 | * Root node is the last node in the way up, when we reach root, it means, |
||
80 | * that searched node belongs to the right subtree of root. |
||
81 | */ |
||
82 | sum = 0; |
||
83 | cur = t->head.next; |
||
84 | while (1) { |
||
85 | sum += cur->key + cur->rgt_sum; |
||
86 | if ((key <= sum) || (cur == t->root)) |
||
87 | break; |
||
88 | else |
||
89 | cur = cur->par; |
||
90 | } |
||
91 | |||
92 | /* |
||
93 | * Sorting for cycle. |
||
94 | * Search for key in choosen subtree. Searching start at cur node which we have found |
||
95 | * in previous step. It is common search algorithm for binary search tree. |
||
96 | */ |
||
97 | while (cur != NULL) { |
||
98 | s = sum - cur->rgt_sum; |
||
99 | if (key < s) { |
||
100 | /* |
||
101 | * Left subtree. Find max value in left subtree of cur. |
||
102 | */ |
||
103 | sum -= cur->key + cur->rgt_sum; |
||
104 | cur = cur->lft; |
||
105 | } else if (key > s) { |
||
106 | /* |
||
107 | * Right subtree. sum has still max value in the right subtree of cur. |
||
108 | */ |
||
109 | cur = cur->rgt; |
||
110 | } else { |
||
111 | /* |
||
112 | * Equal values. We have found node with given key. |
||
113 | */ |
||
114 | return cur; |
||
115 | } |
||
116 | } |
||
117 | return NULL; |
||
118 | } |
||
119 | |||
120 | |||
121 | /** Insert new node into ExtAVL tree. |
||
122 | * |
||
123 | * New node's key must be set. |
||
124 | * |
||
125 | * @param t ExtAVL tree structure. |
||
126 | * @param newnode New node to be inserted. |
||
127 | */ |
||
128 | void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode) |
||
129 | { |
||
130 | extavlreltree_node_t *cur; |
||
131 | extavlreltree_node_t *son; |
||
132 | extavlreltree_node_t *gpa; |
||
133 | extavlreltree_node_t *par; |
||
134 | uint64_t sum, s; |
||
135 | uint8_t dir; |
||
136 | /* |
||
137 | * Condition var - all rgt_sums in the way down to root must be repaired in condition |
||
138 | * that we came there from right and on the way from repaired node to new node we |
||
139 | * never turn to the left. Reparation is done in the reparation cycle. |
||
140 | */ |
||
141 | bool repair_rgt_sum; |
||
142 | |||
143 | ASSERT(t); |
||
144 | ASSERT(newnode); |
||
145 | |||
146 | /* |
||
147 | * Insert first node into empty tree. Key is left without change (according to definition). |
||
148 | */ |
||
149 | cur = t->head.next; |
||
150 | if (cur == &t->head) { |
||
151 | newnode->lft = NULL; |
||
152 | newnode->rgt = NULL; |
||
153 | newnode->lft_height = 0; |
||
154 | newnode->rgt_height = 0; |
||
155 | newnode->par = NULL; |
||
156 | newnode->next = &t->head; |
||
157 | newnode->prev = &t->head; |
||
158 | newnode->rgt_sum = 0; |
||
159 | |||
160 | t->head.prev = newnode; |
||
161 | t->head.next = newnode; |
||
162 | t->root = newnode; |
||
163 | return; |
||
164 | } |
||
165 | |||
166 | /* |
||
167 | * Find right subtree in way up to the root where newnode will be placed. |
||
168 | * Root node is the last node in the way up, when we reach root, it means, |
||
169 | * that newnode belongs to the right subtree of root. |
||
170 | * |
||
171 | * When max key of cur's right subtree is inserted, while cycle overjumps |
||
172 | * right node and stops. But in the next sorting for cycle is this situation |
||
173 | * solved (for cycle jumps back to the left child). |
||
174 | */ |
||
175 | sum = 0; |
||
176 | while (1) { |
||
177 | sum += cur->key + cur->rgt_sum; |
||
178 | if ((newnode->key <= sum) || (cur == t->root)) |
||
179 | break; |
||
180 | else |
||
181 | cur = cur->par; |
||
182 | } |
||
183 | |||
184 | |||
185 | /* |
||
186 | * Sorting for cycle. |
||
187 | * Find a place for newnode. Searching start at cur node which we have found |
||
188 | * in previous step. It is common search algorithm for binary search tree. |
||
189 | */ |
||
190 | for (;;) { |
||
191 | s = sum - cur->rgt_sum; |
||
192 | if (newnode->key < s) { |
||
193 | /* |
||
194 | * Left subtree. Find max value in left subtree of cur. |
||
195 | */ |
||
196 | sum -= cur->key + cur->rgt_sum; |
||
197 | |||
198 | if (!cur->lft) { |
||
199 | /* |
||
200 | * Insert new node to the left. |
||
201 | */ |
||
202 | cur->lft = newnode; |
||
203 | |||
204 | newnode->lft = NULL; |
||
205 | newnode->rgt = NULL; |
||
206 | newnode->lft_height = 0; |
||
207 | newnode->rgt_height = 0; |
||
208 | newnode->par = cur; |
||
209 | /* |
||
210 | * Insert newnode to list. |
||
211 | */ |
||
212 | newnode->next = cur; |
||
213 | newnode->prev = cur->prev; |
||
214 | cur->prev->next = newnode; |
||
215 | cur->prev = newnode; |
||
216 | |||
217 | newnode->key -= sum; |
||
218 | newnode->rgt_sum = 0; |
||
219 | /* |
||
220 | * Repair key of next value (next node always exists). newnode->key |
||
221 | * has been already set. Needn't check whether newnode->next is head |
||
222 | * beacause newnode is left child (next node is his father). |
||
223 | */ |
||
224 | newnode->next->key -= newnode->key; |
||
225 | |||
226 | repair_rgt_sum = false; |
||
227 | dir = AVLTREE_LEFT; |
||
228 | break; |
||
229 | } |
||
230 | cur = cur->lft; |
||
231 | } else if (newnode->key > s) { |
||
232 | /* |
||
233 | * Right subtree. sum has still max value in the right subtree of cur. |
||
234 | */ |
||
235 | |||
236 | if (!cur->rgt) { |
||
237 | cur->rgt = newnode; |
||
238 | |||
239 | newnode->lft = NULL; |
||
240 | newnode->rgt = NULL; |
||
241 | newnode->lft_height = 0; |
||
242 | newnode->rgt_height = 0; |
||
243 | newnode->par = cur; |
||
244 | |||
245 | /* |
||
246 | * Find last node in the chain with the same key as cur node. |
||
247 | */ |
||
248 | gpa = cur->next; |
||
249 | while (gpa != &t->head && gpa->key == 0) |
||
250 | gpa = gpa->next; |
||
251 | |||
252 | /* |
||
253 | * Insert new node to list. Right place in the list was found in |
||
254 | * previous cycle. |
||
255 | */ |
||
256 | newnode->prev = gpa->prev; |
||
257 | newnode->next = gpa; |
||
258 | gpa->prev->next = newnode; |
||
259 | gpa->prev = newnode; |
||
260 | |||
261 | newnode->key -= sum; |
||
262 | newnode->rgt_sum = 0; |
||
263 | /* |
||
264 | * Repair key of next value (next node always exists). newnode->key |
||
265 | * has been already set. |
||
266 | */ |
||
267 | if (newnode->next != &t->head) |
||
268 | newnode->next->key -= newnode->key; |
||
269 | /* |
||
270 | * All rgt_sums in the way down to root must be repaired in condition |
||
271 | * that we came there from right and on the way from node to new node we |
||
272 | * never turn left. |
||
273 | */ |
||
274 | repair_rgt_sum = true; |
||
275 | dir = AVLTREE_RIGHT; |
||
276 | break; |
||
277 | } |
||
278 | cur = cur->rgt; |
||
279 | |||
280 | } else { |
||
281 | /* |
||
282 | * Equal values. Give newnode to the last position of chain with the cur head and |
||
283 | * end insertion. |
||
284 | */ |
||
285 | gpa = cur->next; |
||
286 | while (gpa != &t->head && gpa->key == 0) |
||
287 | gpa = gpa->next; |
||
288 | /* |
||
289 | * Insert new node to list in right place. |
||
290 | */ |
||
291 | newnode->prev = gpa->prev; |
||
292 | newnode->next = gpa; |
||
293 | gpa->prev->next = newnode; |
||
294 | gpa->prev = newnode; |
||
295 | |||
296 | newnode->par = NULL; |
||
297 | newnode->lft = NULL; |
||
298 | newnode->rgt = NULL; |
||
299 | newnode->lft_height = 0; |
||
300 | newnode->rgt_height = 0; |
||
301 | |||
302 | /* |
||
303 | * Nodes in chains has key equal 0, because difference between previous node and them is 0. |
||
304 | */ |
||
305 | newnode->key = 0; |
||
306 | newnode->rgt_sum = 0; |
||
307 | return; |
||
308 | } |
||
309 | } |
||
310 | |||
311 | /* |
||
312 | * Balancing all nodes from newnode's parent down to root. |
||
313 | */ |
||
314 | cur = newnode->par; |
||
315 | while (true) { |
||
316 | if (dir == AVLTREE_LEFT) { |
||
317 | /* |
||
318 | * Insertion was made in the left subtree - repair left height, stop |
||
319 | * repairing rgt_sum and check balance of current node. |
||
320 | */ |
||
321 | cur->lft_height = extavlreltree_tree_height(cur->lft) + 1; |
||
322 | |||
323 | repair_rgt_sum = false; |
||
324 | |||
325 | if ((cur->rgt_height - cur->lft_height) <= -2) { |
||
326 | /* |
||
327 | * Balance was corrupted, must be repaired through LL or LR rotation. |
||
328 | */ |
||
329 | par = cur->par; |
||
330 | son = cur->lft; |
||
331 | if ((son->rgt_height - son->lft_height) != 1) { |
||
332 | /* |
||
333 | * LL rotation. |
||
334 | */ |
||
335 | gpa = son; |
||
336 | cur->lft = son->rgt; |
||
337 | if (cur->lft != NULL) cur->lft->par = cur; |
||
338 | cur->par = son; |
||
339 | son->rgt = cur; |
||
340 | /* |
||
341 | * Repair heights. |
||
342 | */ |
||
343 | cur->lft_height = son->rgt_height; |
||
344 | son->rgt_height = extavlreltree_tree_height(cur) + 1; |
||
345 | /* |
||
346 | * Repair rgt_sum. |
||
347 | */ |
||
348 | son->rgt_sum += cur->key + cur->rgt_sum; |
||
349 | } else { |
||
350 | /* |
||
351 | * LR rotation. |
||
352 | */ |
||
353 | gpa = son->rgt; |
||
354 | son->rgt = gpa->lft; |
||
355 | if (gpa->lft != NULL) gpa->lft->par = son; |
||
356 | gpa->lft = son; |
||
357 | son->par = gpa; |
||
358 | cur->lft = gpa->rgt; |
||
359 | if (gpa->rgt != NULL) gpa->rgt->par = cur; |
||
360 | gpa->rgt = cur; |
||
361 | cur->par = gpa; |
||
362 | /* |
||
363 | * Repair heights. |
||
364 | */ |
||
365 | cur->lft_height = gpa->rgt_height; |
||
366 | son->rgt_height = gpa->lft_height; |
||
367 | gpa->rgt_height = extavlreltree_tree_height(cur) + 1; |
||
368 | gpa->lft_height = extavlreltree_tree_height(son) + 1; |
||
369 | /* |
||
370 | * Repair rgt_sums. |
||
371 | */ |
||
372 | son->rgt_sum -= gpa->key + gpa->rgt_sum; |
||
373 | gpa->rgt_sum += cur->key + cur->rgt_sum; |
||
374 | } |
||
375 | /* |
||
376 | * Repair parent of current node. |
||
377 | */ |
||
378 | gpa->par = par; |
||
379 | } else { |
||
380 | /* |
||
381 | * Balance is correct, continue balancing at parent node. |
||
382 | */ |
||
383 | par = cur->par; |
||
384 | gpa = cur; |
||
385 | } |
||
386 | } else { |
||
387 | /* |
||
388 | * Insertion was made in the right subtree - repair right height, try to |
||
389 | * repair rgt_sum and check balance of current node. |
||
390 | */ |
||
391 | cur->rgt_height = extavlreltree_tree_height(cur->rgt) + 1; |
||
392 | |||
393 | if (repair_rgt_sum) { |
||
394 | cur->rgt_sum += newnode->key; |
||
395 | } |
||
396 | |||
397 | if ((cur->rgt_height - cur->lft_height) >= 2) { |
||
398 | /* |
||
399 | * Balance was corrupted, must be repaired through RL or RR rotation. |
||
400 | */ |
||
401 | par = cur->par; |
||
402 | son = cur->rgt; |
||
403 | if ((son->rgt_height - son->lft_height) != -1) { |
||
404 | /* |
||
405 | * RR rotation. |
||
406 | */ |
||
407 | gpa = son; |
||
408 | cur->rgt = son->lft; |
||
409 | if (cur->rgt != NULL) cur->rgt->par = cur; |
||
410 | cur->par = son; |
||
411 | son->lft = cur; |
||
412 | /* |
||
413 | * Repair heights. |
||
414 | */ |
||
415 | cur->rgt_height = son->lft_height; |
||
416 | son->lft_height = extavlreltree_tree_height(cur) + 1; |
||
417 | /* |
||
418 | * Repair rgt_sum. |
||
419 | */ |
||
420 | cur->rgt_sum -= son->rgt_sum + son->key; |
||
421 | } else { |
||
422 | /* |
||
423 | * RL rotation. |
||
424 | */ |
||
425 | gpa = son->lft; |
||
426 | son->lft = gpa->rgt; |
||
427 | if (gpa->rgt != NULL) gpa->rgt->par = son; |
||
428 | gpa->rgt = son; |
||
429 | son->par = gpa; |
||
430 | cur->rgt = gpa->lft; |
||
431 | if (gpa->lft != NULL) gpa->lft->par = cur; |
||
432 | gpa->lft = cur; |
||
433 | cur->par = gpa; |
||
434 | /* |
||
435 | * Repair heights. |
||
436 | */ |
||
437 | cur->rgt_height = gpa->lft_height; |
||
438 | son->lft_height = gpa->rgt_height; |
||
439 | gpa->lft_height = extavlreltree_tree_height(cur) + 1; |
||
440 | gpa->rgt_height = extavlreltree_tree_height(son) + 1; |
||
441 | /* |
||
442 | * Repair rgt_sums. |
||
443 | */ |
||
444 | cur->rgt_sum -= son->key + son->rgt_sum + gpa->key + gpa->rgt_sum; |
||
445 | gpa->rgt_sum += son->key + son->rgt_sum; |
||
446 | } |
||
447 | |||
448 | /* |
||
449 | * Repair parent of current node. |
||
450 | */ |
||
451 | gpa->par = par; |
||
452 | } else { |
||
453 | /* |
||
454 | * Balance is correct, continue balancing at parent node. |
||
455 | */ |
||
456 | par = cur->par; |
||
457 | gpa = cur; |
||
458 | } |
||
459 | } |
||
460 | /* |
||
461 | * Change parent pointers, set direction where is newnode and |
||
462 | * continue balancing at parent node or if current node |
||
463 | * is root then change root atribute pointer and stop |
||
464 | */ |
||
465 | if (par) { |
||
466 | if (par->lft == cur) { |
||
467 | par->lft = gpa; |
||
468 | dir = AVLTREE_LEFT; |
||
469 | } else { |
||
470 | par->rgt = gpa; |
||
471 | dir = AVLTREE_RIGHT; |
||
472 | } |
||
473 | } else { |
||
474 | t->root = gpa; |
||
475 | break; |
||
476 | } |
||
477 | cur = par; |
||
478 | } |
||
479 | } |
||
480 | |||
481 | |||
482 | /** Delete node from ExtAVLrel tree. |
||
483 | * |
||
484 | * @param t ExtAVLrel tree structure. |
||
485 | * @param node Address of node which will be deleted. |
||
486 | */ |
||
487 | void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node) |
||
488 | { |
||
489 | extavlreltree_node_t **gpapar; |
||
490 | extavlreltree_node_t *cur; |
||
491 | extavlreltree_node_t *par; |
||
492 | extavlreltree_node_t *gpa; |
||
493 | int8_t dir; |
||
494 | int8_t dir2=0; |
||
2421 | mencl | 495 | uint64_t key=0; |
2416 | mencl | 496 | int16_t balance; |
497 | /* |
||
498 | * Condition var - if true then all rgt_sums in the way down to root must be repaired in condition |
||
499 | * that we came there from right and on the way from repaired node to new node we |
||
500 | * never turn to the left. Reparation is done in the reparation cycle. |
||
501 | */ |
||
502 | bool repair_rgt_sum; |
||
503 | |||
504 | |||
505 | ASSERT(t); |
||
506 | ASSERT(node); |
||
507 | |||
508 | /* |
||
509 | * Delete node from list. |
||
510 | */ |
||
511 | node->next->prev = node->prev; |
||
512 | node->prev->next = node->next; |
||
513 | |||
514 | if (!node->par) { |
||
515 | if (t->root != node) { |
||
516 | /* |
||
517 | * It is list node (not a tree node). Needn't repair tree or anything else. |
||
518 | */ |
||
519 | return; |
||
520 | } |
||
521 | repair_rgt_sum = false; |
||
522 | gpapar = &(t->root); |
||
523 | } else { |
||
524 | /* |
||
525 | * Find tree pointer which points to node. |
||
526 | */ |
||
527 | if (node->par->lft == node) { |
||
528 | gpapar = &(node->par->lft); |
||
529 | repair_rgt_sum = false; |
||
530 | } else { |
||
531 | gpapar = &(node->par->rgt); |
||
532 | /* |
||
533 | * Node is right child - rgt_sum might be repaired. |
||
534 | */ |
||
535 | repair_rgt_sum = true; |
||
536 | } |
||
537 | } |
||
538 | |||
539 | |||
540 | if (&t->head != node->next && node->next->key == 0) { |
||
541 | /* |
||
542 | * Deleted node has at least one node node with the same key which is closest next |
||
543 | * neighbor in the list, copy node atributes into next node and end. |
||
544 | */ |
||
545 | cur = node->next; |
||
546 | cur->lft = node->lft; |
||
547 | cur->rgt = node->rgt; |
||
548 | cur->par = node->par; |
||
549 | cur->lft_height = node->lft_height; |
||
550 | cur->rgt_height = node->rgt_height; |
||
551 | *gpapar = cur; |
||
552 | |||
553 | if (node->lft) node->lft->par = cur; |
||
554 | if (node->rgt) node->rgt->par = cur; |
||
555 | |||
556 | cur->key = node->key; |
||
557 | cur->rgt_sum = node->rgt_sum; |
||
558 | return; |
||
559 | } |
||
560 | |||
561 | /* |
||
562 | * Repair next node's key (it must be difference between previous key and its key). |
||
563 | */ |
||
564 | if (node->next != &t->head) { |
||
565 | node->next->key += node->key; |
||
566 | } |
||
567 | |||
568 | /* |
||
569 | * Check situation in the tree around deleted node. |
||
570 | */ |
||
571 | if (!node->lft) { |
||
572 | /* |
||
573 | * Deleted node has not left son. Right son will take deleted node's place. |
||
574 | */ |
||
575 | gpa = node->par; |
||
576 | if (node->rgt) { |
||
577 | /* |
||
578 | * rgt_sum is not corrupted because the biggest key is in right subtree of node |
||
579 | */ |
||
580 | node->rgt->par = gpa; |
||
581 | repair_rgt_sum = false; |
||
582 | } else { |
||
583 | /* |
||
584 | * node is the biggest key and rgt_sum might be repaired according to which |
||
585 | * child is node. |
||
586 | */ |
||
587 | key = node->key; |
||
588 | } |
||
589 | |||
590 | if (!gpa) { |
||
591 | /* |
||
592 | * Deleted node is root node. Balancing is finished, change only |
||
593 | * root pointer in extavltree structure. |
||
594 | */ |
||
595 | *gpapar = node->rgt; |
||
596 | return; |
||
597 | } |
||
598 | dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
||
599 | |||
600 | *gpapar = node->rgt; |
||
601 | } else { |
||
602 | /* |
||
603 | * Node has left son. |
||
604 | */ |
||
605 | cur = node->lft; |
||
606 | if (!cur->rgt) { |
||
607 | /* |
||
608 | * Left son of node hasn't got right son. Left son will take deleted node's place. |
||
609 | */ |
||
610 | *gpapar = cur; |
||
611 | cur->par = node->par; |
||
612 | dir = AVLTREE_LEFT; |
||
613 | cur->rgt = node->rgt; |
||
614 | if (node->rgt) node->rgt->par = cur; |
||
615 | gpa = cur; |
||
616 | cur->rgt_height = node->rgt_height; |
||
617 | cur->lft_height = node->lft_height; |
||
618 | /* |
||
619 | * cur->lft_height will be decreased in repair cycle. |
||
620 | */ |
||
621 | |||
622 | if (repair_rgt_sum == false && node->rgt_sum == 0) { |
||
623 | /* |
||
624 | * node hasn't got right son so right sum is 0. |
||
625 | */ |
||
626 | cur->rgt_sum = 0; |
||
627 | } else { |
||
628 | cur->rgt_sum = node->rgt_sum + node->key; //pri node->rgt_sum == 0 bude opraveno v cyklu |
||
629 | if (repair_rgt_sum == true && node->rgt_sum != 0) { |
||
630 | /* |
||
631 | * node has got right son so node's key is not the biggest key in any subtree. |
||
632 | */ |
||
633 | repair_rgt_sum = false; |
||
634 | } else { |
||
635 | /* |
||
636 | * node is the biggest key and predecessors might be repaired. |
||
637 | */ |
||
638 | key = node->key; |
||
639 | } |
||
640 | } |
||
641 | } else { |
||
642 | /* |
||
643 | * Node has left and right son. Find a node with smallest key in left subtree |
||
644 | * and change that node with deleted node. |
||
645 | */ |
||
646 | while (cur->rgt != NULL) |
||
647 | cur = cur->rgt; |
||
648 | |||
649 | *gpapar = cur; |
||
650 | cur->rgt = node->rgt; |
||
651 | if (node->rgt) node->rgt->par = cur; |
||
652 | gpa = cur->par; |
||
653 | gpa->rgt = cur->lft; |
||
654 | if (cur->lft) cur->lft->par = gpa; |
||
655 | cur->lft = node->lft; |
||
656 | cur->lft->par = cur; |
||
657 | cur->par = node->par; |
||
658 | dir = AVLTREE_RIGHT; |
||
659 | cur->lft_height = node->lft_height; |
||
660 | cur->rgt_height = node->rgt_height; |
||
661 | /* |
||
662 | * gpa->rgt_height and cur->lft_height will be repaired in repair cycle. |
||
663 | */ |
||
664 | |||
665 | /* |
||
666 | * node must have always rgt child otherwise its malfunction of extavltree definition |
||
667 | * so we can add node->key. If it was to the contrary, we wouldn't know where |
||
668 | */ |
||
669 | cur->rgt_sum = node->rgt_sum + node->key; |
||
670 | /* |
||
671 | * The biggest key in at least one subtree was changed - rgt_sum must be repaired. |
||
672 | */ |
||
673 | repair_rgt_sum = true; |
||
674 | key = cur->key; |
||
675 | } |
||
676 | /* |
||
677 | * Deleted node is root node. Balancing is finished. |
||
678 | */ |
||
679 | if (!gpa) return; |
||
680 | } |
||
681 | |||
682 | /* |
||
683 | * Repair cycle which goes from gpa node down to root. |
||
684 | */ |
||
685 | for(;;) { |
||
686 | if (repair_rgt_sum) { |
||
687 | /* |
||
688 | * The biggest key in right subtree was deleted so rgt_sum must be changed. |
||
689 | */ |
||
690 | gpa->rgt_sum -= key; |
||
691 | } |
||
692 | |||
693 | /* |
||
694 | * Find tree pointer which points to the currently balanced node. When balanced |
||
695 | * node is root, root pointer from extavltree structure is taken. |
||
696 | */ |
||
697 | if (!gpa->par) |
||
698 | gpapar = &(t->root); |
||
699 | else { |
||
700 | if (gpa->par->lft == gpa) { |
||
701 | gpapar = &(gpa->par->lft); |
||
702 | dir2 = AVLTREE_LEFT; |
||
2421 | mencl | 703 | repair_rgt_sum = false; |
2416 | mencl | 704 | } else { |
705 | gpapar = &(gpa->par->rgt); |
||
706 | dir2 = AVLTREE_RIGHT; |
||
707 | } |
||
708 | } |
||
709 | |||
710 | if (dir == AVLTREE_LEFT) { |
||
711 | /* |
||
712 | * Deletition was made in left subtree. |
||
713 | */ |
||
714 | gpa->lft_height--; |
||
715 | balance = gpa->rgt_height - gpa->lft_height; |
||
716 | if (balance == 1) { |
||
717 | /* |
||
718 | * Stop balancing, tree is balanced. |
||
719 | */ |
||
720 | break; |
||
721 | } else if (balance == 2) { |
||
722 | /* |
||
723 | * Bad balance, heights of left and right subtrees differs more then is allowed. |
||
724 | */ |
||
725 | par = gpa->rgt; |
||
726 | |||
727 | if ((par->rgt_height - par->lft_height) == -1) { |
||
728 | /* |
||
729 | * RL rotation |
||
730 | */ |
||
731 | |||
732 | cur = par->lft; |
||
733 | par->lft = cur->rgt; |
||
734 | cur->rgt = par; |
||
735 | gpa->rgt = cur->lft; |
||
736 | cur->lft = gpa; |
||
737 | |||
738 | /* |
||
739 | * Repair balances. |
||
740 | */ |
||
741 | par->lft_height = cur->rgt_height; |
||
742 | gpa->rgt_height = cur->lft_height; |
||
743 | cur->lft_height = extavlreltree_tree_height(gpa) + 1; |
||
744 | cur->rgt_height = par->rgt_height + 1; |
||
745 | |||
746 | /* |
||
747 | * Repair paternity. |
||
748 | */ |
||
749 | if (gpa->rgt) gpa->rgt->par = gpa; |
||
750 | if (par->lft) par->lft->par = par; |
||
751 | cur->par = gpa->par; |
||
752 | gpa->par = cur; |
||
753 | par->par = cur; |
||
754 | |||
755 | /* |
||
756 | * Repair tree pointer which points to the current node. |
||
757 | */ |
||
758 | *gpapar = cur; |
||
759 | |||
760 | /* |
||
761 | * Repair rgt_sums after rotation was done. |
||
762 | */ |
||
763 | gpa->rgt_sum -= par->key + par->rgt_sum + cur->key + cur->rgt_sum; |
||
764 | cur->rgt_sum += par->key + par->rgt_sum; |
||
765 | |||
766 | /* |
||
767 | * Next balancing at parent node. |
||
768 | */ |
||
769 | gpa = cur->par; |
||
770 | } else { |
||
771 | /* |
||
772 | * RR rotation |
||
773 | */ |
||
774 | gpa->rgt = par->lft; |
||
775 | gpa->rgt_height = par->lft_height; |
||
776 | if (par->lft) par->lft->par = gpa; |
||
777 | par->lft = gpa; |
||
778 | |||
779 | /* |
||
780 | * Repair paternity. |
||
781 | */ |
||
782 | par->par = gpa->par; |
||
783 | gpa->par = par; |
||
784 | |||
785 | /* |
||
786 | * Repair heights and tree pointer which points to the current node. |
||
787 | */ |
||
788 | balance = par->rgt_height - par->lft_height; |
||
789 | par->lft_height++; |
||
790 | *gpapar = par; |
||
791 | |||
792 | /* |
||
793 | * Repair rgt_sums after rotation was done. |
||
794 | */ |
||
795 | gpa->rgt_sum -= par->key + par->rgt_sum; |
||
796 | |||
797 | /* |
||
798 | * Ends when tree is balanced or do the next step. |
||
799 | */ |
||
800 | if (balance == 0) return; |
||
801 | gpa = par->par; |
||
802 | } |
||
803 | } else { |
||
804 | /* |
||
805 | * Current node is balanced - perform balance check of its parent. |
||
806 | */ |
||
807 | gpa = gpa->par; |
||
808 | } |
||
809 | } else { |
||
810 | /* |
||
811 | * Balance right son. |
||
812 | */ |
||
813 | gpa->rgt_height--; |
||
814 | balance = gpa->rgt_height - gpa->lft_height; |
||
815 | if (balance == -1) { |
||
816 | /* |
||
817 | * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion. |
||
818 | */ |
||
819 | break; |
||
820 | } else if (balance == -2) { |
||
821 | /* |
||
822 | * Balance was corrupted - must be repaired. |
||
823 | */ |
||
824 | par = gpa->lft; |
||
825 | |||
826 | if ((par->rgt_height - par->lft_height) >= +1) { |
||
827 | /* |
||
828 | * If balance is -2 then par node always exists. |
||
829 | */ |
||
830 | if ((gpa->lft_height - (extavlreltree_tree_height(par))) == 1) { |
||
831 | /* |
||
832 | * LR rotation. Height of par subtree is not decreased due to timeout operation. |
||
833 | */ |
||
834 | |||
835 | cur = par->rgt; |
||
836 | par->rgt = cur->lft; |
||
837 | cur->lft = par; |
||
838 | gpa->lft = cur->rgt; |
||
839 | cur->rgt = gpa; |
||
840 | |||
841 | /* |
||
842 | * Repair balances. |
||
843 | */ |
||
844 | par->rgt_height = cur->lft_height; |
||
845 | gpa->lft_height = cur->rgt_height; |
||
846 | cur->rgt_height = gpa->rgt_height + 1; |
||
847 | cur->lft_height = extavlreltree_tree_height(par) + 1; |
||
848 | |||
849 | /* |
||
850 | * Repair paternity. |
||
851 | */ |
||
852 | if (gpa->lft) gpa->lft->par = gpa; |
||
853 | if (par->rgt) par->rgt->par = par; |
||
854 | cur->par = gpa->par; |
||
855 | gpa->par = cur; |
||
856 | par->par = cur; |
||
857 | |||
858 | /* |
||
859 | * Repair tree pointer which points to the current node. |
||
860 | */ |
||
861 | *gpapar = cur; |
||
862 | |||
863 | /* |
||
864 | * Repair rgt_sums after rotation was done. |
||
865 | */ |
||
866 | par->rgt_sum -= cur->key + cur->rgt_sum; |
||
867 | cur->rgt_sum += gpa->key + gpa->rgt_sum; |
||
868 | |||
869 | /* |
||
870 | * Next balancing at parent node. |
||
871 | */ |
||
872 | gpa = cur->par; |
||
873 | } else { |
||
874 | /* |
||
875 | * Left subtree of cur has been already decreased by timeout operation. |
||
876 | */ |
||
877 | gpa = gpa->par; |
||
878 | } |
||
879 | } else { |
||
880 | /* |
||
881 | * LL rotation. |
||
882 | */ |
||
883 | |||
884 | int prevlftheight = gpa->lft_height; |
||
885 | gpa->lft = par->rgt; |
||
886 | gpa->lft_height = par->rgt_height; |
||
887 | if (par->rgt) par->rgt->par = gpa; |
||
888 | par->rgt = gpa; |
||
889 | |||
890 | /* |
||
891 | * Repair paternity. |
||
892 | */ |
||
893 | par->par = gpa->par; |
||
894 | gpa->par = par; |
||
895 | |||
896 | /* |
||
897 | * Repair heights and tree pointer which points to the current node. |
||
898 | */ |
||
899 | balance = par->rgt_height - par->lft_height; |
||
900 | par->rgt_height = extavlreltree_tree_height(gpa) + 1; |
||
901 | *gpapar = par; |
||
902 | |||
903 | /* |
||
904 | * Repair rgt_sums after rotation was done. |
||
905 | */ |
||
906 | par->rgt_sum += gpa->key + gpa->rgt_sum; |
||
907 | |||
908 | /* |
||
909 | * Ends balancing when heights in par nodes are balanced and height |
||
910 | * of par subtree wasn't decreased due to timeout operation or do |
||
911 | * the next step. |
||
912 | */ |
||
913 | if (balance == 0 && par->rgt_height == prevlftheight) { |
||
914 | gpa = par; |
||
915 | break; |
||
916 | } |
||
917 | gpa = par->par; |
||
918 | } |
||
919 | } else { |
||
920 | /* |
||
921 | * Current node is balanced - perform balance check of its parent. |
||
922 | */ |
||
923 | gpa = gpa->par; |
||
924 | } |
||
925 | } |
||
926 | /* |
||
927 | * When root is reached then end balancing. |
||
928 | */ |
||
929 | if (!gpa) return; |
||
930 | |||
931 | dir = dir2; |
||
932 | } |
||
933 | |||
934 | /* |
||
935 | * End balancing. We must continue in repairing rgt_sum until we |
||
936 | * reach first left child. |
||
937 | */ |
||
938 | if (repair_rgt_sum) { |
||
939 | cur = gpa; |
||
940 | gpa = gpa->par; |
||
941 | while (gpa) { |
||
942 | if (gpa->lft == cur) |
||
943 | break; |
||
944 | gpa->rgt_sum -= key; |
||
945 | cur = gpa; |
||
946 | gpa = gpa->par; |
||
947 | } |
||
948 | } |
||
949 | } |
||
950 | |||
951 | |||
952 | /** Delete node from ExtAVLirel tree with the smallest key. |
||
953 | * |
||
954 | * Be careful deleted node must have key equal 0 to perform regular timeout. |
||
955 | * |
||
956 | * @param t ExtAVLrel tree structure. |
||
957 | */ |
||
958 | bool extavlreltree_delete_min(extavlreltree_t *t) |
||
959 | { |
||
960 | extavlreltree_node_t *expnode; |
||
961 | extavlreltree_node_t *nextnode; |
||
962 | |||
963 | ASSERT(t); |
||
964 | |||
965 | expnode = t->head.next; |
||
966 | nextnode = expnode->next; |
||
967 | |||
968 | if (&t->head == expnode) return false; |
||
969 | |||
970 | if (nextnode != &t->head) { |
||
971 | /* |
||
972 | * Only first node in the list can be tree node and its key can be 0 (nextnode is the second). |
||
973 | */ |
||
974 | if (nextnode->key == 0) { |
||
975 | /* |
||
976 | * Next node of expnode is its chain node. Copy expnode into nextnode. |
||
977 | */ |
||
978 | |||
979 | nextnode->lft = expnode->lft; |
||
980 | nextnode->rgt = expnode->rgt; |
||
981 | nextnode->par = expnode->par; |
||
982 | nextnode->lft_height = expnode->lft_height; |
||
983 | nextnode->rgt_height = expnode->rgt_height; |
||
984 | if (t->root == expnode) |
||
985 | t->root = nextnode; |
||
986 | else |
||
987 | if (expnode->par->lft == expnode) |
||
988 | expnode->par->lft = nextnode; |
||
989 | else |
||
990 | expnode->par->rgt = nextnode; |
||
991 | |||
992 | if (expnode->lft) expnode->lft->par = nextnode; |
||
993 | if (expnode->rgt) expnode->rgt->par = nextnode; |
||
994 | |||
995 | nextnode->rgt_sum = expnode->rgt_sum; |
||
996 | } else if (!expnode->par) { |
||
997 | /* |
||
998 | * Delete root node which musn't have left son. |
||
999 | */ |
||
1000 | |||
1001 | t->root = expnode->rgt; |
||
1002 | if (expnode->rgt) expnode->rgt->par = NULL; |
||
1003 | } else if (expnode->rgt) { |
||
1004 | /* |
||
1005 | * Always delete parent of left son. |
||
1006 | */ |
||
1007 | |||
1008 | expnode->rgt->par = expnode->par; |
||
1009 | expnode->par->lft = expnode->rgt; |
||
1010 | expnode->par->lft_height = expnode->rgt_height; |
||
1011 | } else { |
||
1012 | /* |
||
1013 | * Deleted node doesn't have right son. |
||
1014 | */ |
||
1015 | |||
1016 | expnode->par->lft = NULL; |
||
1017 | expnode->par->lft_height = 0; |
||
1018 | } |
||
1019 | nextnode->key += expnode->key; |
||
1020 | } |
||
1021 | |||
1022 | /* |
||
1023 | * Delete node from the list. |
||
1024 | */ |
||
1025 | t->head.next = nextnode; |
||
1026 | nextnode->prev = &t->head; |
||
1027 | |||
1028 | return true; |
||
1029 | } |