chiark - git - mdw - xyla/blob - avl-misc.c

   1 /* -*-c-*-
   2  *
   3  * Miscellaneous operations for AVL trees
   4  *
   5  * (c) 2024 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Xyla, a library of binary trees.
  11  *
  12  * Xyla is free software: you can redistribute it and/or modify it under
  13  * the terms of the GNU Lesser General Public License as published by the
  14  * Free Software Foundation; either version 3 of the License, or (at your
  15  * option) any later version.
  16  *
  17  * Xyla is distributed in the hope that it will be useful, but WITHOUT
  18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  20  * License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
  24  */
  25
  26 /*----- Header files ------------------------------------------------------*/
  27
  28 #include "lib.h"
  29 #include "avl.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 int xyla_avl_height(const struct xyla_avl_node *node)
  34 {
  35   /* Return the height for the (sub)tree rooted at NODE.  This is primarily
  36    * useful as input to `xyla_avl_join' and `xyla_avl_split'.
  37    */
  38
  39   int ht = 0;
  40
  41   while (node) {
  42
  43     /* Count one for this step. */
  44     ht++;
  45
  46     /* Use the balance annotations to discover a minimal path to a leaf. */
  47     switch (node->avl.f&XYLA_AVLF_BALMASK) {
  48       case XYLA_AVLBAL_LBIAS:
  49         ht++; node = CONST_AVL_NODE(node->bt.right);
  50         break;
  51       case XYLA_AVLBAL_RBIAS:
  52         ht++; node = CONST_AVL_NODE(node->bt.left);
  53         break;
  54       case XYLA_AVLBAL_EVEN:
  55         node = CONST_AVL_NODE(node->bt.left);
  56         break;
  57     }
  58   }
  59   return (ht);
  60 }
  61
  62 /*----- That's all, folks -------------------------------------------------*/