chiark - git - mdw - xyla/blob - splay-balance.c

   1 /* -*-c-*-
   2  *
   3  * Rebalancind splay 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 "splay.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 void xyla_splay_rebalance(struct xyla_bt_nodecls *cls,
  34                           struct xyla_bt_node **root)
  35 {
  36   /* Force the tree whose root link is at ROOT to be rebalanced.
  37    *
  38    * The tree is restructured so as to have minimal height.  Weight balance
  39    * is not guaranteed, and, currently, at any rate, the rightmost portions
  40    * of the tree are likely to be quite light if the number of nodes is far
  41    * from a power of 2.
  42    */
  43
  44   struct xyla_splay_node *node, *u, *v, *nv[XYLA_SPLAY_HTMAX];
  45   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  46   int i, j, bit;
  47
  48   /* The usual algorithm for this task is by Day, Stout, and Warren
  49    * (see
  50    *
  51    *    https://en.m.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm
  52    *
  53    * It works by initially straightening the tree into a `vine' using
  54    * rotations, and then repeatedly `compressing' the vine by applying
  55    * a rotation to every other link along the rightmost.  The
  56    * algorithm here is similar to the Day--Stout--Warren algorithm in
  57    * nearly no respect whatsoever.
  58    *
  59    * Instead, we start by giving each node, in order, an index.
  60    * Astonishingly, this is a situation where it makes everything easier to
  61    * start counting from 1.  When we do that, we get a picture like the
  62    * following.
  63    *
  64    *                                16
  65    *                                  *
  66    *                 8  ,-----------'   `-----------,  24
  67    *                  *                               *
  68    *         4  ,---'   `---,  12           20  ,---'   `---,  28
  69    *          *               *               *               *
  70    *     2  /   \  6    10  /   \  14   18  /   \  22   26  /   \  30
  71    *      *       *       *       *       *       *       *       *
  72    *     / \     / \     / \     / \     / \     / \     / \     / \
  73    *    *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *
  74    *    1   3   5   7   9  11  13  15  17  19  21  23  25  27  29  31
  75    *
  76    * This is all more striking in binary.  The leaf nodes, along the bottom
  77    * row, all have odd indices, so their least significant bits are set.  In
  78    * the next row up, the nodes' indices have bit 0 clear, but bit 1 set.
  79    * And, in general, the nodes k levels up from the bottom have indices with
  80    * bit k set, and all the less significant bits clear.
  81    *
  82    * It gets better.  The higher bit positions of a node's index describe the
  83    * path from the node back up to the root: bit k + 1 is clear if the node
  84    * is a left child, or set if it's a right child; in the same way, bit
  85    * k + 2 describes which child of the node's grandparent its parent is,
  86    * and so on.  (The root itself therefore appears to have an infinite
  87    * rightwards path: the indices can describe an infinite tree, of which any
  88    * finite tree is a leftmost subtree.)
  89    *
  90    * Keeping track of node indices is (nearly) trivial if we can visit the
  91    * nodes in order.  That's the job of `xyla_bt_severfirst'.  The index
  92    * then tells us exactly how to attach the node into the balanced tree
  93    * structure.
  94    *
  95    * We maintain a vector `nv' for the nodes currently under construction.
  96    * Because we build the tree in-order, when we come to build a node, we'll
  97    * already have constructed its left subtree, but its right subtree won't
  98    * be ready yet.  The node's index i describes the state that the vector
  99    * should be in /after/ we've added the current node; the previous index i
 100    * - 1 therefore describes the state it's in right now: if bit k is set,
 101    * then nv[k] holds a pointer to a half-finished level-k node, and if the
 102    * bit is clear, then nv[k] is uninteresting.
 103    *
 104    * So, suppose that we want to process a new node, with index i.  Let k be
 105    * the position of the least-significant set bit in i.  In the previous
 106    * index i - 1, by contrast, bit k is clear, but all of the
 107    * less-significant bits are set, so the corresponding slots nv[j] hold
 108    * half-finished nodes which we can now complete.  Level-0 slots need no
 109    * work.  For levels 1 <= j < k, take the finished node from level j - 1,
 110    * and attach it as the right subtree of the half-finished node in level j.
 111    * The completed level-(k - 1) node is then the left subtree of the new
 112    * level-k node, which we now store in nv[k].  There are fancy `ctz'
 113    * instructions on many processors -- and clever bitwise tricks, such as
 114    * those described in Hank Warren's magnificent /Hacker's Delight/ -- for
 115    * finding k efficiently, but since we have to finish off k half-finished
 116    * nodes anyway, there's no advantage to avoiding the obvious but simple
 117    * linear search.
 118    *
 119    * That almost sounds too easy.  There are, unfortunately, two difficulties
 120    * to deal with.
 121    *
 122    * The first is that the lovely indexing scheme only works for /complete/
 123    * trees, and we probably don't have one of those.  At the end, we're left
 124    * with an index describing the final state of the `nv' vector.  We just
 125    * walk up through this index, starting with a null pointer in hand: each
 126    * time we find a set bit, bit k, say, we set the pointer in hand as the
 127    * right child of the half-finished node in nv[k], and the resulting
 128    * complete node becomes the new node in hand.  The root is the final node
 129    * in hand.  The resulting tree has minimal height, which is the important
 130    * thing; it probably won't actually satisfy any reasonable definition of
 131    * `balance'.  (For example, if we have 2^h nodes, then the root will have
 132    * a complete left subtree and no right subtree at all.)  Later splaying
 133    * will make a total mess of any structure we apply here, so it's not worth
 134    * paying attention to such æsthetic matters.
 135    *
 136    * (Here's an approach we could use if we wanted an actually balanced tree.
 137    * The complete tree of height h has 2^h - 1 nodes.  Suppose instead that
 138    * we have only 2^h - 1 - t (for some 0 <= t < 2^{h/2}), so that the bottom
 139    * row of leaves is short by t nodes.  Then the nodes with /odd/ indices
 140    * greater than or equal to 2^h - 2 t + 1 will be missing.  All we need to
 141    * do is store a null pointer in the nv[0] slot in these cases rather than
 142    * the next node from the input tree.  This depends on knowing the total
 143    * number of nodes in the tree, which we otherwise avoid.  An initial
 144    * vine-construction pass would provide this information without the need
 145    * for a tree traversal.)
 146    *
 147    * The iteration performed by `xyla_bt_severfirst' is amortized-linear,
 148    * and we run it to completion.  The number of subtrees collected in each
 149    * step is equal to the number of low-significance zero bits in the index.
 150    * If we sum these, we get a series of the form
 151    *
 152    *    1 + 2 + 1 + 3 + 1 + 2 + 1 + 4 + ... .
 153    *
 154    * The terms are successive values of the `ruler function'
 155    * (https://oeis.org/A001511); the sequence of partial sums
 156    * (https://oeis.org/A005187) is easily seen to be bounded above
 157    * by 2 n - 1.  The overall complexity is therefore linear.  Unlike
 158    * Day--Stout--Warren, we require logarithmic additional space, but this is
 159    * inevitable because we want to rebuild a path.
 160    */
 161
 162   /* Start the main iteration. */
 163   i = 0;
 164   for (;;) {
 165
 166     /* Collect the next node from the old tree. */
 167     node = xyla_bt_severfirst(root); if (!node) break;
 168
 169     /* Bump the index. */
 170     i++;
 171
 172     /* Read the bits of i to work out what to do.  Stop when we find a
 173      * set bit: the index is strictly positive, so there must be one.
 174      */
 175     for (j = 0, bit = 1, u = 0; !(i&bit); j++, bit <<= 1) {
 176       /* Bit j of the index is clear.  Complete the node in nv[j] by
 177        * attaching child as its right child and advance our focus.
 178        */
 179
 180       v = nv[j]; v->bt.right = u ? &u->bt : 0; if (u) u->spl.parent = v;
 181       if (updfn) updfn(cls, &v->bt);
 182
 183       /* Shift focus. */
 184       u = v;
 185     }
 186
 187     /* We've found the set bit.  Save a half-finished node for later. */
 188     node->bt.left = u ? &u->bt : 0; if (u) u->spl.parent = node;
 189     nv[j] = node;
 190   }
 191
 192   /* The main iteration is complete.  Collect up the half-finished nodes
 193    * according to the final index.  This time we keep going until we've seen
 194    * all of the bits of i, so it's easiest to just shift it down.
 195    */
 196   node = 0;
 197   for (j = 0; i; j++, i >>= 1) {
 198
 199     /* Ignore clear bits.  We could skip more efficiently with a `ctz'
 200      * instruction but it doesn't seem worth the effort.
 201      */
 202     if (!(i&1)) continue;
 203
 204     /* Collect the right tree. */
 205     v = nv[j]; v->bt.right = node ? &node->bt : 0;
 206       if (node) node->spl.parent = v;
 207     if (updfn) updfn(cls, &v->bt);
 208
 209     /* Shift focus. */
 210     node = v;
 211   }
 212
 213   /* The tree is balanced.  Save the new root. */
 214   if (node) node->spl.parent = 0;
 215   *root = node ? &node->bt : 0;
 216 }
 217
 218 /*----- That's all, folks -------------------------------------------------*/