Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 : : /*
3 : : * AVL Tree
4 : : * (C) 2014 Jung-Sang Ahn <jungsang.ahn@gmail.com>
5 : : * see https://github.com/greensky00/avltree
6 : : */
7 : :
8 : : #ifndef INLINE
9 : : #ifdef __APPLE__
10 : : #define INLINE extern inline
11 : : #elif __linux__
12 : : #define INLINE __inline
13 : : #else
14 : : #define INLINE
15 : : #endif
16 : : #endif
17 : :
18 : : #include "avltree.h"
19 : :
20 : : #define max(a,b) (((a) > (b)) ? (a) : (b))
21 : :
22 : 61686925 : INLINE int _abs(int n) {
23 : 61686925 : int mask = n >> ((sizeof(int)*8) -1);
24 : 61686925 : return (mask + n)^mask;
25 : : }
26 : :
27 : 49427669 : INLINE void avl_set_parent(struct avl_node *node, struct avl_node *parent)
28 : : {
29 : : node->parent = (struct avl_node *)(
30 : 49427669 : (uint64_t)parent | ((uint64_t)node->parent & 0x3));
31 : 49427669 : }
32 : :
33 : : #ifdef __AVL_DEBUG
34 : : #include <stdio.h>
35 : : #include <assert.h>
36 : : #include "avltree_debug.h"
37 : : #else
38 : : #define __AVL_DEBUG_BF_CHECK(bf)
39 : : #define __AVL_DEBUG_LL(p, c, pb, cb)
40 : : #define __AVL_DEBUG_RR(p, c, pb, cb)
41 : : #define __AVL_DEBUG_BAL_BEGIN(node, bf, height_diff)
42 : : #define __AVL_DEBUG_BAL_END(node)
43 : : #define __AVL_DEBUG_INSERT(node)
44 : : #define __AVL_DEBUG_REMOVE(node)
45 : : #define __AVL_DEBUG_DISPLAY(tree)
46 : : #endif
47 : :
48 : 84713765 : INLINE void avl_set_bf(struct avl_node *node, int bf)
49 : : {
50 : : __AVL_DEBUG_BF_CHECK(bf);
51 : :
52 : : #ifdef _AVL_SEPARATE_PARENT_BF
53 : : node->bf = bf;
54 : : #else
55 : : node->parent = (struct avl_node *)(
56 : 84713765 : (uint64_t)avl_parent(node) | (uint64_t)(bf+1));
57 : : #endif
58 : 84713765 : }
59 : :
60 : 1262258 : INLINE struct avl_node* _rotate_LL(struct avl_node *parent,
61 : : int parent_bf,
62 : : int *child_bf,
63 : : int *height_delta)
64 : : // MUST ensure that parent_bf <= 0
65 : : {
66 : : int p_right, c_left, c_right;
67 : 1262258 : struct avl_node *child = parent->left;
68 : :
69 : : __AVL_DEBUG_LL(parent, child, parent_bf, *child_bf);
70 : :
71 [ + + ]: 1262258 : c_left = (child->left)?(1):(0);
72 [ + + ]: 1262258 : c_right = (child->right)?(1):(0);
73 [ + + ]: 1262258 : if (*child_bf < 0) {
74 : : // child->left > child->right
75 : 832910 : c_left = c_right - (*child_bf);
76 : 832910 : p_right = c_left + 1 + parent_bf;
77 [ + + ]: 832910 : if (height_delta)
78 [ - + ][ + - ]: 43948 : *height_delta = max(c_left, max(c_right, p_right)+1) - (c_left + 1);
[ - + ]
79 : :
80 : : } else {
81 : : // child->left <= child->right
82 : 429348 : c_right = c_left + (*child_bf);
83 : 429348 : p_right = c_right + 1 + parent_bf;
84 [ + + ]: 429348 : if (height_delta)
85 [ - + ][ + - ]: 368680 : *height_delta = max(c_left, max(c_right, p_right)+1) - (c_right + 1);
[ - + ]
86 : : }
87 [ + + ]: 1262258 : *child_bf = (max(c_right, p_right) + 1) - c_left;
88 : 1262258 : avl_set_bf(parent, p_right - c_right);
89 : :
90 : 1262258 : parent->left = child->right;
91 [ + + ]: 1262258 : if (child->right)
92 : 397628 : avl_set_parent(child->right, parent);
93 : 1262258 : child->right = parent;
94 : 1262258 : avl_set_parent(child, avl_parent(parent));
95 : 1262258 : avl_set_parent(parent, child);
96 : :
97 : 1262258 : return child;
98 : : }
99 : :
100 : 9694729 : INLINE struct avl_node* _rotate_RR(struct avl_node *parent,
101 : : int parent_bf,
102 : : int *child_bf,
103 : : int *height_delta)
104 : : // MUST ensure that parent_bf >= 0
105 : : {
106 : : int p_left, c_left, c_right;
107 : 9694729 : struct avl_node *child = parent->right;
108 : :
109 : : __AVL_DEBUG_RR(parent, child, parent_bf, *child_bf);
110 : :
111 [ + + ]: 9694729 : c_left = (child->left)?(1):(0);
112 [ + + ]: 9694729 : c_right = (child->right)?(1):(0);
113 [ + + ]: 9694729 : if (*child_bf < 0) {
114 : : // child->left > child->right
115 : 44219 : c_left = c_right - (*child_bf);
116 : 44219 : p_left = c_left + 1 - parent_bf;
117 [ + + ]: 44219 : if (height_delta)
118 [ - + ][ + - ]: 44208 : *height_delta = max(c_right, max(c_left, p_left)+1) - (c_left + 1);
[ - + ]
119 : :
120 : : } else {
121 : : // child->left <= child->right
122 : 9650510 : c_right = c_left + (*child_bf);
123 : 9650510 : p_left = c_right + 1 - parent_bf;
124 [ + + ]: 9650510 : if (height_delta)
125 [ - + ][ + - ]: 436490 : *height_delta = max(c_right, max(c_left, p_left)+1) - (c_right + 1);
[ - + ]
126 : :
127 : : }
128 [ + + ]: 9694729 : *child_bf = c_right - (max(c_left, p_left) + 1);
129 : 9694729 : avl_set_bf(parent, c_left - p_left);
130 : :
131 : 9694725 : parent->right = child->left;
132 [ + + ]: 9694725 : if (child->left)
133 : 5747964 : avl_set_parent(child->left, parent);
134 : 9694726 : child->left = parent;
135 : 9694726 : avl_set_parent(child, avl_parent(parent));
136 : 9694702 : avl_set_parent(parent, child);
137 : :
138 : 9694681 : return child;
139 : : }
140 : :
141 : 480698 : INLINE struct avl_node* _rotate_LR(struct avl_node *parent, int parent_bf)
142 : : {
143 : 480698 : int child_bf, height_delta = 0;
144 : 480698 : struct avl_node *child = parent->left;
145 : : struct avl_node *ret;
146 : :
147 [ + - ]: 480698 : if (child->right) {
148 : 480698 : child_bf = avl_bf(child->right);
149 : 480698 : parent->left = _rotate_RR(child, avl_bf(child), &child_bf, &height_delta);
150 : : } else {
151 : 0 : child_bf = avl_bf(child);
152 : : }
153 : :
154 : 480698 : ret = _rotate_LL(parent, parent_bf-height_delta, &child_bf, NULL);
155 : 480698 : avl_set_bf(ret, child_bf);
156 : 480698 : return ret;
157 : : }
158 : :
159 : 412628 : INLINE struct avl_node* _rotate_RL(struct avl_node *parent, int parent_bf)
160 : : {
161 : 412628 : int child_bf, height_delta = 0;
162 : 412628 : struct avl_node *child = parent->right;
163 : : struct avl_node *ret;
164 : :
165 [ + - ]: 412628 : if (child->left) {
166 : 412628 : child_bf = avl_bf(child->left);
167 : 412628 : parent->right = _rotate_LL(child, avl_bf(child), &child_bf, &height_delta);
168 : : } else {
169 : 0 : child_bf = avl_bf(child);
170 : : }
171 : :
172 : 412628 : ret = _rotate_RR(parent, parent_bf+height_delta, &child_bf, NULL);
173 : 412628 : avl_set_bf(ret, child_bf);
174 : 412628 : return ret;
175 : : }
176 : :
177 : : #define _get_balance(node) ((node)?(avl_bf(node)):(0))
178 : :
179 : 54146859 : struct avl_node* _balance_tree(struct avl_node *node, int bf)
180 : : {
181 : : int child_bf;
182 [ + - ]: 54146859 : int height_diff= _get_balance(node) + bf;
183 : :
184 [ + + ]: 54146859 : if (node) {
185 : : __AVL_DEBUG_BAL_BEGIN(node, bf, height_diff);
186 : :
187 [ + + ][ + - ]: 54146857 : if(height_diff < -1 && node->left) {
188 : : // balance left sub tree
189 [ + - ][ + + ]: 1699260 : if(_get_balance(node->left) <= 0) {
190 : 368932 : child_bf = avl_bf(node->left);
191 : 368932 : node = _rotate_LL(node, height_diff, &child_bf, NULL);
192 : 368932 : avl_set_bf(node, child_bf);
193 : : } else {
194 : 480698 : node = _rotate_LR(node, height_diff);
195 : : }
196 [ + + ][ + - ]: 53297227 : } else if(height_diff > 1 && node->right) {
197 : : // balance right sub tree
198 [ + - ][ + + ]: 18428003 : if(_get_balance(node->right) >= 0) {
199 : 8801383 : child_bf = avl_bf(node->right);
200 : 8801383 : node = _rotate_RR(node, height_diff, &child_bf, NULL);
201 : 8801366 : avl_set_bf(node, child_bf);
202 : : } else {
203 : 412628 : node = _rotate_RL(node, height_diff);
204 : : }
205 : : } else {
206 : 54146838 : avl_set_bf(node, avl_bf(node) + bf);
207 : : }
208 : :
209 : : __AVL_DEBUG_BAL_END(node);
210 : : }
211 : :
212 : 54146486 : return node;
213 : : }
214 : :
215 : 20068977 : struct avl_node* avl_first(struct avl_tree *tree)
216 : : {
217 : 20068977 : struct avl_node *p = NULL;
218 : 20068977 : struct avl_node *node = tree->root;
219 : :
220 [ + + ]: 67382908 : while(node) {
221 : 47313931 : p = node;
222 : 47313931 : node = node->left;
223 : : }
224 : 20068977 : return p;
225 : : }
226 : :
227 : 17 : struct avl_node* avl_last(struct avl_tree *tree)
228 : : {
229 : 17 : struct avl_node *p = NULL;
230 : 17 : struct avl_node *node = tree->root;
231 : :
232 [ + + ]: 76 : while(node) {
233 : 59 : p = node;
234 : 59 : node = node->right;
235 : : }
236 : 17 : return p;
237 : : }
238 : :
239 : 4860661 : struct avl_node* avl_next(struct avl_node *node)
240 : : {
241 [ - + ]: 4860661 : if (node == NULL) return NULL;
242 : :
243 : : #ifdef _AVL_NEXT_POINTER
244 : : return node->next;
245 : : #else
246 : :
247 : : struct avl_node *p;
248 : :
249 : : // smallest value of right subtree
250 [ + + ]: 4860661 : if (node->right) {
251 : 2327198 : p = node;
252 : 2327198 : node = node->right;
253 [ + + ]: 6814191 : while (node) {
254 : 4486993 : p = node;
255 : 4486993 : node = node->left;
256 : : }
257 : 2327198 : return p;
258 : : }
259 : :
260 : : // node does not have right child
261 [ + + ]: 2533463 : if (avl_parent(node)) {
262 : : // find first parent that has right child
263 : 2332867 : p = node;
264 : 2332867 : node = avl_parent(node);
265 [ + + ]: 4512427 : while(node) {
266 [ + + ]: 4508526 : if (node->left == p) {
267 : 2328966 : return node;
268 : : }
269 : 2179560 : p = node;
270 : 2179560 : node = avl_parent(node);
271 : : }
272 : : }
273 : : #endif
274 : 4860661 : return NULL;
275 : : }
276 : :
277 : 16517 : struct avl_node* avl_prev(struct avl_node *node)
278 : : {
279 [ - + ]: 16517 : if (node == NULL) return NULL;
280 : :
281 : : #ifdef _AVL_NEXT_POINTER
282 : : return node->prev;
283 : : #else
284 : :
285 : : struct avl_node *p;
286 : :
287 : : // largest value of left subtree
288 [ + + ]: 16517 : if (node->left) {
289 : 7617 : p = node;
290 : 7617 : node = node->left;
291 [ + + ]: 20246 : while (node) {
292 : 12629 : p = node;
293 : 12629 : node = node->right;
294 : : }
295 : 7617 : return p;
296 : : }
297 : :
298 : : // node does not have left child
299 [ + - ]: 8900 : if (avl_parent(node)) {
300 : : // find first parent that has left child
301 : 8900 : p = node;
302 : 8900 : node = avl_parent(node);
303 [ + + ]: 18587 : while(node) {
304 [ + + ]: 17119 : if (node->right == p) {
305 : 7432 : return node;
306 : : }
307 : 9687 : p = node;
308 : 9687 : node = avl_parent(node);
309 : : }
310 : : }
311 : : #endif
312 : 16517 : return NULL;
313 : : }
314 : :
315 : 50883837 : struct avl_node* avl_search(struct avl_tree *tree,
316 : : struct avl_node *node,
317 : : avl_cmp_func *func)
318 : : // exact match
319 : : {
320 : 50883837 : struct avl_node *p = tree->root;
321 : : int cmp;
322 : :
323 [ + + ]: 78948219 : while(p)
324 : : {
325 : 67801402 : cmp = func(p, node, tree->aux);
326 [ + + ]: 67820475 : if (cmp > 0) {
327 : 9691161 : p = p->left;
328 [ + + ]: 58129314 : }else if (cmp < 0){
329 : 18373221 : p = p->right;
330 : : }else {
331 : : // search success
332 : 39756093 : return p;
333 : : }
334 : : }
335 : : // search fail
336 : 50902910 : return NULL;
337 : : }
338 : :
339 : 2054 : struct avl_node* avl_search_greater(struct avl_tree *tree,
340 : : struct avl_node *node,
341 : : avl_cmp_func *func)
342 : : // if an exact match does not exist,
343 : : // return smallest node greater than NODE
344 : : {
345 : 2054 : struct avl_node *p = tree->root;
346 : 2054 : struct avl_node *pp = NULL;
347 : : int cmp;
348 : :
349 [ + + ]: 7774 : while(p)
350 : : {
351 : 6217 : cmp = func(p, node, tree->aux);
352 : 6217 : pp = p;
353 : :
354 [ + + ]: 6217 : if (cmp > 0) {
355 : 2988 : p = p->left;
356 [ + + ]: 3229 : }else if (cmp < 0){
357 : 2732 : p = p->right;
358 : : }else {
359 : : // search success
360 : 497 : return p;
361 : : }
362 : : }
363 : :
364 [ + + ]: 1557 : if (!pp) {
365 : 505 : return pp;
366 : : }
367 : :
368 : 1052 : cmp = func(pp, node, tree->aux);
369 [ + + ]: 1052 : if (cmp > 0) {
370 : 563 : return pp;
371 : : }else{
372 : 2054 : return avl_next(pp);
373 : : }
374 : : }
375 : :
376 : 1984 : struct avl_node* avl_search_smaller(struct avl_tree *tree,
377 : : struct avl_node *node,
378 : : avl_cmp_func *func)
379 : : // if an exact match does not exist,
380 : : // return greatest node smaller than NODE
381 : : {
382 : 1984 : struct avl_node *p = tree->root;
383 : 1984 : struct avl_node *pp = NULL;
384 : : int cmp;
385 : :
386 [ + + ]: 7580 : while(p)
387 : : {
388 : 6078 : cmp = func(p, node, tree->aux);
389 : 6078 : pp = p;
390 : :
391 [ + + ]: 6078 : if (cmp > 0) {
392 : 2650 : p = p->left;
393 [ + + ]: 3428 : }else if (cmp < 0){
394 : 2946 : p = p->right;
395 : : }else {
396 : : // search success
397 : 482 : return p;
398 : : }
399 : : }
400 : :
401 [ + + ]: 1502 : if (!pp) {
402 : 488 : return pp;
403 : : }
404 : :
405 : 1014 : cmp = func(pp, node, tree->aux);
406 [ + + ]: 1014 : if (cmp < 0) {
407 : 542 : return pp;
408 : : }else{
409 : 1984 : return avl_prev(pp);
410 : : }
411 : : }
412 : :
413 : 2896158 : void avl_init(struct avl_tree *tree, void *aux)
414 : : {
415 : 2896158 : tree->root = NULL;
416 : 2896158 : tree->aux = aux;
417 : 2896158 : }
418 : :
419 : 15224117 : struct avl_node* avl_insert(struct avl_tree *tree,
420 : : struct avl_node *node,
421 : : avl_cmp_func *func)
422 : : {
423 : : __AVL_DEBUG_INSERT(node);
424 : :
425 : 15224117 : struct avl_node *p=NULL,*cur;
426 : : int cmp, bf, bf_old;
427 : :
428 : 15224117 : cur = tree->root;
429 [ + + ]: 87032448 : while(cur)
430 : : {
431 : 71808347 : cmp = func(cur, node, tree->aux);
432 : 71808349 : p = cur;
433 : :
434 [ + + ]: 71808349 : if(cmp > 0) {
435 : 5100903 : cur = cur->left;
436 [ + + ]: 66707446 : }else if (cmp < 0){
437 : 66707428 : cur = cur->right;
438 : : }else {
439 : : // duplicated key -> return
440 : 18 : return cur;
441 : : }
442 : : }
443 : :
444 : 15224101 : avl_set_parent(node, p);
445 : 15224098 : avl_set_bf(node, 0);
446 : 15224169 : node->left = node->right = NULL;
447 : : #ifdef _AVL_NEXT_POINTER
448 : : node->prev = node->next = NULL;
449 : : #endif
450 : :
451 : : // P is parent node of CUR
452 [ + + ]: 15224169 : if(p) {
453 [ + + ]: 9125101 : if(func(p, node, tree->aux) > 0) {
454 : 1484521 : p->left = node;
455 : : #ifdef _AVL_NEXT_POINTER
456 : : node->next = p;
457 : : node->prev = p->prev;
458 : : if (p->prev) p->prev->next = node;
459 : : p->prev = node;
460 : : #endif
461 : :
462 : : }else {
463 : 7640229 : p->right = node;
464 : : #ifdef _AVL_NEXT_POINTER
465 : : node->prev = p;
466 : : node->next = p->next;
467 : : if (p->next) p->next->prev = node;
468 : : p->next = node;
469 : : #endif
470 : : }
471 : :
472 : : } else {
473 : : // no parent .. make NODE as root
474 : 6099068 : tree->root = node;
475 : : }
476 : :
477 : : // recursive balancing process .. scan from leaf to root
478 : 15223818 : bf = 0;
479 [ + - ]: 38642513 : while(node) {
480 : 38642558 : p = avl_parent(node);
481 : :
482 [ + + ]: 38642558 : if (p) {
483 : : // if parent exists
484 : 30144116 : bf_old = avl_bf(node);
485 : :
486 [ + + ]: 30144116 : if (p->right == node) {
487 : 26290952 : node = _balance_tree(node, bf);
488 : 26291267 : p->right = node;
489 : : }else {
490 : 3853164 : node = _balance_tree(node, bf);
491 : 3853162 : p->left = node;
492 : : }
493 : :
494 : : // calculate balance facter BF for parent
495 [ + + ][ + + ]: 30144429 : if (node->left == NULL && node->right == NULL) {
496 : : // leaf node
497 [ + + ]: 16765202 : if (p->left == node) bf = -1;
498 : 7640221 : else bf = 1;
499 : : } else {
500 : : // index ndoe
501 : 21019448 : bf = 0;
502 [ + + ]: 21019448 : if (_abs(bf_old) < _abs(avl_bf(node))) {
503 : : // if ABS of balance factor increases
504 : : // cascade to parent
505 [ + + ]: 14293695 : if (p->left == node) bf = -1;
506 : 30144329 : else bf = 1;
507 : : }
508 : : }
509 : :
510 [ + + ]: 8498442 : } else if(node == tree->root){
511 : 8498392 : tree->root = _balance_tree(tree->root, bf);
512 : 8498336 : break;
513 : : }
514 [ + + ]: 30144379 : if (bf == 0) break;
515 : :
516 : 23418695 : node = p;
517 : : }
518 : :
519 : : __AVL_DEBUG_DISPLAY(tree);
520 : :
521 : 15223993 : return node;
522 : : }
523 : :
524 : 15219095 : void avl_remove(struct avl_tree *tree,
525 : : struct avl_node *node)
526 : : {
527 : : __AVL_DEBUG_REMOVE(node);
528 : :
529 : : // not found
530 [ - + ]: 30438652 : if (node == NULL) return;
531 : :
532 : : struct avl_tree right_subtree;
533 : 15219095 : struct avl_node *p=NULL,*cur, *next=NULL;
534 : 15219095 : int bf = 0, bf_old;
535 : :
536 : :
537 : : #ifdef _AVL_NEXT_POINTER
538 : : if (node->prev) node->prev->next = node->next;
539 : : if (node->next) node->next->prev = node->prev;
540 : : #endif
541 : :
542 : : // find smallest node in right sub-tree
543 : 15219095 : right_subtree.root = node->right;
544 : 15219095 : next = avl_first(&right_subtree);
545 : :
546 [ + + ]: 15220103 : if (next) {
547 : : // 1. NEXT exists
548 [ + - ]: 4388874 : if (avl_parent(next)) {
549 [ + + ]: 4388886 : if (avl_parent(next) != node) {
550 : : // NODE is not NEXT's direct parent
551 : : // MUST ensure NEXT should be *left child* of its parent
552 : : // MUST ensure NEXT doesn't have right child
553 : 409603 : avl_parent(next)->left = next->right;
554 [ + + ]: 409603 : if (next->right)
555 : 57229 : avl_set_parent(next->right, avl_parent(next));
556 : : }
557 : : }
558 [ + + ]: 4388886 : if (avl_parent(node)) {
559 : : // replace NODE by NEXT
560 [ + + ]: 3661046 : if (avl_parent(node)->left == node) {
561 : 3335241 : avl_parent(node)->left = next;
562 : : } else {
563 : 325805 : avl_parent(node)->right = next;
564 : : }
565 : : }
566 : :
567 : : // re-link pointers
568 [ + + ]: 4388886 : if (node->right != next) {
569 : 409603 : next->right = node->right;
570 [ + - ]: 409603 : if (node->right) avl_set_parent(node->right, next);
571 : 409603 : cur = avl_parent(next);
572 : 409603 : bf = 1;
573 : : }else{
574 : 3979283 : cur = next;
575 : 3979283 : bf = -1;
576 : : }
577 : :
578 : 4388886 : next->left = node->left;
579 [ + + ]: 4388886 : if (node->left) avl_set_parent(node->left, next);
580 : 4388886 : avl_set_parent(next, avl_parent(node));
581 : :
582 : : // inherit NODE's balance factor
583 : 4388852 : avl_set_bf(next, avl_bf(node));
584 : :
585 : : } else {
586 : : // 2. NEXT == NULL (only when there's no right sub-tree)
587 : 10831229 : p = avl_parent(node);
588 [ + + ]: 10831229 : if (p) {
589 [ + + ]: 4404373 : if (p->left == node) {
590 : 3816639 : p->left = node->left;
591 : 3816639 : bf = 1;
592 : : } else {
593 : 587734 : p->right = node->left;
594 : 587734 : bf = -1;
595 : : }
596 : : }
597 [ + + ]: 10831229 : if (node->left)
598 : 467437 : avl_set_parent(node->left, p);
599 : :
600 : 10831209 : cur = avl_parent(node);
601 : : }
602 : :
603 : : // reset root
604 [ + + ]: 15218743 : if (tree->root == node) {
605 : 7155031 : tree->root = next;
606 [ + + ]: 7155031 : if (next == NULL) {
607 [ + + ]: 6427522 : if (node->left) tree->root = node->left;
608 : : }
609 : : }
610 : :
611 : : // recursive balancing process .. scan from CUR to root
612 [ + + ]: 21931110 : while(cur) {
613 : 15504478 : p = avl_parent(cur);
614 [ + + ]: 15504478 : if (p) {
615 : : // if parent exists
616 : 13291054 : bf_old = avl_bf(cur);
617 : :
618 [ + + ]: 13291054 : if (p->right == cur) {
619 : 1086190 : cur = _balance_tree(cur, bf);
620 : 1087511 : p->right = cur;
621 : : }else {
622 : 12204864 : cur = _balance_tree(cur, bf);
623 : 12204642 : p->left = cur;
624 : : }
625 : :
626 : : // calculate balance facter BF for parent
627 [ + + ][ + + ]: 13292153 : if (cur->left == NULL && cur->right == NULL) {
628 : : // leaf node
629 [ + + ]: 3709116 : if (p->left == cur) bf = 1;
630 : 241430 : else bf = -1;
631 : : } else {
632 : : // index ndoe
633 : 9824467 : bf = 0;
634 [ + + ]: 9824467 : if (_abs(bf_old) > _abs(avl_bf(cur))) {
635 : : // if ABS of balance factor decreases
636 : : // cascade to parent
637 [ + + ]: 3244415 : if (p->left == cur) bf = 1;
638 : 13291870 : else bf = -1;
639 : : }
640 : : }
641 : :
642 [ + + ]: 2213424 : } else if(cur == tree->root){
643 : 2212784 : tree->root = _balance_tree(tree->root, bf);
644 : 2212782 : break;
645 : : }
646 [ + + ]: 13292510 : if (bf == 0) break;
647 : :
648 : 6712367 : cur = p;
649 : : }
650 : :
651 : : __AVL_DEBUG_DISPLAY(tree);
652 : : }
653 : :
|
