home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 3 / 3147 / rotate.old < prev    next >
Encoding:
Text File  |  1991-03-29  |  3.0 KB  |  89 lines
  1. /**
  2. *
  3. * rotate.old -- first set of rotations used for avl trees. There are two ways
  4. *        to code up the avl tree rotations.
  5. *
  6. *        The first way to implement the rotations is to write a
  7. *               single rotation procedure which adjusts balances with no
  8. *        prior knowledge of what they previously were. Then a double
  9. *        double roatation is merely two single rotation. This is the
  10. *        method used in this file. 
  11. *
  12. *        The second method is to write two procedures and to adjust
  13. *        balances by taking advantage of the knowledge of what the
  14. *        balances must be in order for the rotation procedure to have
  15. *        been called. This second method is implemented in the file
  16. *        "avl_tree.c" which contains all the other avl tree functions.
  17. *
  18. *        The advantage of the first approach is less code.
  19. *
  20. *        The advantage of the second approach is less function calls
  21. *        and less statements executed for a given rotation.
  22. *
  23. * ^{Mods:* }
  24. * 
  25. * Fri Jul 14 13:56:20 1989, Rev 1.0, brad(0165)
  26. * 
  27. * 16 Jun 89 -- Created.
  28. **/
  29.  
  30. /*
  31. * rotate_once()  --  rotate a given node in the given direction
  32. *                    to restore the balance of a tree
  33. */
  34. PRIVATE     short rotate_once( rootp, dir )
  35. AVLtree    *rootp;
  36. DIRECTION  dir;
  37. {
  38.     DIRECTION   other_dir = OPPOSITE( dir );    /* opposite direction to "dir" */
  39.     AVLtree     old_root  = *rootp;        /* copy of original root of tree */
  40.     short    ht_unchanged;            /* true if height unchanged */
  41.  
  42.     ht_unchanged = ( (*rootp) -> subtree[ other_dir ] -> bal ) ? FALSE : TRUE;
  43.   
  44.         /* assign new root */
  45.     *rootp = old_root -> subtree[ other_dir ];
  46.   
  47.         /* new-root exchanges it's "dir" subtree for it's parent */
  48.     old_root -> subtree[ other_dir ]   =   (*rootp) -> subtree[ dir ];
  49.     (*rootp) -> subtree[ dir ]         =   old_root;
  50.   
  51.         /* update balances */
  52.     if ( dir == LEFT )  {
  53.        old_root -> bal -=  ( 1 + MAX( (*rootp) -> bal, 0) );
  54.        (*rootp) -> bal -=  ( 1 - MIN( old_root -> bal, 0) );
  55.      }/* if */
  56.  
  57.     else  /* dir == RIGHT */  {
  58.        old_root -> bal +=  ( 1 - MIN( (*rootp)-> bal, 0) );
  59.        (*rootp) -> bal +=  ( 1 + MAX( old_root -> bal, 0) );
  60.      }/* else */
  61.   
  62.     return  ht_unchanged;
  63. }/* rotate_once */
  64.   
  65.  
  66. /****************************************************************************
  67. *    Normally I wouldnt bother with this next routine; I'd just call        *
  68. *    the above function twice. However, by using the routine below,        *
  69. *    I was able to use the same function calls in the "balance()"        *
  70. *    routine in "avl_tree.fns".                        *
  71. ****************************************************************************/
  72.  
  73.  
  74. /*
  75. * rotate_twice()  --  rotate a given node in the given direction
  76. *                     and then in the opposite direction
  77. *                     to restore the balance of a tree
  78. */
  79. PRIVATE     void rotate_twice( rootp, dir )
  80. AVLtree    *rootp;
  81. DIRECTION  dir;
  82. {
  83.     DIRECTION   other_dir = OPPOSITE( dir );
  84.   
  85.     rotate_once( &( (*rootp) -> subtree[ other_dir ] ), other_dir );  
  86.     rotate_once( rootp, dir );
  87.  
  88. }/* rotate_twice */
  89.