Rev 2416 | Rev 2431 | 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 implementation. |
||
36 | * |
||
37 | * This file implements Extended AVL tree type and operations. |
||
38 | * |
||
39 | * Extended AVL tree (ExtAvl tree) has the following properties: |
||
40 | * @li it is binary search tree with unique 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 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 keys |
||
46 | * |
||
47 | * Be careful of using this tree because of base atribute, which is added to every inserted |
||
48 | * node key. |
||
49 | */ |
||
50 | |||
51 | #include <adt/extavl.h> |
||
52 | #include <debug.h> |
||
53 | #include <panic.h> |
||
54 | |||
55 | #define AVLTREE_LEFT 0 |
||
56 | #define AVLTREE_RIGHT 1 |
||
57 | |||
58 | /* Returns height of tree -1 */ |
||
59 | #define extavltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height)) |
||
60 | |||
61 | /** Search first occurence (oldest node with this key) of given key in Extended AVL tree. |
||
62 | * |
||
63 | * @param t Extended AVL tree. |
||
64 | * @param key Key to be searched. |
||
65 | * |
||
2421 | mencl | 66 | * @return Pointer to node or NULL if there is no such key. |
2416 | mencl | 67 | */ |
68 | extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key) |
||
69 | { |
||
70 | extavltree_node_t *cur; |
||
71 | |||
72 | cur = t->root; |
||
73 | while (cur != NULL) { |
||
74 | if (cur->key < key) { |
||
75 | cur = cur->rgt; |
||
76 | } else if (cur->key > key) { |
||
77 | cur = cur->lft; |
||
78 | } else { |
||
79 | return cur; |
||
80 | } |
||
81 | } |
||
82 | return NULL; |
||
83 | } |
||
84 | |||
85 | /** Insert new node into ExtAVL tree. |
||
86 | * |
||
87 | * New node's key must be set. |
||
88 | * |
||
89 | * @param t ExtAVL tree structure. |
||
90 | * @param newnode New node to be inserted. |
||
91 | */ |
||
92 | void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode) |
||
93 | { |
||
94 | extavltree_node_t *cur; |
||
95 | extavltree_node_t *son; |
||
96 | extavltree_node_t *gpa; |
||
97 | extavltree_node_t *par; |
||
98 | uint64_t key; |
||
99 | |||
100 | ASSERT(t); |
||
101 | ASSERT(newnode); |
||
102 | |||
103 | /* |
||
104 | * Creating absolute key. |
||
105 | */ |
||
106 | newnode->key = key = newnode->key + t->base; |
||
107 | |||
108 | |||
109 | /* |
||
110 | * Insert first node into empty tree. |
||
111 | */ |
||
112 | if (t->root == NULL) { |
||
113 | newnode->lft = NULL; |
||
114 | newnode->rgt = NULL; |
||
115 | newnode->lft_height = 0; |
||
116 | newnode->rgt_height = 0; |
||
117 | newnode->par = NULL; |
||
118 | newnode->next = &t->head; |
||
119 | newnode->prev = &t->head; |
||
120 | |||
121 | t->head.prev = newnode; |
||
122 | t->head.next = newnode; |
||
123 | t->root = newnode; |
||
124 | return; |
||
125 | } |
||
126 | |||
127 | /* |
||
128 | * Tree is not empty - search for the right place for new node. |
||
129 | */ |
||
130 | cur = t->root; |
||
131 | while(true) { |
||
132 | if (cur->key < key) { |
||
133 | if (!cur->rgt) { |
||
134 | /* |
||
135 | * We have reach leaf. New node will be right son. |
||
136 | */ |
||
137 | cur->rgt = newnode; |
||
138 | |||
139 | newnode->lft = NULL; |
||
140 | newnode->rgt = NULL; |
||
141 | newnode->lft_height = 0; |
||
142 | newnode->rgt_height = 0; |
||
143 | newnode->par = cur; |
||
144 | |||
145 | newnode->prev = cur; |
||
146 | newnode->next = cur->next; |
||
147 | cur->next->prev = newnode; |
||
148 | cur->next = newnode; |
||
149 | break; |
||
150 | } |
||
151 | cur = cur->rgt; |
||
152 | } else if (cur->key > key) { |
||
153 | if (!cur->lft) { |
||
154 | /* |
||
155 | * We have reach leaf. New node will be left son. |
||
156 | */ |
||
157 | cur->lft = newnode; |
||
158 | |||
159 | newnode->lft = NULL; |
||
160 | newnode->rgt = NULL; |
||
161 | newnode->lft_height = 0; |
||
162 | newnode->rgt_height = 0; |
||
163 | newnode->par = cur; |
||
164 | |||
165 | gpa = cur; |
||
166 | while (gpa != &t->head && gpa->key == cur->key) |
||
167 | gpa = gpa->prev; |
||
168 | newnode->next = gpa->next; |
||
169 | newnode->prev = gpa; |
||
170 | gpa->next->prev = newnode; |
||
171 | gpa->next = newnode; |
||
172 | break; |
||
173 | } |
||
174 | cur = cur->lft; |
||
175 | } else { |
||
176 | /* |
||
177 | * Key has been previously inserted into tree. Make new node as a tree node |
||
178 | * and old tree node move to the prev. Old tree node will be list node. |
||
179 | */ |
||
180 | |||
181 | newnode->prev = cur; |
||
182 | newnode->next = cur->next; |
||
183 | cur->next->prev = newnode; |
||
184 | cur->next = newnode; |
||
185 | |||
186 | newnode->par = cur->par; |
||
187 | cur->par = NULL; |
||
188 | newnode->lft = cur->lft; |
||
189 | cur->lft = NULL; |
||
190 | newnode->rgt = cur->rgt; |
||
191 | cur->rgt = NULL; |
||
192 | newnode->lft_height = cur->lft_height; |
||
193 | cur->lft_height = 0; |
||
194 | newnode->rgt_height = cur->rgt_height; |
||
195 | cur->rgt_height = 0; |
||
196 | |||
197 | if (newnode->lft) newnode->lft->par = newnode; |
||
198 | if (newnode->rgt) newnode->rgt->par = newnode; |
||
199 | if (newnode->par) { |
||
200 | if (newnode->par->lft == cur) |
||
201 | newnode->par->lft = newnode; |
||
202 | else |
||
203 | newnode->par->rgt = newnode; |
||
204 | } else { |
||
205 | t->root = newnode; |
||
206 | } |
||
207 | return; |
||
208 | } |
||
209 | } |
||
210 | |||
211 | /* |
||
212 | * Balancing all nodes from newnode's parent down to root. All nodes must be checked |
||
213 | * because delete min operation can corrupt heights and only insert operation can |
||
214 | * repair it. |
||
215 | */ |
||
216 | cur = newnode->par; |
||
217 | while (cur) { |
||
218 | if (cur->key > key) { |
||
219 | /* |
||
220 | * Insertion was made in the left subtree - repair left height |
||
221 | * and check balance of current node. |
||
222 | */ |
||
223 | cur->lft_height = extavltree_tree_height(cur->lft) + 1; |
||
224 | |||
225 | if ((cur->rgt_height - cur->lft_height) <= -2) { |
||
226 | /* |
||
227 | * Balance was corrupted, must be repaired through LL or LR rotation. |
||
228 | */ |
||
229 | par = cur->par; |
||
230 | son = cur->lft; |
||
231 | if ((son->rgt_height - son->lft_height) != 1) { |
||
232 | /* |
||
233 | * LL rotation |
||
234 | */ |
||
235 | |||
236 | gpa = son; |
||
237 | cur->lft = son->rgt; |
||
238 | if (cur->lft != NULL) cur->lft->par = cur; |
||
239 | cur->par = son; |
||
240 | son->rgt = cur; |
||
241 | /* |
||
242 | * Repair heights. |
||
243 | */ |
||
244 | cur->lft_height = son->rgt_height; |
||
245 | son->rgt_height = extavltree_tree_height(cur) + 1; |
||
246 | } else { |
||
247 | /* |
||
248 | * LR rotation |
||
249 | */ |
||
250 | |||
251 | gpa = son->rgt; |
||
252 | son->rgt = gpa->lft; |
||
253 | if (gpa->lft != NULL) gpa->lft->par = son; |
||
254 | gpa->lft = son; |
||
255 | son->par = gpa; |
||
256 | cur->lft = gpa->rgt; |
||
257 | if (gpa->rgt != NULL) gpa->rgt->par = cur; |
||
258 | gpa->rgt = cur; |
||
259 | cur->par = gpa; |
||
260 | /* |
||
261 | * Repair heights. |
||
262 | */ |
||
263 | cur->lft_height = gpa->rgt_height; |
||
264 | son->rgt_height = gpa->lft_height; |
||
265 | gpa->rgt_height = extavltree_tree_height(cur) + 1; |
||
266 | gpa->lft_height = extavltree_tree_height(son) + 1; |
||
267 | } |
||
268 | |||
269 | /* |
||
270 | * Change parent pointers or if current node is root then |
||
271 | * change root atribute pointer. |
||
272 | */ |
||
273 | gpa->par = par; |
||
274 | if (par) { |
||
275 | if (par->lft == cur) |
||
276 | par->lft = gpa; |
||
277 | else |
||
278 | par->rgt = gpa; |
||
279 | } else { |
||
280 | t->root = gpa; |
||
281 | } |
||
282 | cur = par; |
||
283 | } else { |
||
284 | /* |
||
285 | * Current node is balanced, continue balancing of its parent. |
||
286 | */ |
||
287 | cur = cur->par; |
||
288 | } |
||
289 | } else { |
||
290 | /* |
||
291 | * Insertion was made in the right subtree - repair right height |
||
292 | * and check balance of current node. |
||
293 | */ |
||
294 | cur->rgt_height = extavltree_tree_height(cur->rgt) + 1; |
||
295 | |||
296 | if ((cur->rgt_height - cur->lft_height) >= 2) { |
||
297 | /* |
||
298 | * Balance was corrupted, must be repaired through LL or LR rotation. |
||
299 | */ |
||
300 | par = cur->par; |
||
301 | son = cur->rgt; |
||
302 | if ((son->rgt_height - son->lft_height) != -1) { |
||
303 | /* |
||
304 | * RR rotation |
||
305 | */ |
||
306 | gpa = son; |
||
307 | cur->rgt = son->lft; |
||
308 | if (cur->rgt != NULL) cur->rgt->par = cur; |
||
309 | cur->par = son; |
||
310 | son->lft = cur; |
||
311 | /* |
||
312 | * Repair heights. |
||
313 | */ |
||
314 | cur->rgt_height = son->lft_height; |
||
315 | son->lft_height = extavltree_tree_height(cur) + 1; |
||
316 | } else { |
||
317 | /* |
||
318 | * RL rotation |
||
319 | */ |
||
320 | gpa = son->lft; |
||
321 | son->lft = gpa->rgt; |
||
322 | if (gpa->rgt != NULL) gpa->rgt->par = son; |
||
323 | gpa->rgt = son; |
||
324 | son->par = gpa; |
||
325 | cur->rgt = gpa->lft; |
||
326 | if (gpa->lft != NULL) gpa->lft->par = cur; |
||
327 | gpa->lft = cur; |
||
328 | cur->par = gpa; |
||
329 | /* |
||
330 | * Repair heights. |
||
331 | */ |
||
332 | cur->rgt_height = gpa->lft_height; |
||
333 | son->lft_height = gpa->rgt_height; |
||
334 | gpa->lft_height = extavltree_tree_height(cur) + 1; |
||
335 | gpa->rgt_height = extavltree_tree_height(son) + 1; |
||
336 | } |
||
337 | |||
338 | /* |
||
339 | * Change parent pointers or if current node is root then |
||
340 | * change root atribute pointer. |
||
341 | */ |
||
342 | gpa->par = par; |
||
343 | if (par) { |
||
344 | if (par->lft == cur) |
||
345 | par->lft = gpa; |
||
346 | else |
||
347 | par->rgt = gpa; |
||
348 | } else { |
||
349 | t->root = gpa; |
||
350 | } |
||
351 | cur = par; |
||
352 | } else { |
||
353 | /* |
||
354 | * Current node is balanced, continue balancing of its parent. |
||
355 | */ |
||
356 | cur = cur->par; |
||
357 | } |
||
358 | } |
||
359 | } |
||
360 | } |
||
361 | |||
362 | /** Delete node from ExtAVL tree. |
||
363 | * |
||
364 | * @param t ExtAVL tree structure. |
||
365 | * @param node Address of node which will be deleted. |
||
366 | */ |
||
367 | void extavltree_delete(extavltree_t *t, extavltree_node_t *node) |
||
368 | { |
||
369 | extavltree_node_t **gpapar; |
||
370 | extavltree_node_t *cur; |
||
371 | extavltree_node_t *par; |
||
372 | extavltree_node_t *gpa; |
||
373 | int8_t dir; |
||
374 | int8_t dir2=0; |
||
375 | int16_t balance; |
||
376 | |||
377 | ASSERT(t); |
||
378 | ASSERT(node); |
||
379 | |||
380 | /* |
||
381 | * Delete node from list. |
||
382 | */ |
||
383 | node->next->prev = node->prev; |
||
384 | node->prev->next = node->next; |
||
385 | |||
386 | if (!node->par) { |
||
387 | if (t->root != node) { |
||
388 | /* |
||
389 | * It is list node (not a tree node). Needn't repair tree or anything else. |
||
390 | */ |
||
391 | return; |
||
392 | } |
||
393 | gpapar = &(t->root); |
||
394 | } else { |
||
395 | /* |
||
396 | * Find tree pointer which points to node. |
||
397 | */ |
||
398 | if (node->par->lft == node) { |
||
399 | gpapar = &(node->par->lft); |
||
400 | } else { |
||
401 | gpapar = &(node->par->rgt); |
||
402 | } |
||
403 | } |
||
404 | |||
405 | |||
406 | if (&t->head != node->prev && node->prev->key == node->key) { |
||
407 | /* |
||
408 | * Deleted node has at least one node node with the same key which is closest previous |
||
409 | * neighbor in the list, copy node atributes into previous node and end. |
||
410 | */ |
||
411 | cur = node->prev; |
||
412 | cur->lft = node->lft; |
||
413 | cur->rgt = node->rgt; |
||
414 | cur->par = node->par; |
||
415 | cur->lft_height = node->lft_height; |
||
416 | cur->rgt_height = node->rgt_height; |
||
417 | *gpapar = cur; |
||
418 | |||
419 | if (node->lft) node->lft->par = cur; |
||
420 | if (node->rgt) node->rgt->par = cur; |
||
421 | return; |
||
422 | } |
||
423 | |||
424 | /* |
||
425 | * Check situation in the tree around deleted node. |
||
426 | */ |
||
427 | if (!node->lft) { |
||
428 | /* |
||
429 | * Deleted node has not left son. Right son will take deleted node's place. |
||
430 | */ |
||
431 | gpa = node->par; |
||
432 | if (node->rgt) node->rgt->par = gpa; |
||
433 | if (!gpa) { |
||
434 | /* |
||
435 | * Deleted node is root node. Balancing is finished, change only |
||
436 | * root pointer in extavltree structure. |
||
437 | */ |
||
438 | *gpapar = node->rgt; |
||
439 | return; |
||
440 | } |
||
441 | dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
||
442 | *gpapar = node->rgt; |
||
443 | } else { |
||
444 | /* |
||
445 | * Node has left son. |
||
446 | */ |
||
447 | cur = node->lft; |
||
448 | if (!cur->rgt) { |
||
449 | /* |
||
450 | * Left son of node hasn't got right son. Left son will take deleted node's place. |
||
451 | */ |
||
452 | *gpapar = cur; |
||
453 | cur->par = node->par; |
||
454 | dir = AVLTREE_LEFT; |
||
455 | cur->rgt = node->rgt; |
||
456 | if (node->rgt) node->rgt->par = cur; |
||
457 | gpa = cur; |
||
458 | cur->rgt_height = node->rgt_height; |
||
459 | cur->lft_height = node->lft_height; |
||
460 | /* |
||
461 | * cur->lft_height will be decreased in repair cycle. |
||
462 | */ |
||
463 | } else { |
||
464 | /* |
||
465 | * Node has left and right son. Find a node with smallest key in left subtree |
||
466 | * and change that node with deleted node. |
||
467 | */ |
||
468 | while (cur->rgt != NULL) |
||
469 | cur = cur->rgt; |
||
470 | |||
471 | *gpapar = cur; |
||
472 | cur->rgt = node->rgt; |
||
473 | if (node->rgt) node->rgt->par = cur; |
||
474 | gpa = cur->par; |
||
475 | gpa->rgt = cur->lft; |
||
476 | if (cur->lft) cur->lft->par = gpa; |
||
477 | cur->lft = node->lft; |
||
478 | cur->lft->par = cur; |
||
479 | cur->par = node->par; |
||
480 | dir = AVLTREE_RIGHT; |
||
481 | cur->lft_height = node->lft_height; |
||
482 | cur->rgt_height = node->rgt_height; |
||
483 | /* |
||
484 | * gpa->rgt_height and cur->lft_height will be repaired in repair cycle. |
||
485 | */ |
||
486 | } |
||
487 | /* |
||
488 | * Deleted node is root node. Balancing is finished. |
||
489 | */ |
||
490 | if (!gpa) return; |
||
491 | } |
||
492 | |||
493 | /* |
||
494 | * Repair cycle which goes from gpa node down to root. |
||
495 | */ |
||
496 | for(;;) { |
||
497 | /* |
||
498 | * Find tree pointer which points to the currently balanced node. When balanced |
||
499 | * node is root, root pointer from extavltree structure is taken. |
||
500 | */ |
||
501 | if (!gpa->par) |
||
502 | gpapar = &(t->root); |
||
503 | else { |
||
504 | if (gpa->par->lft == gpa) { |
||
505 | gpapar = &(gpa->par->lft); |
||
506 | dir2 = AVLTREE_LEFT; |
||
507 | } else { |
||
508 | gpapar = &(gpa->par->rgt); |
||
509 | dir2 = AVLTREE_RIGHT; |
||
510 | } |
||
511 | } |
||
512 | |||
513 | if (dir == AVLTREE_LEFT) { |
||
514 | /* |
||
515 | * Deletition was made in left subtree. |
||
516 | */ |
||
517 | gpa->lft_height--; |
||
518 | balance = gpa->rgt_height - gpa->lft_height; |
||
519 | if (balance == 1) { |
||
520 | /* |
||
521 | * Stop balancing, tree is balanced. |
||
522 | */ |
||
523 | break; |
||
524 | } else if (balance == 2) { |
||
525 | /* |
||
526 | * Bad balance, heights of left and right subtrees differs more then is allowed. |
||
527 | */ |
||
528 | par = gpa->rgt; |
||
529 | |||
530 | if ((par->rgt_height - par->lft_height) == -1) { |
||
531 | /* |
||
532 | * RL rotation |
||
533 | */ |
||
534 | |||
535 | cur = par->lft; |
||
536 | par->lft = cur->rgt; |
||
537 | cur->rgt = par; |
||
538 | gpa->rgt = cur->lft; |
||
539 | cur->lft = gpa; |
||
540 | |||
541 | /* |
||
542 | * Repair balances. |
||
543 | */ |
||
544 | par->lft_height = cur->rgt_height; |
||
545 | gpa->rgt_height = cur->lft_height; |
||
546 | cur->lft_height = extavltree_tree_height(gpa) + 1; //POZOR nelze: cur->lft_height = gpa->lft_height + 1; - vyska cur je diky timeoutu nesttabilni |
||
547 | cur->rgt_height = par->rgt_height + 1; //POZOR zmena: cur->rgt_height = extavltree_tree_height(par) + 1; |
||
548 | |||
549 | /* |
||
550 | * Repair paternity. |
||
551 | */ |
||
552 | if (gpa->rgt) gpa->rgt->par = gpa; |
||
553 | if (par->lft) par->lft->par = par; |
||
554 | cur->par = gpa->par; |
||
555 | gpa->par = cur; |
||
556 | par->par = cur; |
||
557 | |||
558 | /* |
||
559 | * Repair tree pointer which points to the current node and do the next step. |
||
560 | */ |
||
561 | *gpapar = cur; |
||
562 | gpa = cur->par; |
||
563 | } else { |
||
564 | /* |
||
565 | * RR rotation |
||
566 | */ |
||
567 | |||
568 | gpa->rgt = par->lft; |
||
569 | gpa->rgt_height = par->lft_height; |
||
570 | if (par->lft) par->lft->par = gpa; |
||
571 | par->lft = gpa; |
||
572 | |||
573 | /* |
||
574 | * Repair paternity. |
||
575 | */ |
||
576 | par->par = gpa->par; |
||
577 | gpa->par = par; |
||
578 | |||
579 | /* |
||
580 | * Repair balances. |
||
581 | */ |
||
582 | balance = par->rgt_height - par->lft_height; |
||
583 | par->lft_height++; |
||
584 | |||
585 | /* |
||
586 | * Repair tree pointer which points to the current node, ends when tree is balanced |
||
587 | * or do the next step. |
||
588 | */ |
||
589 | *gpapar = par; |
||
590 | if (balance == 0) break; |
||
591 | gpa = par->par; |
||
592 | } |
||
593 | } else { |
||
594 | /* |
||
595 | * Current node is balanced - perform balance check of its parent. |
||
596 | */ |
||
597 | gpa = gpa->par; |
||
598 | } |
||
599 | } else { |
||
600 | /* |
||
601 | * Balance right son. |
||
602 | */ |
||
603 | gpa->rgt_height--; |
||
604 | balance = gpa->rgt_height - gpa->lft_height; |
||
605 | if (balance == -1) { |
||
606 | /* |
||
607 | * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion. |
||
608 | */ |
||
609 | break; |
||
610 | } else if (balance == -2) { |
||
611 | /* |
||
612 | * Balance was corrupted - must be repaired. |
||
613 | */ |
||
614 | par = gpa->lft; |
||
615 | |||
616 | if ((par->rgt_height - par->lft_height) >= +1) { |
||
617 | /* |
||
618 | * If balance is -2 then par node always exists. |
||
619 | */ |
||
620 | if ((gpa->lft_height - (extavltree_tree_height(par))) == 1) { |
||
621 | /* |
||
622 | * LR rotation. Height of par subtree is not decreased due to timeout operation. |
||
623 | */ |
||
624 | |||
625 | cur = par->rgt; |
||
626 | par->rgt = cur->lft; |
||
627 | cur->lft = par; |
||
628 | gpa->lft = cur->rgt; |
||
629 | cur->rgt = gpa; |
||
630 | |||
631 | /* |
||
632 | * Repair balances. |
||
633 | */ |
||
634 | par->rgt_height = cur->lft_height; |
||
635 | gpa->lft_height = cur->rgt_height; |
||
636 | cur->rgt_height = gpa->rgt_height + 1; |
||
637 | cur->lft_height = extavltree_tree_height(par) + 1; |
||
638 | |||
639 | /* |
||
640 | * Repair paternity. |
||
641 | */ |
||
642 | if (gpa->lft) gpa->lft->par = gpa; |
||
643 | if (par->rgt) par->rgt->par = par; |
||
644 | cur->par = gpa->par; |
||
645 | gpa->par = cur; |
||
646 | par->par = cur; |
||
647 | |||
648 | /* |
||
649 | * Repair tree pointer which points to the current node and do the next step. |
||
650 | */ |
||
651 | *gpapar = cur; |
||
652 | gpa = cur->par; |
||
653 | } else { |
||
654 | /* |
||
655 | * Left subtree of cur has been already decreased by timeout operation. |
||
656 | */ |
||
657 | gpa = gpa->par; |
||
658 | } |
||
659 | } else { |
||
660 | /* |
||
661 | * LL rotation. |
||
662 | */ |
||
663 | |||
664 | int prevlftheight = gpa->lft_height; |
||
665 | gpa->lft = par->rgt; |
||
666 | gpa->lft_height = par->rgt_height; |
||
667 | if (par->rgt) par->rgt->par = gpa; |
||
668 | par->rgt = gpa; |
||
669 | |||
670 | /* |
||
671 | * Repair paternity. |
||
672 | */ |
||
673 | par->par = gpa->par; |
||
674 | gpa->par = par; |
||
675 | |||
676 | /* |
||
677 | * Repair height. |
||
678 | */ |
||
679 | balance = par->rgt_height - par->lft_height; |
||
680 | par->rgt_height = extavltree_tree_height(gpa) + 1; |
||
681 | |||
682 | /* |
||
683 | * Repair tree pointer which points to the current node, ends when heights in par nodes are |
||
684 | * balanced and height of par subtree wasn't decreased due to timeout operation orr do |
||
685 | * the next step. |
||
686 | */ |
||
687 | *gpapar = par; |
||
688 | if (balance == 0 && par->rgt_height == prevlftheight) return; |
||
689 | gpa = par->par; |
||
690 | } |
||
691 | } else { |
||
692 | /* |
||
693 | * Current node is balanced - perform balance check of its parent. |
||
694 | */ |
||
695 | gpa = gpa->par; |
||
696 | } |
||
697 | } |
||
698 | /* |
||
699 | * When root is reached then end balancing. |
||
700 | */ |
||
701 | if (!gpa) return; |
||
702 | |||
703 | dir = dir2; |
||
704 | } |
||
705 | } |
||
706 | |||
707 | |||
708 | /** Delete node from ExtAVL tree with the smallest key and set base of tree to that key. |
||
709 | * |
||
710 | * @param t ExtAVL tree structure. |
||
711 | */ |
||
712 | bool extavltree_delete_min(extavltree_t *t) |
||
713 | { |
||
714 | extavltree_node_t *expnode; |
||
715 | |||
716 | ASSERT(t); |
||
717 | |||
718 | expnode = t->head.next; |
||
719 | |||
720 | if (&t->head == expnode) return false; |
||
721 | |||
722 | if (expnode->key != expnode->next->key) { |
||
723 | /* |
||
724 | * Repair tree data structure. |
||
725 | */ |
||
726 | if (!expnode->par) { |
||
727 | /* |
||
728 | * Delete root node which musn't have left son. |
||
729 | */ |
||
730 | |||
731 | ASSERT(!expnode->lft); |
||
732 | t->root = expnode->rgt; |
||
733 | if (expnode->rgt) expnode->rgt->par = NULL; |
||
734 | } else if (expnode->rgt) { |
||
735 | /* |
||
736 | * Always delete parent of left son. |
||
737 | */ |
||
738 | |||
739 | expnode->rgt->par = expnode->par; |
||
740 | expnode->par->lft = expnode->rgt; |
||
741 | expnode->par->lft_height = expnode->rgt_height; |
||
742 | } else { |
||
743 | /* |
||
744 | * Deleted node doesn't have right son. |
||
745 | */ |
||
746 | |||
747 | expnode->par->lft = NULL; |
||
748 | expnode->par->lft_height = 0; |
||
749 | } |
||
750 | } |
||
751 | |||
752 | /* |
||
753 | * Delete node from the list. |
||
754 | */ |
||
755 | t->head.next = expnode->next; |
||
756 | expnode->next->prev = &t->head; |
||
757 | |||
758 | return true; |
||
759 | } |