Subversion Repositories HelenOS

Rev

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

  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   AVL tree implementation.
  36.  *
  37.  * This file implements AVL tree type and operations.
  38.  *
  39.  * Implemented AVL tree has the following properties:
  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.
  43.  *
  44.  * Every node has a pointer to its parent which allows insertion of multiple
  45.  * identical keys into the tree.
  46.  *
  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.
  50.  */
  51.  
  52. #include <adt/avl.h>
  53. #include <debug.h>
  54.  
  55.  
  56. #define LEFT    0
  57. #define RIGHT   1
  58.  
  59.  
  60. /** Search for the first occurence of the given key in an AVL tree.
  61.  *
  62.  * @param t AVL tree.
  63.  * @param key Key to be searched.
  64.  *
  65.  * @return Pointer to a node or NULL if there is no such key.
  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;
  80.         else
  81.             return p;
  82.     }
  83.     return NULL;
  84. }
  85.  
  86.  
  87. /** Find the node with the smallest key in an AVL tree.
  88.  *
  89.  * @param t AVL tree.
  90.  *
  91.  * @return Pointer to a node or NULL if there is no node in the tree.
  92.  */
  93. avltree_node_t *avltree_find_min(avltree_t *t)
  94. {
  95.     avltree_node_t *p = t->root;
  96.    
  97.     /*
  98.      * Check whether the tree is empty.
  99.      */
  100.     if (!p)
  101.         return NULL;
  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.  
  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.     /*
  134.      * Iteratively descend to the leaf that can contain the new node.
  135.      * Last node with non-zero balance in the way to leaf is stored as top -
  136.      * it is a place of possible inbalance.
  137.      */
  138.     dpc = &t->root;
  139.     gpa = NULL;
  140.     top = t->root;
  141.     while ((par = (*dpc)) != NULL) {
  142.         if (par->balance != 0) {
  143.             top = par;
  144.         }
  145.         gpa = par;
  146.         dpc = par->key > key ? &par->lft: &par->rgt;
  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.     /*
  159.      * Insert first node into the empty tree.
  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.     /*
  172.      * If the tree contains one node - end.
  173.      */
  174.     if (top == NULL)
  175.         return;
  176.  
  177.     /*
  178.      * Store pointer of top's father which points to the node with
  179.      * potentially broken balance (top).
  180.      */
  181.     if (top->par == NULL) {
  182.         dpc = &t->root;
  183.     } else {
  184.         if (top->par->lft == top)
  185.             dpc = &top->par->lft;
  186.         else
  187.             dpc = &top->par->rgt;
  188.     }
  189.  
  190.     /*
  191.      * Repair all balances on the way from top node to the newly inserted
  192.      * node.
  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.     /*
  206.      * To balance the tree, we must check and balance top node.
  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;
  215.             if (top->lft != NULL)
  216.                 top->lft->par = top;
  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;
  230.             if (gpa->lft != NULL)
  231.                 gpa->lft->par = par;
  232.             gpa->lft = par;
  233.             par->par = gpa;
  234.             top->lft = gpa->rgt;
  235.             if (gpa->rgt != NULL)
  236.                 gpa->rgt->par = top;
  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;
  260.             if (top->rgt != NULL)
  261.                 top->rgt->par = top;
  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;
  275.             if (gpa->rgt != NULL)
  276.                 gpa->rgt->par = par;
  277.             gpa->rgt = par;
  278.             par->par = gpa;
  279.             top->rgt = gpa->lft;
  280.             if (gpa->lft != NULL)
  281.                 gpa->lft->par = top;
  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.  
  307. /** Delete a node from the AVL tree.
  308.  *
  309.  * Because multiple identical keys are allowed, the parent pointers are
  310.  * essential during deletion.
  311.  *
  312.  * @param t AVL tree structure.
  313.  * @param node Address of the node which will be deleted.
  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.             /*
  328.              * Replace the node with its only right son.
  329.              *
  330.              * Balance of the right son will be repaired in the
  331.              * balancing cycle.
  332.              */
  333.             cur = node->rgt;
  334.             cur->par = node->par;
  335.             gpa = cur;
  336.             dir = RIGHT;
  337.             cur->balance = node->balance;
  338.         } else {
  339.             if (node->par == NULL) {
  340.                 /*
  341.                  * The tree has only one node - it will become
  342.                  * an empty tree and the balancing can end.
  343.                  */
  344.                 t->root = NULL;
  345.                 return;
  346.             }
  347.             /*
  348.              * The node has no child, it will be deleted with no
  349.              * substitution.
  350.              */
  351.             gpa = node->par;
  352.             cur = NULL;
  353.             dir = (gpa->lft == node) ? LEFT: RIGHT;
  354.         }
  355.     } else {
  356.         /*
  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.
  360.          */
  361.         for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
  362.             ;
  363.  
  364.         if (cur != node->lft) {
  365.             /*
  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.
  370.              */
  371.             if (cur->lft) {
  372.                 /*
  373.                  * The found node has a left son.
  374.                  */
  375.                 gpa = cur->lft;
  376.                 gpa->par = cur->par;
  377.                 dir = LEFT;
  378.                 gpa->balance = cur->balance;
  379.             } else {
  380.                 dir = RIGHT;
  381.                 gpa = cur->par;
  382.             }
  383.             cur->par->rgt = cur->lft;
  384.             cur->lft = node->lft;
  385.             cur->lft->par = cur;
  386.         } else {
  387.             /*
  388.              * The left son of the node hasn't got a right son. The
  389.              * left son will take the deleted node's place.
  390.              */
  391.             dir = LEFT;
  392.             gpa = cur;
  393.         }
  394.         if (node->rgt)
  395.             node->rgt->par = cur;
  396.         cur->rgt = node->rgt;
  397.         cur->balance = node->balance;
  398.         cur->par = node->par;
  399.     }
  400.    
  401.     /*
  402.      * Repair the parent node's pointer which pointed previously to the
  403.      * deleted node.
  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.     /*
  416.      * Repair cycle which repairs balances of nodes on the way from from the
  417.      * cut-off node up to the root.
  418.      */
  419.     for (;;) {
  420.         if (dir == LEFT) {
  421.             /*
  422.              * Deletion was made in the left subtree.
  423.              */
  424.             gpa->balance++;
  425.             if (gpa->balance == 1) {
  426.                 /*
  427.                  * Stop balancing, the tree is balanced.
  428.                  */
  429.                 break;
  430.             } else if (gpa->balance == 2) {
  431.                 /*
  432.                  * Bad balance, heights of left and right
  433.                  * subtrees differ more than by one.
  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.                     /*
  449.                      * Repair balances and paternity of
  450.                      * children, depending on the balance
  451.                      * factor of the grand child (cur).
  452.                      */
  453.                     if (cur->balance == 1) {
  454.                         par->balance = 0;
  455.                         gpa->balance = -1;
  456.                         if (gpa->rgt)
  457.                             gpa->rgt->par = gpa;
  458.                         par->lft->par = par;
  459.                     } else if (cur->balance == 0) {
  460.                         par->balance = gpa->balance = 0;
  461.                         if (gpa->rgt)
  462.                             gpa->rgt->par = gpa;
  463.                         if (par->lft)
  464.                             par->lft->par = par;
  465.                     } else {
  466.                         par->balance = 1;
  467.                         gpa->balance = 0;
  468.                         if (par->lft)
  469.                             par->lft->par = par;
  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.                     /*
  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).
  487.                      */
  488.                     if (cur->par == NULL) {
  489.                         t->root = cur; 
  490.                         break;
  491.                     } else {
  492.                         if (cur->par->lft == gpa) {
  493.                             cur->par->lft = cur;
  494.                             dir = LEFT;
  495.                         } else {
  496.                             cur->par->rgt = cur;
  497.                             dir = RIGHT;
  498.                         }
  499.                     }
  500.                     gpa = cur->par;
  501.                 } else {
  502.                     /*
  503.                      * RR rotation.
  504.                      */
  505.                    
  506.                     gpa->rgt = par->lft;
  507.                     if (par->lft)
  508.                         par->lft->par = gpa;
  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.                         /*
  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.
  524.                          */
  525.                         par->balance = -1;
  526.                         gpa->balance = 1;
  527.  
  528.                         /*
  529.                          * Repair the pointer which
  530.                          * pointed to the balanced node
  531.                          * and finish balancing.
  532.                          */
  533.                         if (par->par == NULL) {
  534.                             t->root = par; 
  535.                         } else {
  536.                             if (par->par->lft ==
  537.                                 gpa) {
  538.                                 par->par->lft =
  539.                                     par;
  540.                             } else {
  541.                                 par->par->rgt =
  542.                                     par;
  543.                             }
  544.                         }
  545.                         break;
  546.                     } else {
  547.                         par->balance = gpa->balance = 0;
  548.                         /*
  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).
  555.                          */
  556.                         if (par->par == NULL) {
  557.                             t->root = par; 
  558.                             break;
  559.                         } else {   
  560.                             if (par->par->lft ==
  561.                                 gpa) {
  562.                                 par->par->lft =
  563.                                     par;
  564.                                 dir = LEFT;
  565.                             } else {
  566.                                 par->par->rgt =
  567.                                     par;
  568.                                 dir = RIGHT;
  569.                             }
  570.                         }
  571.                     }
  572.                     gpa = par->par;
  573.                 }
  574.             } else {
  575.                 /*
  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).
  580.                  */
  581.                 if (!gpa->par)
  582.                     break;
  583.  
  584.                 if (gpa->par->lft == gpa) {
  585.                     dir = LEFT;
  586.                 } else {
  587.                     dir = RIGHT;
  588.                 }
  589.                 gpa = gpa->par;
  590.             }
  591.         } else {
  592.             /*
  593.              * Deletion was made in the right subtree.
  594.              */
  595.             gpa->balance--;
  596.             if (gpa->balance == -1) {
  597.                 /*
  598.                  * Stop balancing, the tree is balanced.
  599.                  */
  600.                 break;
  601.             } else if (gpa->balance == -2) {
  602.                 /*
  603.                  * Bad balance, heights of left and right
  604.                  * subtrees differ more than by one.
  605.                  */
  606.                 par = gpa->lft;
  607.                
  608.                 if (par->balance == 1) {
  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.                     /*
  620.                      * Repair balances and paternity of
  621.                      * children, depending on the balance
  622.                      * factor of the grand child (cur).
  623.                      */
  624.                     if (cur->balance == -1) {
  625.                         par->balance = 0;
  626.                         gpa->balance = 1;
  627.                         if (gpa->lft)
  628.                             gpa->lft->par = gpa;
  629.                         par->rgt->par = par;
  630.                     } else if (cur->balance == 0) {
  631.                         par->balance = gpa->balance = 0;
  632.                         if (gpa->lft)
  633.                             gpa->lft->par = gpa;
  634.                         if (par->rgt)
  635.                             par->rgt->par = par;
  636.                     } else {
  637.                         par->balance = -1;
  638.                         gpa->balance = 0;
  639.                         if (par->rgt)
  640.                             par->rgt->par = par;
  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.                     /*
  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).
  658.                      */
  659.                     if (cur->par == NULL) {
  660.                         t->root = cur; 
  661.                         break;
  662.                     } else {
  663.                         if (cur->par->lft == gpa) {
  664.                             cur->par->lft = cur;
  665.                             dir = LEFT;
  666.                         } else {
  667.                             cur->par->rgt = cur;
  668.                             dir = RIGHT;
  669.                         }
  670.                     }
  671.                     gpa = cur->par;
  672.                 } else {
  673.                     /*
  674.                      * LL rotation.
  675.                      */
  676.                    
  677.                     gpa->lft = par->rgt;
  678.                     if (par->rgt)
  679.                         par->rgt->par = gpa;
  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.                         /*
  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.
  694.                          */
  695.                         par->balance = 1;
  696.                         gpa->balance = -1;
  697.                        
  698.                         /*
  699.                          * Repair the pointer which
  700.                          * pointed to the balanced node
  701.                          * and finish balancing.
  702.                          */
  703.                         if (par->par == NULL) {
  704.                             t->root = par;
  705.                         } else {
  706.                             if (par->par->lft ==
  707.                                 gpa) {
  708.                                 par->par->lft =
  709.                                     par;
  710.                             } else {
  711.                                 par->par->rgt =
  712.                                     par;
  713.                             }
  714.                         }
  715.                         break;
  716.                     } else {
  717.                         par->balance = gpa->balance = 0;
  718.                        
  719.                         /*
  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).
  726.                          */
  727.                         if (par->par == NULL) {
  728.                             t->root = par;
  729.                             break;
  730.                         } else {
  731.                             if (par->par->lft ==
  732.                                 gpa) {
  733.                                 par->par->lft =
  734.                                     par;
  735.                                 dir = LEFT;
  736.                             } else {
  737.                                 par->par->rgt =
  738.                                     par;
  739.                                 dir = RIGHT;
  740.                             }
  741.                         }
  742.                     }
  743.                     gpa = par->par;
  744.                 }
  745.             } else {
  746.                 /*
  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).
  751.                  */
  752.                 if (!gpa->par)
  753.                     break;
  754.  
  755.                 if (gpa->par->lft == gpa) {
  756.                     dir = LEFT;
  757.                 } else {
  758.                     dir = RIGHT;
  759.                 }
  760.                 gpa = gpa->par;
  761.             }
  762.         }
  763.     }
  764. }
  765.  
  766.  
  767. /** Delete a node with the smallest key from the AVL tree.
  768.  *
  769.  * @param t AVL tree structure.
  770.  */
  771. bool avltree_delete_min(avltree_t *t)
  772. {
  773.     avltree_node_t *node;
  774.    
  775.     /*
  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).
  779.      */
  780.      
  781.     node = t->root;
  782.     if (!node)
  783.         return false;
  784.    
  785.     while (node->lft != NULL)
  786.         node = node->lft;
  787.    
  788.     avltree_delete(t, node);
  789.  
  790.     return true;
  791. }
  792.  
  793. /** @}
  794.  */
  795.