chiark - git - mdw - xyla/blob - avl.h

   1 #ifndef AVL_H
   2 #define AVL_H
   3
   4 #include <limits.h>
   5
   6 #include "bst.h"
   7
   8 struct avlnode {
   9   struct bstnode _bst;
  10   unsigned f;
  11 #define AVLF_BALMASK 3u
  12 #define AVLBAL_LBIAS 1u
  13 #define AVLBAL_EVEN 0u
  14 #define AVLBAL_RBIAS 2u
  15 };
  16
  17 /* The maximum possible height %$H_n$% for an AVL tree containing %$n$% nodes
  18  * is somewhat annoying to calculate.  The best way to start is to reverse
  19  * the question and find the smallest number %$N_h$% of nodes which can force
  20  * the tree to have height %$h$%.
  21  *
  22  * This is going to involve a recurrence.  The base case is the rather
  23  * unsurprising observations that %$N_0 = 0$% and %$N_1 = 1$%.
  24  *
  25  * The imbalance between the root's left and right subtrees can be at most 1.
  26  * The cheapest way we can make a tree with height %$h$%, then, is if the
  27  * root is biased to the left (say) and then its left and right subtrees are
  28  * the smallest trees with height %$h - 1$% and %$h - 2$% respectively.  We
  29  * have the oddly familiar recurrence
  30  *
  31  *      %$N_h = N_{h-1} + N_{h-2} + 1$%.
  32  *
  33  * Guess that %$N_h = x^h + C$% for some constants %$x$% and %$C$%.  Then
  34  *
  35  *      %$x^h + C = x^{h-1} + x^{h-2} + 2 C + 1$%,
  36  *
  37  * and
  38  *
  39  *      %$x^h = x^{h-1} + x^{h-2} + C + 1$%,
  40  *
  41  * so setting %$C = -1$% seems like the best bet; that leaves
  42  *
  43  *      %$x^h = x^{h-1} + x^{h-2}%,
  44  *
  45  * which is well-known to be solved by setting %$x = \phi$% or
  46  * %$x = \bar{\phi}$%, where
  47  *
  48  *      %$\displaystyle \phi = \frac{1 + \sqrt{5}}{2}$%
  49  *
  50  * and
  51  *
  52  *      %$\displaystyle \bar{\phi} = \frac{1 - \sqrt{5}}{2}$%.
  53  *
  54  * This relationship clearly holds for any linear combination of %$\phi$% and
  55  * %$\bar{\phi}$%.  So we finally set
  56  *
  57  *      %$N_h = A \phi^h + B \bar{\phi}^h - 1$%
  58  *
  59  * and check the initial conditions.  %$N_0 = 0$% forces %$A + B = 1$%.  And
  60  * %$N_1 = 1$% means
  61  *
  62  *      %$A \phi + B \bar{\phi} = 2$%;
  63  *
  64  * substituting %$\phi$% and %$\bar{\phi}$% and rearranging gives
  65  *
  66  *      %$(A + B) + \sqrt{5} (A - B) = 4$%.
  67  *
  68  * We know %$A + B = 1$%, so %$A - B = 3/\sqrt{5} = 3 \sqrt{5}/5$%.  Adding
  69  * these two gives
  70  *
  71  *      %$\displaystyle A = \frac{5 + 3 \sqrt{5}}{10}$%
  72  *
  73  * and
  74  *
  75  *      %$\displaystyle B = \frac{5 - 3 \sqrt{5}}{10}$%.
  76  *
  77  * What we actually wanted to know was the maximum possible height %$H_n$%
  78  * for a red-black tree with %$n$% nodes.  Suppose, then, that, for some
  79  * %$h$%, the tree has %$n \ge N_h \ge A \phi^h + B \bar{\phi}^h - 1$% nodes.
  80  * Notice that %$|B < 1$% and %$|\bar{\phi}| < 1$%; therefore,
  81  * %$|B \bar{\phi}^h| < 1$%, and we have %$n \ge A \phi^h - 2$%.  (Sadly,
  82  * %$\bar{\phi}$% is negative.)
  83  *
  84  * Continuing, we see %$A \phi^h \le n + 2$%.  Taking (binary) logs gives
  85  * %$h \lg \phi + \lg A \le \lg (n + 2)$%, whence
  86  *
  87  *      %$\displaystyle h\le\frac{\lg (n + 2) - \lg A}{\lg \phi}$%.
  88  *
  89  * This is pretty gnarly to evaluate with the C preprocessor.  Fortunately,
  90  * $%0 < 13/9 - 1/\lg \phi < 1/200$%, so
  91  *
  92  *      %$\displaystyle h \le \frac{13}{9}\lg(n+2) - \frac{\lg A}{\lg\phi}$%.
  93  *
  94  * In fact, we can do better .  As %$n$% gets larger, the difference
  95  * %$\log (n + 2) - \log n$% tends to zero.  There is therefore a value %$N$%
  96  * such that
  97  *
  98  *      %$\displaystyle \frac{13}{9}\lg n\ge\frac{\lg(n+2)-\lg A}{\lg\phi}$%
  99  *
 100  * whenever %$n \ge N$%.
 101  *
 102  * This is too horrid to solve by hand, but numerical methods show that
 103  * %$N = 12$% satisfies our requirements.  We must, of course, round up
 104  * rather than down while computing this.
 105  *
 106  * Our %$n$% of interest is the largest value that can fit in @size_t@, which
 107  * is an unsigned type; therefore %$n = 2^k - 1$% for some %$k$%, and
 108  * %$\floor{\lg (n + 2)} = k$%.  Alas, C doesn't give us %$k$% directly, but
 109  * it can certainly be no more than @CHAR_BIT*sizeof(size_t)@; since padding
 110  * bits in integers are extremely rare, this is usually the exact value.  C
 111  * permits objects at least %$2^{15} - 1$% bytes in size, so this must be at
 112  * least that large.  In particular, it's larger than %$12$%, so we can apply
 113  * this simplification.
 114  *
 115  * On conventional 32-bit targets, this is 47; on 64-bit targets, it's 93.
 116  * Both overestimate by one entry.
 117  */
 118
 119 #define AVLTREE_PATHMAX (13*(sizeof(size_t)*CHAR_BIT + 8)/9)
 120
 121 struct avlpath {
 122   int k;
 123   struct bstnode **p[AVLTREE_PATHMAX];
 124 };
 125
 126 struct avliter {
 127   int sp;
 128   struct bstnode *stack[AVLTREE_PATHMAX];
 129 };
 130
 131 /* --- @avltree_check@ --- *
 132  *
 133  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 134  *              @struct avlnode *const *root@ = root pointer that we're
 135  *                      checking
 136  *              @int expht@ = expected height for tree, or %$-1$% if unknown
 137  *              @void *arg@ = argument to pass to check function
 138  *
 139  * Returns:     Zero if everything was OK, %$-1$% if problems were found and
 140  *              reported.
 141  *
 142  * Use:         Recursively examine an AVL tree, checking that it satisfies
 143  *              all of the necessary invariants.
 144  */
 145
 146 extern int avltree_check(struct bstree_nodecls */*cls*/,
 147                          struct bstnode *const */*root*/, int /*expht*/,
 148                          void */*arg*/);
 149
 150 /* --- @avltree_height@ --- *
 151  *
 152  * Arguments:   @const struct avlnode *node@ = pointer to a tree node
 153  *
 154  * Returns:     The height for the (sub)tree rooted at @node@.  This is
 155  *              primarily useful as input to @avltree_join@ and
 156  *              @avltree_split@.
 157  */
 158
 159 extern int avltree_height(const struct avlnode */*node*/);
 160
 161 /* --- @avltree_lookup@ --- *
 162  *
 163  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 164  *              @struct bstnode *root@ = pointer to root node
 165  *              @void *arg@ = argument to the navigation function
 166  *
 167  * Returns:     Pointer to the matching node, or null if it couldn't be
 168  *              found.
 169  *
 170  * Use:         Search for a node within the tree according to the navigation
 171  *              function.
 172  */
 173
 174 extern void *avltree_lookup(struct bstree_nodecls */*cls*/,
 175                             struct bstnode */*root*/, void */*arg*/);
 176
 177 /* --- @avltree_probe@ --- *
 178  *
 179  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 180  *              @struct bstnode **root@ = pointer to root link
 181  *              @const void *search_key@ = the key to search for
 182  *              @struct avlpath *path@ = path to fill in
 183  *
 184  * Returns:     Pointer to the matching node, or null if it couldn't be
 185  *              found.
 186  *
 187  * Use:         Search for a node within the tree according to the navigation
 188  *              function, recording the search path  This can be used later,
 189  *              e.g., by @avltree_insert@ to insert a new node if none was
 190  *              found, or by @avltree_remove@ to remove the node that was
 191  *              found.
 192  */
 193
 194 extern void *avltree_probe(struct bstree_nodecls */*cls*/,
 195                            struct bstnode **/*root*/, void */*arg*/,
 196                            struct avlpath */*path*/);
 197
 198 /* --- @avltree_inititer@ --- *
 199  *
 200  * Arguments:   @struct bstnode *root@ = pointer to the tree header
 201  *              @struct avliter *it@ = pointer to iterator to initialize
 202  *
 203  * Returns:     ---
 204  *
 205  * Use:         Initialize an iterator.
 206  */
 207
 208 extern void avltree_inititer(struct bstnode */*root*/,
 209                              struct avliter */*it*/);
 210
 211 /* --- @avltree_next@ --- *
 212  *
 213  * Arguments:   @struct avliter *it@ = pointer to iterator
 214  *
 215  * Returns:     A pointer to the next node in ascending order, or null
 216  *              if no more nodes remain.
 217  *
 218  * Use:         Advances a tree iterator.  Inserting or removing elements
 219  *              invalidates the iterator.  As a special exception, it is
 220  *              permitted to free all of the nodes by iterating over the tree
 221  *              in the obvious manner:
 222  *
 223  *                      @avltree_inititer(tree, &it);@
 224  *                      @for (;;) {@
 225  *                        @node = avltree_next(&it); if (!node) break;@
 226  *                        @free(node);@
 227  *                      @}@
 228  *
 229  *              At this point, the tree header structure is left in an
 230  *              invalid state, and must not be used; it is, however, safe to
 231  *              discard, since it holds no resources.
 232  */
 233
 234 extern void *avltree_next(struct avliter */*it*/);
 235
 236 /* --- @avltree_firstpath@, @avltree_lastpath@ --- *
 237  *
 238  * Arguments:   @struct bstnode **root@ = address of the tree root link
 239  *              @struct avlpath *path@ = path to fill in
 240  *
 241  * Returns:     Pointer to the requested node, or null if the tree is empty.
 242  *
 243  * Use:         Return the first or last node in the tree, as ordered by
 244  *              their keys, together with a path to the requested node, which
 245  *              can be used to remove them, or to navigate to other nodes in
 246  *              the tree.
 247  */
 248
 249 extern void *avltree_firstpath(struct bstnode **/*root*/,
 250                                struct avlpath */*path*/);
 251 extern void *avltree_lastpath(struct bstnode **/*root*/,
 252                               struct avlpath */*path*/);
 253
 254 /* --- @avltree_nextpath@, @avltree_prevpath@ --- *
 255  *
 256  * Arguments:   @struct avlpath *path@ = path to update
 257  *
 258  * Returns:     Pointer to the requested node, or null if the tree is empty
 259  *              or the path is already positioned at the relevant extreme.
 260  *
 261  * Use:         Return the next or previous node in the tree, as ordered by
 262  *              their keys, together with a path to the requested node, which
 263  *              can be used to remove them, or to navigate to other nodes in
 264  *              the tree.
 265  *
 266  *              If the path is full, i.e., refers to an existing node, then
 267  *              the functions return that node's successor or predecessor.
 268  *              If the path is empty, i.e., refers to a space between nodes
 269  *              where a new node can be inserted, then the functions return
 270  *              the node at the upper or lower end of the gap, unless the
 271  *              `gap' is actually at an extreme of the tree and no such node
 272  *              exists.  In the latter case, a null pointer is returned.
 273  *              The path is modified to refer to the new node, if any, or to
 274  *              the gap at the appropriate extreme of the tree.
 275  */
 276
 277 extern void *avltree_nextpath(struct avlpath */*path*/);
 278 extern void *avltree_prevpath(struct avlpath */*path*/);
 279
 280 /* --- @avltree_beforepath@, @avltree_afterpath@ --- *
 281  *
 282  * Arguments:   @struct avlpath *path@ = path to update
 283  *
 284  * Returns:     ---
 285  *
 286  * Use:         Advance the path to just before or after the current node.
 287  *              The path thereby becomes empty, suitable to insert an element
 288  *              or split the tree just before or after the previously
 289  *              selected node.
 290  */
 291
 292 extern void avltree_afterpath(struct avlpath */*path*/);
 293 extern void avltree_beforepath(struct avlpath */*path*/);
 294
 295 /* --- @avltree_replace@ --- *
 296  *
 297  * Arguments:   @struct avlpath *path@ = pointer to a full path
 298  *              @struct avlnode *node@ = pointer to replacement node
 299  *
 300  * Returns:     ---
 301  *
 302  * Use:         Replace the node identified by the @path@ with the given
 303  *              @node@.  The replacement @node@ should have the same (equal,
 304  *              according to the node-class comparison function) key as the
 305  *              node it replaces, and %%\emph{must}%% be strictly between the
 306  *              keys of the old node's predecessor and successor.  The node's
 307  *              links need not be initialized.  Paths and iterators are not
 308  *              invalidated.
 309  */
 310
 311 extern void avltree_replace(struct avlpath */*path*/,
 312                             struct avlnode */*node*/);
 313
 314 /* --- @avltree_insert@ --- *
 315  *
 316  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 317  *              @struct avlpath *path@ = pointer to an empty path
 318  *              @struct avlnode *node@ = the new node to add
 319  *
 320  * Returns:     Adjustment (%$0$% or %$+1$%) to the tree height.
 321  *
 322  * Use:         Add a new node to the tree, in the place determined by the
 323  *              empty path.  The @new_node@'s key must be equal to the key
 324  *              passed to @avltree_probe@ when it produced the path.
 325  *
 326  *              The new node is not copied, and its storage must remain valid
 327  *              until the node is removed or the tree is discarded.
 328  */
 329
 330 extern int avltree_insert(struct bstree_nodecls */*cls*/,
 331                           struct avlpath */*path*/,
 332                           struct avlnode */*node*/);
 333
 334 /* --- @avltree_remove@ --- *
 335  *
 336  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 337  *              @struct avlpath *path@ = pointer to a full path
 338  *
 339  * Returns:     Adjustment (%$0$% or %$-1$%) to the tree height.
 340  *
 341  * Use:         Removes the node identified by the path.  The node was
 342  *              allocated by the caller, and should be freed by the caller in
 343  *              whatever way is appropriate.
 344  */
 345
 346 extern int avltree_remove(struct bstree_nodecls */*cls*/,
 347                           struct avlpath */*path*/);
 348
 349 /* --- @avltree_join@ --- *
 350  *
 351  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 352  *              @struct bstnode **root_out@ = address to store the link to
 353  *                      the root of the combined tree
 354  *              @struct bstnode **left@ = address containing the current
 355  *                      root of the left tree
 356  *              @int lht@ = height of the left tree, or %$-1$% if unknown
 357  *              @struct bstnode *mid@ = pointer to middle node, or null
 358  *              @struct bstnode **right@ = address containing the current
 359  *                      root of the right tree
 360  *              @int rht@ = height of the right tree, or %$-1$% if unknown
 361  *
 362  * Returns:     The height of the combined tree.
 363  *
 364  * Use:         Concatenate two trees.
 365  *
 366  *              Every node in the left tree must have a key strictly less
 367  *              than any node of the right tree.  If a middle node is
 368  *              provided, then its key must be greater than that of any node
 369  *              in the left tree, and less than that of any node in the right
 370  *              tree.
 371  *
 372  *              The output is a single tree containing every node in the left
 373  *              and right input trees, together with the middle node, if that
 374  *              is not null.
 375  *
 376  *              The @root_out@ pointer may equal either @left@ or @right@
 377  *              (or, indeed, both, only if both are empty).  If @lroot@ is
 378  *              distinct from @root_out@ then it @*left@ set null on exit;
 379  *              similarly, if @rroot@ is distinct from @root_out@, then
 380  *              @*right@ is set null on exit.
 381  */
 382
 383 extern int avltree_join(struct bstree_nodecls */*cls*/,
 384                         struct bstnode **/*root_out*/,
 385                         struct bstnode **/*left*/, int /*lht*/,
 386                         struct bstnode */*mid*/,
 387                         struct bstnode **/*right*/, int /*rht*/);
 388
 389 /* --- @avltree_split@ --- *
 390  *
 391  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 392  *              @struct bstnode *left_out@ = where to leave the root of the
 393  *                      resulting left tree
 394  *              @int *lht_out@ = where to leave the height of the left tree,
 395  *                      or null to discard this information
 396  *              @int *mht_out@ = where to leave the height of the middle node
 397  *                      (either zero or one), or null to discard this
 398  *                      information
 399  *              @struct bstnode *rirght_out@ = where to leave the root of the
 400  *                      resulting right tree
 401  *              @int *rht_out@ = where to leave the height of the right tree,
 402  *                      or null to discard this information
 403  *              @struct avlpath *path@ = full or empty path at which to split
 404  *                      the tree
 405  *
 406  * Returns:     A pointer to the resulting middle node, or null.
 407  *
 408  * Use:         Split a tree into two at an indicated place.
 409  *
 410  *              The splitting operation produces two trees, a `left tree'
 411  *              containing every node preceding the given path, and a `right
 412  *              tree' containing every node following the path.  If the path
 413  *              is full, i.e., it denotes a node in the input tree, then that
 414  *              becomes the `middle node', which does not appear in either
 415  *              tree, and is returned separately.
 416  */
 417
 418 extern void *avltree_split(struct bstree_nodecls */*cls*/,
 419                            struct bstnode **/*left_out*/, int */*lht_out*/,
 420                            int */*mht_out*/,
 421                            struct bstnode **/*right_out*/, int */*rht_out*/,
 422                            struct avlpath */*path*/);
 423
 424 /* --- @avltree_splitat@ --- *
 425  *
 426  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 427  *              @struct bstnode *left_out@ = where to leave the root of the
 428  *                      resulting left tree
 429  *              @int *lht_out@ = where to leave the height of the left tree,
 430  *                      or null to discard this information
 431  *              @int *mht_out@ = where to leave the height of the middle
 432  *                      node (either zero or one), or null to discard this
 433  *                      information
 434  *              @struct bstnode *right_out@ = where to leave the root of the
 435  *                      resulting right tree
 436  *              @int *rht_out@ = where to leave the height of the right tree,
 437  *                      or null to discard this information
 438  *              @struct bstnode **root@ = address of the root link of the
 439  *                      input tree
 440  *              @const void *key@ = key at which to split the tree.
 441  *
 442  * Returns:     A pointer to the matching middle node, or null.
 443  *
 444  * Use:         Split a tree into two at an indicated key.
 445  *
 446  *              The splitting operation produces two trees, a `left tree'
 447  *              containing every node whose key is less than @key@, and a
 448  *              `right tree' containing every node whose key is greater than
 449  *              @key@.  If a node matching the @key@ exists in the input
 450  *              tree, then that becomes the `middle node', which does not
 451  *              appear in either tree, and is returned separately.
 452  */
 453
 454 extern void *avltree_splitat(struct bstree_nodecls */*cls*/,
 455                              struct bstnode **/*left_out*/,
 456                                int */*lht_out*/,
 457                              int */*mht_out*/,
 458                              struct bstnode **/*right_out*/,
 459                                int */*rht_out*/,
 460                              struct bstnode **/*root*/, const void */*key*/);
 461
 462 /* --- @avltree_splitroot@ --- *
 463  *
 464  * Arguments:   @struct bstnode *left_out@ = where to leave the root of the
 465  *                      resulting left tree
 466  *              @int *lht_out@ = where to leave the height of the left
 467  *                      tree, or null to discard this information
 468  *              @int *mht_out@ = where to leave the height of the
 469  *                      middle node (either zero or one), or null to discard
 470  *                      this information
 471  *              @struct bstnode *right_out@ = where to leave the root of the
 472  *                      resulting right tree
 473  *              @int *rht_out@ = where to leave the height of the right
 474  *                      tree, or null to discard this information
 475  *              @struct bstnode **root@ = tree root node, or null
 476  *              @int ht@ = height of the tree, or %$-1$% if unknown
 477  *
 478  * Returns:     A pointer to the resulting middle node, or null.
 479  *
 480  * Use:         Split a tree into two at its root.
 481  *
 482  *              The splitting operation produces two trees, a `left tree'
 483  *              containing every node preceding the root, and a `right
 484  *              tree' containing every node following the root, together with
 485  *              the root.  If the root is null, then the left and right trees
 486  *              are also null.
 487  */
 488
 489 extern void *avltree_splitroot(struct bstnode **/*left_out*/,
 490                                  int */*lht_out*/,
 491                                int */*mht_out*/,
 492                                struct bstnode **/*right_out*/,
 493                                  int */*rht_out*/,
 494                                struct bstnode **/*root*/, int /*ht*/);
 495
 496 /* --- @avltree_unisect@ --- *
 497  *
 498  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 499  *              @struct bstnode **uni_out@ = where to write the union root
 500  *              @int *uniht_out@ = where to put the union height (or null)
 501  *              @struct bstnode **isect_out@ = where to write the
 502  *                      intersection root
 503  *              @int *isectht_out@ = where to put the intersection height (or
 504  *                      null)
 505  *              @struct bstnode *a@ = pointer to first operand root node
 506  *              @int aht@ = first operand height, or %$-1$%
 507  *              @struct bstnode *b@ = pointer to second operand root node
 508  *              @int bht@ = second operand height, or %$-1$%
 509  *
 510  * Returns:     ---
 511  *
 512  * Use:         Compute the union and intersection of the two operand trees.
 513  *
 514  *              The original trees are destroyed.  Each node in the original
 515  *              operands trees ends up in exactly one of the result trees.
 516  */
 517
 518 extern void avltree_unisect(struct bstree_nodecls */*cls*/,
 519                             struct bstnode **/*uni_out*/,
 520                               int */*uniht_out*/,
 521                             struct bstnode **/*isect_out*/,
 522                               int */*isectht_out*/,
 523                             struct bstnode **/*aroot*/, int /*aht*/,
 524                             struct bstnode **/*broot*/, int /*bht*/);
 525
 526 /* --- @avltree_diffsect@ --- *
 527  *
 528  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 529  *              @struct bstnode **diff_out@ = where to write the difference
 530  *                      root
 531  *              @int *diffht_out@ = where to put the difference height (or
 532  *                      null)
 533  *              @struct bstnode **isect_out@ = where to write the
 534  *                      intersection root
 535  *              @int *isectht_out@ = where to put the intersection height (or
 536  *                      null)
 537  *              @struct bstnode *a@ = pointer to first operand root node
 538  *              @int aht@ = first operand height, or %$-1$%
 539  *              @struct bstnode *b@ = pointer to second operand root node
 540  *
 541  * Returns:     ---
 542  *
 543  * Use:         Compute the difference -- i.e., those nodes in %$a$% without
 544  *              matching nodes in %$b$% -- and intersection of the two
 545  *              operand trees.
 546  *
 547  *              The original tree %$a$% is destroyed.  Each node in the
 548  *              original operands tree ends up in exactly one of the result
 549  *              trees.  The input tree %$b$% is unchanged.
 550  */
 551
 552 extern void avltree_diffsect(struct bstree_nodecls */*cls*/,
 553                              struct bstnode **/*diff_out*/,
 554                                int */*diffht_out*/,
 555                              struct bstnode **/*isect_out*/,
 556                                int */*isectht_out*/,
 557                              struct bstnode **/*aroot*/, int /*aht*/,
 558                              struct bstnode **/*broot*/);
 559
 560 #endif