Subversion Repositories HelenOS

Rev

Rev 2461 | Rev 2497 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2416 mencl 1
/*
2421 mencl 2
 * Copyright (c) 2007 Vojtech Mencl
2416 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   AVL tree implementation.
36
 *
37
 * This file implements AVL tree type and operations.
38
 *
39
 * Implemented AVL tree has the following properties:
2496 jermar 40
 * @li It is a binary search tree with non-unique keys.
41
 * @li Difference of heights of the left and the right subtree of every node is
42
 *     one at maximum.
2416 mencl 43
 *
2496 jermar 44
 * Every node has a pointer to its parent which allows insertion of multiple
45
 * identical keys into the tree.
2416 mencl 46
 *
2496 jermar 47
 * Be careful when using this tree because of the base atribute which is added
48
 * to every inserted node key. There is no rule in which order nodes with the
49
 * same key are visited.
2416 mencl 50
 */
51
 
52
#include <adt/avl.h>
53
#include <debug.h>
54
 
55
 
2496 jermar 56
#define LEFT    0
57
#define RIGHT   1
2416 mencl 58
 
59
 
2496 jermar 60
/** Search for the first occurence of the given key in an AVL tree.
2416 mencl 61
 *
62
 * @param t AVL tree.
63
 * @param key Key to be searched.
64
 *
2496 jermar 65
 * @return Pointer to a node or NULL if there is no such key.
2416 mencl 66
 */
67
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
68
{
69
    avltree_node_t *p;
70
 
71
    /*
72
     * Iteratively descend to the leaf that can contain the searched key.
73
     */
74
    p = t->root;
75
    while (p != NULL) {
76
        if (p->key > key)
77
            p = p->lft;
78
        else if (p->key < key)
79
            p = p->rgt;
2496 jermar 80
        else
2416 mencl 81
            return p;
82
    }
83
    return NULL;
84
}
85
 
86
 
2496 jermar 87
/** Find the node with the smallest key in an AVL tree.
2421 mencl 88
 *
89
 * @param t AVL tree.
90
 *
2496 jermar 91
 * @return Pointer to a node or NULL if there is no node in the tree.
2421 mencl 92
 */
93
avltree_node_t *avltree_find_min(avltree_t *t)
94
{
95
    avltree_node_t *p = t->root;
96
 
97
    /*
2496 jermar 98
     * Check whether the tree is empty.
2421 mencl 99
     */
2496 jermar 100
    if (!p)
101
        return NULL;
2421 mencl 102
 
103
    /*
104
     * Iteratively descend to the leftmost leaf in the tree.
105
     */
106
    while (p->lft != NULL)
107
        p = p->lft;
108
 
109
    return p;
110
}
111
 
2416 mencl 112
/** Insert new node into AVL tree.
113
 *
114
 * @param t AVL tree.
115
 * @param newnode New node to be inserted.
116
 */
117
void avltree_insert(avltree_t *t, avltree_node_t *newnode)
118
{  
119
    avltree_node_t *par;
120
    avltree_node_t *gpa;
121
    avltree_node_t *top;
122
    avltree_node_t **dpc;
123
    uint64_t key;
124
 
125
    ASSERT(t);
126
    ASSERT(newnode);
127
 
128
    /*
129
     * Creating absolute key.
130
     */
131
    key = newnode->key + t->base;
132
 
133
    /*
2496 jermar 134
     * Iteratively descend to the leaf that can contain the new node.
2416 mencl 135
     * Last node with non-zero balance in the way to leaf is stored as top -
2496 jermar 136
     * it is a place of possible inbalance.
2416 mencl 137
     */
138
    dpc = &t->root;
139
    gpa = NULL;
140
    top = t->root;
2421 mencl 141
    while ((par = (*dpc)) != NULL) {
2416 mencl 142
        if (par->balance != 0) {
143
            top = par;
144
        }
145
        gpa = par;
2496 jermar 146
        dpc = par->key > key ? &par->lft: &par->rgt;
2416 mencl 147
    }
148
 
149
    /*
150
     * Initialize new node.
151
     */
152
    newnode->key = key;
153
    newnode->lft = NULL;
154
    newnode->rgt = NULL;
155
    newnode->par = gpa;
156
    newnode->balance = 0;
157
 
158
    /*
2496 jermar 159
     * Insert first node into the empty tree.
2416 mencl 160
     */
161
    if (t->root == NULL) {
162
        *dpc = newnode;
163
        return;
164
    }
165
 
166
    /*
167
     * Insert new node into previously found leaf place.
168
     */
169
    *dpc = newnode;
170
 
171
    /*
2496 jermar 172
     * If the tree contains one node - end.
2416 mencl 173
     */
2496 jermar 174
    if (top == NULL)
175
        return;
2416 mencl 176
 
177
    /*
2496 jermar 178
     * Store pointer of top's father which points to the node with
179
     * potentially broken balance (top).
2416 mencl 180
     */
2496 jermar 181
    if (top->par == NULL) {
2416 mencl 182
        dpc = &t->root;
2496 jermar 183
    } else {
2416 mencl 184
        if (top->par->lft == top)
2496 jermar 185
            dpc = &top->par->lft;
2416 mencl 186
        else
2496 jermar 187
            dpc = &top->par->rgt;
188
    }
2416 mencl 189
 
190
    /*
2496 jermar 191
     * Repair all balances on the way from top node to the newly inserted
192
     * node.
2416 mencl 193
     */
194
    par = top;
195
    while (par != newnode) {
196
        if (par->key > key) {
197
            par->balance--;
198
            par = par->lft;
199
        } else {
200
            par->balance++;
201
            par = par->rgt;
202
        }
203
    }
204
 
205
    /*
2496 jermar 206
     * To balance the tree, we must check and balance top node.
2416 mencl 207
     */
208
    if (top->balance == -2) {
209
        par = top->lft;
210
        if (par->balance == -1) {
211
            /*
212
             * LL rotation.
213
             */
214
            top->lft = par->rgt;
2496 jermar 215
            if (top->lft != NULL)
216
                top->lft->par = top;
2416 mencl 217
            par->par = top->par;
218
            top->par = par;
219
            par->rgt = top;
220
            par->balance = top->balance = 0;
221
            *dpc = par;
222
        } else {
223
            /*
224
             * LR rotation.
225
             */
226
            ASSERT(par->balance == 1);
227
 
228
            gpa = par->rgt;
229
            par->rgt = gpa->lft;
2496 jermar 230
            if (gpa->lft != NULL)
231
                gpa->lft->par = par;
2416 mencl 232
            gpa->lft = par;
233
            par->par = gpa;
234
            top->lft = gpa->rgt;
2496 jermar 235
            if (gpa->rgt != NULL)
236
                gpa->rgt->par = top;
2416 mencl 237
            gpa->rgt = top;
238
            gpa->par = top->par;
239
            top->par = gpa;
240
 
241
            if (gpa->balance == -1) {
242
                par->balance = 0;
243
                top->balance = 1;
244
            } else if (gpa->balance == 0) {
245
                par->balance = top->balance = 0;
246
            } else {
247
                par->balance = -1;
248
                top->balance = 0;
249
            }
250
            gpa->balance = 0;
251
            *dpc = gpa;
252
        }
253
    } else if (top->balance == 2) {
254
        par = top->rgt;
255
        if (par->balance == 1) {
256
            /*
257
             * RR rotation.
258
             */
259
            top->rgt = par->lft;
2496 jermar 260
            if (top->rgt != NULL)
261
                top->rgt->par = top;
2416 mencl 262
            par->par = top->par;
263
            top->par = par;
264
            par->lft = top;
265
            par->balance = top->balance = 0;
266
            *dpc = par;
267
        } else {
268
            /*
269
             * RL rotation.
270
             */
271
            ASSERT(par->balance == -1);
272
 
273
            gpa = par->lft;
274
            par->lft = gpa->rgt;
2496 jermar 275
            if (gpa->rgt != NULL)
276
                gpa->rgt->par = par;
2416 mencl 277
            gpa->rgt = par;
278
            par->par = gpa;
279
            top->rgt = gpa->lft;
2496 jermar 280
            if (gpa->lft != NULL)
281
                gpa->lft->par = top;
2416 mencl 282
            gpa->lft = top;
283
            gpa->par = top->par;
284
            top->par = gpa;
285
 
286
            if (gpa->balance == 1) {
287
                par->balance = 0;
288
                top->balance = -1;
289
            } else if (gpa->balance == 0) {
290
                par->balance = top->balance = 0;
291
            } else {
292
                par->balance = 1;
293
                top->balance = 0;
294
            }
295
            gpa->balance = 0;
296
            *dpc = gpa;
297
        }
298
    } else {
299
        /*
300
         * Balance is not broken, insertion is finised.
301
         */
302
        return;
303
    }
304
 
305
}
306
 
2496 jermar 307
/** Delete a node from the AVL tree.
2416 mencl 308
 *
2496 jermar 309
 * Because multiple identical keys are allowed, the parent pointers are
310
 * essential during deletion.
2416 mencl 311
 *
312
 * @param t AVL tree structure.
2496 jermar 313
 * @param node Address of the node which will be deleted.
2416 mencl 314
 */
315
void avltree_delete(avltree_t *t, avltree_node_t *node)
316
{
317
    avltree_node_t *cur;
318
    avltree_node_t *par;
319
    avltree_node_t *gpa;
320
    uint8_t dir;
321
 
322
    ASSERT(t);
323
    ASSERT(node);
324
 
325
    if (node->lft == NULL) {
326
        if (node->rgt) {
327
            /*
2496 jermar 328
             * Replace the node with its only right son.
2416 mencl 329
             *
2496 jermar 330
             * Balance of the right son will be repaired in the
331
             * balancing cycle.
2416 mencl 332
             */
333
            cur = node->rgt;
334
            cur->par = node->par;
335
            gpa = cur;
2496 jermar 336
            dir = RIGHT;
2416 mencl 337
            cur->balance = node->balance;
338
        } else {
339
            if (node->par == NULL) {
340
                /*
2496 jermar 341
                 * The tree has only one node - it will become
342
                 * an empty tree and the balancing can end.
2416 mencl 343
                 */
344
                t->root = NULL;
345
                return;
346
            }
347
            /*
2496 jermar 348
             * The node has no child, it will be deleted with no
349
             * substitution.
2416 mencl 350
             */
351
            gpa = node->par;
352
            cur = NULL;
2496 jermar 353
            dir = (gpa->lft == node) ? LEFT: RIGHT;
2416 mencl 354
        }
355
    } else {
356
        /*
2496 jermar 357
         * The node has left and right son. Find a node with the
358
         * smallest key in the left subtree and replace the deleted node
359
         * with that node.
2416 mencl 360
         */
361
        for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
362
            ;
2496 jermar 363
 
2416 mencl 364
        if (cur != node->lft) {
365
            /*
2496 jermar 366
             * The rightmost node of the deleted node's left subtree
367
             * was found. Replace the deleted node with this node.
368
             * Cutting off of the found node has two cases that
369
             * depend on its left son.
2416 mencl 370
             */
371
            if (cur->lft) {
372
                /*
2496 jermar 373
                 * The found node has a left son.
2416 mencl 374
                 */
375
                gpa = cur->lft;
376
                gpa->par = cur->par;
2496 jermar 377
                dir = LEFT;
2416 mencl 378
                gpa->balance = cur->balance;
379
            } else {
2496 jermar 380
                dir = RIGHT;
2416 mencl 381
                gpa = cur->par;
382
            }
383
            cur->par->rgt = cur->lft;
384
            cur->lft = node->lft;
385
            cur->lft->par = cur;
386
        } else {
387
            /*
2496 jermar 388
             * The left son of the node hasn't got a right son. The
389
             * left son will take the deleted node's place.
2416 mencl 390
             */
2496 jermar 391
            dir = LEFT;
2416 mencl 392
            gpa = cur;
393
        }
2496 jermar 394
        if (node->rgt)
395
            node->rgt->par = cur;
2416 mencl 396
        cur->rgt = node->rgt;
397
        cur->balance = node->balance;
398
        cur->par = node->par;
399
    }
400
 
401
    /*
2496 jermar 402
     * Repair the parent node's pointer which pointed previously to the
403
     * deleted node.
2416 mencl 404
     */
405
    if (node->par == NULL) {
406
        t->root = cur;
407
    } else {
408
        if (node->par->lft == node) {
409
            node->par->lft = cur;
410
        } else {
411
            node->par->rgt = cur;
412
        }
413
    }
414
 
415
    /*
2496 jermar 416
     * Repair cycle which repairs balances of nodes on the way from from the
417
     * cut-off node up to the root.
2416 mencl 418
     */
2496 jermar 419
    for (;;) {
420
        if (dir == LEFT) {
2416 mencl 421
            /*
2496 jermar 422
             * Deletion was made in the left subtree.
2416 mencl 423
             */
424
            gpa->balance++;
2496 jermar 425
            if (gpa->balance == 1) {
2416 mencl 426
                /*
2496 jermar 427
                 * Stop balancing, the tree is balanced.
2416 mencl 428
                 */
429
                break;
2496 jermar 430
            } else if (gpa->balance == 2) {
2416 mencl 431
                /*
2496 jermar 432
                 * Bad balance, heights of left and right
433
                 * subtrees differ more than by one.
2416 mencl 434
                 */
435
                par = gpa->rgt;
436
 
437
                if (par->balance == -1) {
438
                    /*
439
                     * RL rotation.
440
                     */
441
 
442
                    cur = par->lft;
443
                    par->lft = cur->rgt;
444
                    cur->rgt = par;
445
                    gpa->rgt = cur->lft;
446
                    cur->lft = gpa;
447
 
448
                    /*
2496 jermar 449
                     * Repair balances and paternity of
450
                     * children, depending on the balance
451
                     * factor of the grand child (cur).
2416 mencl 452
                     */
2496 jermar 453
                    if (cur->balance == 1) {
2416 mencl 454
                        par->balance = 0;
455
                        gpa->balance = -1;
2496 jermar 456
                        if (gpa->rgt)
457
                            gpa->rgt->par = gpa;
2416 mencl 458
                        par->lft->par = par;
459
                    } else if (cur->balance == 0) {
460
                        par->balance = gpa->balance = 0;
2496 jermar 461
                        if (gpa->rgt)
462
                            gpa->rgt->par = gpa;
463
                        if (par->lft)
464
                            par->lft->par = par;
2416 mencl 465
                    } else {
2496 jermar 466
                        par->balance = 1;
2416 mencl 467
                        gpa->balance = 0;
2496 jermar 468
                        if (par->lft)
469
                            par->lft->par = par;
2416 mencl 470
                        gpa->rgt->par = gpa;
471
                    }
472
                    cur->balance = 0;
473
 
474
                    /*
475
                     * Repair paternity.
476
                     */
477
                    cur->par = gpa->par;
478
                    gpa->par = cur;
479
                    par->par = cur;
480
 
481
                    /*
2496 jermar 482
                     * Repair the pointer which pointed to
483
                     * the balanced node. If it was root
484
                     * then the balancing is finished.
485
                     * Otherwise continue with the next
486
                     * iteration (parent node).
2416 mencl 487
                     */
488
                    if (cur->par == NULL) {
489
                        t->root = cur; 
490
                        break;
2496 jermar 491
                    } else {
2416 mencl 492
                        if (cur->par->lft == gpa) {
493
                            cur->par->lft = cur;
2496 jermar 494
                            dir = LEFT;
2416 mencl 495
                        } else {
496
                            cur->par->rgt = cur;
2496 jermar 497
                            dir = RIGHT;
2416 mencl 498
                        }
2496 jermar 499
                    }
2416 mencl 500
                    gpa = cur->par;
501
                } else {
502
                    /*
503
                     * RR rotation.
504
                     */
505
 
506
                    gpa->rgt = par->lft;
2496 jermar 507
                    if (par->lft)
508
                        par->lft->par = gpa;
2416 mencl 509
                    par->lft = gpa;
510
 
511
                    /*
512
                     * Repair paternity.
513
                     */
514
                    par->par = gpa->par;
515
                    gpa->par = par;
516
 
517
                    if (par->balance == 0) {
518
                        /*
2496 jermar 519
                         * The right child of the
520
                         * balanced node is balanced,
521
                         * after RR rotation is done,
522
                         * the whole tree will be
523
                         * balanced.
2416 mencl 524
                         */
525
                        par->balance = -1;
2496 jermar 526
                        gpa->balance = 1;
2416 mencl 527
 
528
                        /*
2496 jermar 529
                         * Repair the pointer which
530
                         * pointed to the balanced node
531
                         * and finish balancing.
2416 mencl 532
                         */
533
                        if (par->par == NULL) {
534
                            t->root = par; 
2496 jermar 535
                        } else {
536
                            if (par->par->lft ==
537
                                gpa) {
538
                                par->par->lft =
539
                                    par;
2416 mencl 540
                            } else {
2496 jermar 541
                                par->par->rgt =
542
                                    par;
2416 mencl 543
                            }
2496 jermar 544
                        }
2416 mencl 545
                        break;
546
                    } else {
547
                        par->balance = gpa->balance = 0;
548
                        /*
2496 jermar 549
                         * Repair the pointer which
550
                         * pointed to the balanced node.
551
                         * If it was root then balancing
552
                         * is finished. Otherwise
553
                         * continue with the next
554
                         * iteration (parent node).
2416 mencl 555
                         */
556
                        if (par->par == NULL) {
557
                            t->root = par; 
558
                            break;
2496 jermar 559
                        } else {   
560
                            if (par->par->lft ==
561
                                gpa) {
562
                                par->par->lft =
563
                                    par;
564
                                dir = LEFT;
2416 mencl 565
                            } else {
2496 jermar 566
                                par->par->rgt =
567
                                    par;
568
                                dir = RIGHT;
2416 mencl 569
                            }
570
                        }
571
                    }
572
                    gpa = par->par;
573
                }
574
            } else {
575
                /*
2496 jermar 576
                 * Repair the pointer which pointed to the
577
                 * balanced node. If it was root then balancing
578
                 * is finished else continue with the next
579
                 * iteration (parent node).
2416 mencl 580
                 */
2496 jermar 581
                if (!gpa->par)
582
                    break;
2416 mencl 583
 
584
                if (gpa->par->lft == gpa) {
2496 jermar 585
                    dir = LEFT;
2416 mencl 586
                } else {
2496 jermar 587
                    dir = RIGHT;
2416 mencl 588
                }
589
                gpa = gpa->par;
590
            }
591
        } else {
592
            /*
2496 jermar 593
             * Deletion was made in the right subtree.
2416 mencl 594
             */
595
            gpa->balance--;
596
            if (gpa->balance == -1) {
597
                /*
2496 jermar 598
                 * Stop balancing, the tree is balanced.
2416 mencl 599
                 */
600
                break;
601
            } else if (gpa->balance == -2) {
602
                /*
2496 jermar 603
                 * Bad balance, heights of left and right
604
                 * subtrees differ more than by one.
2416 mencl 605
                 */
606
                par = gpa->lft;
607
 
2496 jermar 608
                if (par->balance == 1) {
2416 mencl 609
                    /*
610
                     * LR rotation.
611
                     */
612
 
613
                    cur = par->rgt;
614
                    par->rgt = cur->lft;
615
                    cur->lft = par;
616
                    gpa->lft = cur->rgt;
617
                    cur->rgt = gpa;
618
 
619
                    /*
2496 jermar 620
                     * Repair balances and paternity of
621
                     * children, depending on the balance
622
                     * factor of the grand child (cur).
2416 mencl 623
                     */
624
                    if (cur->balance == -1) {
625
                        par->balance = 0;
2496 jermar 626
                        gpa->balance = 1;
627
                        if (gpa->lft)
628
                            gpa->lft->par = gpa;
2416 mencl 629
                        par->rgt->par = par;
630
                    } else if (cur->balance == 0) {
631
                        par->balance = gpa->balance = 0;
2496 jermar 632
                        if (gpa->lft)
633
                            gpa->lft->par = gpa;
634
                        if (par->rgt)
635
                            par->rgt->par = par;
2416 mencl 636
                    } else {
637
                        par->balance = -1;
638
                        gpa->balance = 0;
2496 jermar 639
                        if (par->rgt)
640
                            par->rgt->par = par;
2416 mencl 641
                        gpa->lft->par = gpa;
642
                    }
643
                    cur->balance = 0;
644
 
645
                    /*
646
                     * Repair paternity.
647
                     */
648
                    cur->par = gpa->par;
649
                    gpa->par = cur;
650
                    par->par = cur;
651
 
652
                    /*
2496 jermar 653
                     * Repair the pointer which pointed to
654
                     * the balanced node. If it was root
655
                     * then balancing is finished. Otherwise
656
                     * continue with the next iteration
657
                     * (parent node).
2416 mencl 658
                     */
659
                    if (cur->par == NULL) {
660
                        t->root = cur; 
661
                        break;
2496 jermar 662
                    } else {
2416 mencl 663
                        if (cur->par->lft == gpa) {
664
                            cur->par->lft = cur;
2496 jermar 665
                            dir = LEFT;
2416 mencl 666
                        } else {
667
                            cur->par->rgt = cur;
2496 jermar 668
                            dir = RIGHT;
2416 mencl 669
                        }
2496 jermar 670
                    }
2416 mencl 671
                    gpa = cur->par;
672
                } else {
673
                    /*
674
                     * LL rotation.
675
                     */
676
 
677
                    gpa->lft = par->rgt;
2496 jermar 678
                    if (par->rgt)
679
                        par->rgt->par = gpa;
2416 mencl 680
                    par->rgt = gpa;
681
                    /*
682
                     * Repair paternity.
683
                     */
684
                    par->par = gpa->par;
685
                    gpa->par = par;
686
 
687
                    if (par->balance == 0) {
688
                        /*
2496 jermar 689
                         * The left child of the
690
                         * balanced node is balanced,
691
                         * after LL rotation is done,
692
                         * the whole tree will be
693
                         * balanced.
2416 mencl 694
                         */
2496 jermar 695
                        par->balance = 1;
2416 mencl 696
                        gpa->balance = -1;
697
 
698
                        /*
2496 jermar 699
                         * Repair the pointer which
700
                         * pointed to the balanced node
701
                         * and finish balancing.
2416 mencl 702
                         */
703
                        if (par->par == NULL) {
704
                            t->root = par;
2496 jermar 705
                        } else {
706
                            if (par->par->lft ==
707
                                gpa) {
708
                                par->par->lft =
709
                                    par;
2416 mencl 710
                            } else {
2496 jermar 711
                                par->par->rgt =
712
                                    par;
2416 mencl 713
                            }
2496 jermar 714
                        }
2416 mencl 715
                        break;
716
                    } else {
717
                        par->balance = gpa->balance = 0;
718
 
719
                        /*
2496 jermar 720
                         * Repair the pointer which
721
                         * pointed to the balanced node.
722
                         * If it was root then balancing
723
                         * is finished. Otherwise
724
                         * continue with the next
725
                         * iteration (parent node).
2416 mencl 726
                         */
727
                        if (par->par == NULL) {
728
                            t->root = par;
729
                            break;
730
                        } else {
2496 jermar 731
                            if (par->par->lft ==
732
                                gpa) {
733
                                par->par->lft =
734
                                    par;
735
                                dir = LEFT;
2416 mencl 736
                            } else {
2496 jermar 737
                                par->par->rgt =
738
                                    par;
739
                                dir = RIGHT;
2416 mencl 740
                            }
741
                        }
742
                    }
743
                    gpa = par->par;
744
                }
745
            } else {
746
                /*
2496 jermar 747
                 * Repair the pointer which pointed to the
748
                 * balanced node. If it was root then balancing
749
                 * is finished. Otherwise continue with the next
750
                 * iteration (parent node).
2416 mencl 751
                 */
2496 jermar 752
                if (!gpa->par)
753
                    break;
2416 mencl 754
 
755
                if (gpa->par->lft == gpa) {
2496 jermar 756
                    dir = LEFT;
2416 mencl 757
                } else {
2496 jermar 758
                    dir = RIGHT;
2416 mencl 759
                }
760
                gpa = gpa->par;
761
            }
762
        }
763
    }
764
}
765
 
766
 
2496 jermar 767
/** Delete a node with the smallest key from the AVL tree.
2416 mencl 768
 *
769
 * @param t AVL tree structure.
770
 */
2421 mencl 771
bool avltree_delete_min(avltree_t *t)
2416 mencl 772
{
773
    avltree_node_t *node;
774
 
775
    /*
2496 jermar 776
     * Start searching for the smallest key in the tree starting in the root
777
     * node and continue in cycle to the leftmost node in the tree (which
778
     * must have the smallest key).
2416 mencl 779
     */
2496 jermar 780
 
2416 mencl 781
    node = t->root;
2496 jermar 782
    if (!node)
783
        return false;
2416 mencl 784
 
785
    while (node->lft != NULL)
786
        node = node->lft;
787
 
2496 jermar 788
    avltree_delete(t, node);
2416 mencl 789
 
790
    return true;
791
}
2496 jermar 792
 
793
/** @}
794
 */