src/livarot/AVL.h

   1 /*
   2  *  AVL.h
   3  *  nlivarot
   4  *
   5  *  Created by fred on Mon Jun 16 2003.
   6  *
   7  */
   8
   9 #ifndef my_avl
  10 #define my_avl
  11
  12 #include <cstdlib>
  13 #include "LivarotDefs.h"
  14
  15 /*
  16  * base class providing AVL tree functionnality, that is binary balanced tree
  17  * there is no Find() function because the class only deal with topological info
  18  * subclasses of this class have to implement a Find(), and most certainly to
  19  * override the Insert() function
  20  */
  21
  22 class AVLTree
  23 {
  24 public:
  25
  26     AVLTree *elem[2];
  27
  28     // left most node (ie, with smallest key) in the subtree of this node
  29     AVLTree *Leftmost();
  30
  31 protected:
  32
  33     AVLTree *son[2];
  34
  35     AVLTree();
  36     virtual ~AVLTree();
  37
  38     // constructor/destructor meant to be called for an array of AVLTree created by malloc
  39     void MakeNew();
  40     void MakeDelete();
  41
  42     // insertion of the present node in the tree
  43     // insertType is the insertion type (defined in LivarotDefs.h: not_found, found_exact, found_on_left, etc)
  44     // insertL is the node in the tree that is immediatly before the current one, NULL is the present node goes to the
  45     // leftmost position. if insertType == found_exact, insertL should be the node with ak key
  46     // equal to that of the present node
  47     int Insert(AVLTree * &racine, int insertType, AVLTree *insertL,
  48                AVLTree * insertR, bool rebalance);
  49
  50     // called when this node is relocated to a new position in memory, to update pointers to him
  51     void Relocate(AVLTree *to);
  52
  53     // removal of the present element racine is the tree's root; it's a reference because if the
  54     // node is the root, removal of the node will change the root
  55     // rebalance==true if rebalancing is needed
  56     int Remove(AVLTree * &racine, bool rebalance = true);
  57
  58 private:
  59
  60     AVLTree *dad;
  61
  62     int balance;
  63
  64     // insertion gruntwork.
  65     int Insert(AVLTree * &racine, int insertType, AVLTree *insertL, AVLTree *insertR);
  66
  67     // rebalancing functions. both are recursive, but the depth of the trees we'll use should not be a problem
  68     // this one is for rebalancing after insertions
  69     int RestoreBalances(AVLTree *from, AVLTree * &racine);
  70     // this one is for removals
  71     int RestoreBalances(int diff, AVLTree * &racine);
  72
  73     // startNode is the node where the rebalancing starts; rebalancing then moves up the tree to the root
  74     // diff is the change in "subtree height", as needed for the rebalancing
  75     // racine is the reference to the root, since rebalancing can change it too
  76     int Remove(AVLTree * &racine, AVLTree * &startNode, int &diff);
  77
  78     void insertOn(Side s, AVLTree *of);
  79     void insertBetween(AVLTree *l, AVLTree *r);
  80     AVLTree *leaf(AVLTree *from, Side s);
  81     AVLTree *leafFromDad(AVLTree *from, Side s);
  82 };
  83
  84 #endif
  85
  86 /*
  87   Local Variables:
  88   mode:c++
  89   c-file-style:"stroustrup"
  90   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  91   indent-tabs-mode:nil
  92   fill-column:99
  93   End:
  94 */
  95 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :