Subversion Repositories HelenOS

Rev

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