ARBRE BINAIRE (NON-EQUILIBRE)

  //----------------------------------------------------------
  //	TREE
  //----------------------------------------------------------
  // 
  // permet de gerer les arbres non-equilibres
  // les operations possibles sur les arbres sont :
  // 
  //  * InitTree              : initialise un arbre
  //  * SetKeyNodeTree        : attribu une cle
  //  * GetKeyNodeTree        : donne la valeur une cle
  //  * IsEmptyTree           : est-ce-que l'arbre est vide
  //  * CloseTree             : ferme un arbre
  //  * NextNodeTree          : l'element suivant (plus grand), le successeur
  //  * PrevNodeTree          : l'element precedant (plus petit), le predecesseur
  //  * MinNodeTree           : l'element le plus petit
  //  * MaxNodeTree           : l'element le plus grand
  //  * InsertNodeTree        : insert un nouvel element
  //  * RemoveNodeTree        : enleve un element
  //  * SearchNodeTree        : recherche un element
  //  * LeftRotationNodeTree  : rotation gauche sur un noeud
  //  * RightRotationNodeTree : rotation droite sur un noeud
  // 
  typedef struct tagNODE_TREE
    {
    struct tagNODE_TREE    *parent; // parent
    struct tagNODE_TREE    *left;   // fils de gauche
    struct tagNODE_TREE    *right;  // fils de droite
    void                   *key;    // cle de tri    
    }NODE_TREE,*P_NODE_TREE,**PP_NODE_TREE;

  typedef struct tagTREE
    {
    int           nElem;    // nombre d'elements
    CMP_FUNC      cmpFunc;  // fonction de comparaison
    void         *param;    // parametre pour la fonction de comparaison
    P_NODE_TREE   root;     // racine de l'arbre
    }TREE,*P_TREE,**PP_TREE;

//----------------------------------------------------------
//	TREE
//----------------------------------------------------------
#if DBG_LIB_DATA_TREE == DBG_ON
static int checkTree(P_TREE tree,P_NODE_TREE node)
{
int n;                              // le nombre de noeuds
AssertNodeTree(tree,node);          // verification du noeud
n = 1;                              // on compte le noeud courant
if(NULL != node->left )             // on verifie l'arboresence gauche
  n += checkTree(tree,node->left);
if(NULL != node->right)             // on verifie l'arboresence droite
  n += checkTree(tree,node->right);

                                    // on verifie que l'ordre est repecte
if(NULL != node->left && NULL != node->right)
  Assert(CMP_LESS == tree->cmpFunc(node->left->key,node->right->key,tree->param));

// on retourne le nombre de noeuds
return n;
} // checkTree()

void _AssertTree(P_TREE tree,BOOL bWholeChecking)
{
AssertPointer(tree);
AssertPointer(tree->cmpFunc);

if(0 == tree->nElem)
  {
  Assert(NULL == tree->root);
  }
else
  {
  int rnd;
  Assert(tree->nElem > 0);
  // la verification doit etre en O(1)
  // donc on l'effectue de temps en temps i.e. tout les 1 fois sur n
  // or la verification de l'arbre est en O(n), donc globalement
  // c'est en O(1)
  rnd = RandomInt(1,tree->nElem);
  if(bWholeChecking || (1 == rnd))
    {
    int n;
    n = checkTree(tree,tree->root);
    Assert(tree->nElem == n);
    }
  }
PopErrorMacro();
} // _AssertTree()
#endif // DBG_LIB_DATA_TREE == DBG_ON


//----------------------------------------------------------
#if DBG_LIB_DATA_TREE == DBG_ON
void _AssertNodeTree(P_TREE tree,P_NODE_TREE node)
{
AssertPointer(node);                                    // verification du noeud
if(NULL != node->parent)  AssertPointer(node->parent);  // verification du parent
if(NULL != node->left  )  AssertPointer(node->left  );  // verification du fils gauche
if(NULL != node->right )  AssertPointer(node->right );  // verification du fils droit

if(NULL != node->parent)                                // est-il bien le fils de son pere ?
  Assert(node->parent->left == node || node->parent->right == node);

if(NULL != node->right && NULL != node->left)
  {
  Assert(node->left   != node->right);                  // les jumeaux sont interdits !
  Assert(node->parent != node->left);                   // le fils (gauche) ne peut etre le pere
  Assert(node->parent != node->right);                  // le fils (droit)  ne peut etre le pere
  }
PopErrorMacro();
} // _AssertNodeTree()
#endif // DBG_LIB_DATA_TREE == DBG_ON


//----------------------------------------------------------
// fonction en interne
// calcul le minimum a partir d'un noeud
static P_NODE_TREE minNode(P_NODE_TREE root)
{
P_NODE_TREE min;
min = root;
if(NULL != min)
  {
  // les elements plus petits sont a gauche de l'arbre
  while(NULL != min->left)
    {    
    min = min->left;
    }
  }
return min;
} // minNode()


//----------------------------------------------------------
// fonction en interne
// calcul le maximum a partir d'un noeud
static P_NODE_TREE maxNode(P_NODE_TREE root)
{
P_NODE_TREE max;
max = root;
if(NULL != max)
  {
  // les elements plus petits sont a droite de l'arbre
  while(NULL != max->right)
    {
    max = max->right;
    }
  }
return max;
} // maxNode()


//----------------------------------------------------------
// fonction en interne
// retourne l'adresse du pointeur qui pointe sur le noeud
static PP_NODE_TREE holdNode(P_TREE tree,P_NODE_TREE node)
{
P_NODE_TREE parent;

AssertNodeTree(tree,node);

parent = node->parent;

if(NULL == node->parent)        // si le parent n'existe pas, alors c'est la racine de l'arbre
  {
  return &tree->root;
  }
else if(node == parent->left)   // si c'est le fils gauche de son pere
  {
  return &parent->left;
  }
else                            // sinon c'est forcement le fils droit de son pere
  {
  Assert(node == parent->right);
  return &parent->right;
  }

} // holdNode()

//----------------------------------------------------------
P_TREE _InitTree(P_TREE tree,CMP_FUNC cmpFunc,void *param)
{
AssertPointer(tree);
AssertPointer(cmpFunc);

tree->cmpFunc     = cmpFunc;
tree->param       = param;
tree->nElem       = 0;
tree->root        = NULL;

PopErrorMacro();
return tree;
} // _InitTree()


//----------------------------------------------------------
P_NODE_TREE _SetKeyNodeTree(P_NODE_TREE node,void *key)
{
AssertPointer(node);
node->key = key;
PopErrorMacro();
return node;
} // _SetKeyNodeTree()


//----------------------------------------------------------
void *_GetKeyNodeTree(P_NODE_TREE node)
{
AssertPointer(node);
PopErrorMacro();
return node->key;
} // _GetKeyNodeTree()


//----------------------------------------------------------
BOOL _IsEmptyTree(P_TREE tree)
{
AssertTree(tree,FALSE);
PopErrorMacro();
return NULL == tree->root;
} // _IsEmptyTree()



//----------------------------------------------------------
P_TREE _CloseTree(P_TREE tree)
{
AssertTree(tree,FALSE);
Assert(0    == tree->nElem);
Assert(NULL == tree->root);
PopErrorMacro();
return tree;
} // _CloseTree()


//----------------------------------------------------------
P_NODE_TREE _NextNodeTree(P_TREE tree,P_NODE_TREE node)
{
P_NODE_TREE next;

AssertTree(tree,FALSE);
AssertNodeTree(tree,node);

// s'il y a un fiston droit, alors il existe des elements
// plus grands que le noeud courant, et plus petits que
// son pere, le plus petit des noeuds ayants cette
// propriete est le successeur du noeud courant
if(NULL != node->right)
  {
  next = minNode(node->right);
  }
// s'il n'y a pas de fiston droit, le successeur ne se trouve
// pas a gauche car le successeur est plus grand que le noeud
// 
// pour comprendre la logique, voici l'arbre suivant avec
// les petites lettres sont les noeuds dont on cherche leurs
// successeurs respectifs notes en majuscules :
// 
//            D
//           / \
//          /   \
//         /     \
//        /       \
//       /         \
//      B           F
//     / \         / \
//    /   \       /   \
//   A     C     E     G
//  / \   / \   / \   / \
// a   b c   d e   f g   h   (H n'existe pas)
// 
// la logique est alors tres simple, le successeur est parmi
// ses ancetres (pere, grand-pere, ou arrier-grand-pere
// dans l'exemple ci-dessus)
// le successeur est le plus jeune des ancetres dont
// son fils (qui appartient aux ancetres) est un fils gauche
// mais s'il n'y a plus de parent, alors il n'y a pas de successeur
// 
// c'est par cette logique que l'on construit l'exemple du dessus
// et maintenant il est facile de trouve le successeur
// 
else
  {
  P_NODE_TREE x; // x represente l'ancetre fils
  P_NODE_TREE y; // x represente l'ancetre pere

  x = node;
  y = node->parent;

  // tant que l'on est dans la configuration ci-dessous
  // on remonte dans l'arbre genealogique
  // 
  //   y
  //  / \
  // ?   x
  // 
  while(
        (NULL != y)     // s'il y a un pere
          &&
        (x == y->right) // si c'est le fils droit
        )
    {
    // on remonte dans l'arbre genealogique
    x = y;
    y = y->parent;
    AssertNodeTree(tree,x);
    AssertNodeTree(tree,y);
    }

  // le successeur est le pere, et le fils est un fils gauche
  // 
  //     y     <------ successeur
  //    / \
  //   x   ?
  //  / \
  // ?   ...   <------ chemin qui mene au noeud dont on cherche le successeur      
  next = y;
  }

Assert(NULL == next || (AssertNodeTree(tree,next),TRUE));
PopErrorMacro();
return next;
} // _NextNodeTree()


//----------------------------------------------------------
P_NODE_TREE _PrevNodeTree(P_TREE tree,P_NODE_TREE node)
{
P_NODE_TREE prev;

AssertTree(tree,FALSE);
AssertNodeTree(tree,node);

// s'il y a un fiston gauche, alors il existe des elements
// plus petits que le noeud courant, et plus grands que
// son pere, le plus grand des noeuds ayants cette
// propriete est le predecesseur du noeud courant
if(NULL != node->left)
  {
  prev = maxNode(node->left);
  }
// s'il n'y a pas de fiston gauche, le predecesseur ne se trouve
// pas a droite car le predecesseur est plus petit que le noeud
// 
// pour comprendre la logique, voici l'arbre suivant avec
// les petites lettres sont les noeuds dont on cherche leurs
// predecesseur respectifs notes en majuscules :
// 
//            E
//           / \
//          /   \
//         /     \
//        /       \
//       /         \
//      C           G
//     / \         / \
//    /   \       /   \
//   B     D     F     H
//  / \   / \   / \   / \
// a   b c   d e   f g   h   (A n'existe pas)
// 
// la logique est alors tres simple, le predecesseur est parmi
// ses ancetres (pere, grand-pere, ou arrier-grand-pere
// dans l'exemple ci-dessus)
// le predecesseur est le plus jeune des ancetres dont
// son fils (qui appartient aux ancetres) est un fils droit
// mais s'il n'y a plus de parent, alors il n'y a pas de predecesseur
// 
// c'est par cette logique que l'on construit l'exemple du dessus
// et maintenant il est facile de trouve le predecesseur
// 
else
  {
  P_NODE_TREE x; // x represente l'ancetre fils
  P_NODE_TREE y; // x represente l'ancetre pere

  x = node;
  y = node->parent;

  // tant que l'on est dans la configuration ci-dessous
  // on remonte dans l'arbre genealogique
  // 
  //   y
  //  / \
  // x   ?
  // 
  while(
        (NULL != y)     // s'il y a un pere
          &&
        (x == y->left) // si c'est le fils gauche
        )
    {
    // on remonte dans l'arbre genealogique
    x = y;
    y = y->parent;
    AssertNodeTree(tree,x);
    AssertNodeTree(tree,y);
    }

  // le predecesseur est le pere, et le fils est un fils gauche
  // 
  //     y         <------ predecesseur
  //    / \
  //   ?   x
  //      / \
  //     ?   ...   <------ chemin qui mene au noeud dont on cherche le predecesseur      
  prev = y;
  }

Assert(NULL == prev || (AssertNodeTree(tree,prev),TRUE));
PopErrorMacro();
return prev;
} // _PrevNodeTree()


//----------------------------------------------------------
P_NODE_TREE _MinNodeTree(P_TREE tree)
{
P_NODE_TREE min;
AssertTree(tree,FALSE);
min = minNode(tree->root);
Assert(NULL == min || (AssertNodeTree(tree,min),TRUE));
PopErrorMacro();
return min;
} // _MinNodeTree()


//----------------------------------------------------------
P_NODE_TREE _MaxNodeTree(P_TREE tree)
{
P_NODE_TREE max;
AssertTree(tree,FALSE);
max = maxNode(tree->root);
Assert(NULL == max || (AssertNodeTree(tree,max),TRUE));
PopErrorMacro();
return max;
} // _MaxNodeTree()


//----------------------------------------------------------
P_NODE_TREE _InsertNodeTree(P_TREE tree,P_NODE_TREE ins)
{

AssertTree(tree,FALSE);
AssertPointer(ins);

// le nouvel element n'aura pas de fistons
ins->left  = NULL;
ins->right = NULL;

// si l'arbre est vide, alors
if(NULL == tree->root)
  {
  tree->root  = ins;
  ins->parent = NULL;
  }
// on met nouvel element tout en bas de l'arbre
// comme une "feuille", mais on doit choisir la
// position suivant ca cle, pour cela on calcule
// quel element sera le parent que nouveau element
else
  {
  P_NODE_TREE parent; // le parent
  int         r;      // resultat des comparaisons

  parent = tree->root;
  while(TRUE)
    {
    AssertNodeTree(tree,parent);

    r = tree->cmpFunc(ins->key,parent->key,tree->param);

    // l'element se trouvera a gauche car il est plus petit
    if(CMP_LESS == r)
      {
      // on a trouve
      if(NULL == parent->left)
        {
        ins->parent  = parent;
        parent->left = ins;
        break;
        }
      // on continue
      else
        {
        parent = parent->left;
        }
      }
    // l'element se trouvera a droite car il est plus grand
    else
      {
      Assert(CMP_MORE == r);
      // on a trouve
      if(NULL == parent->right)
        {
        ins->parent   = parent;
        parent->right = ins;
        break;
        }
      // on continue
      else
        {
        parent = parent->right;
        }
      }      
    }
  }

tree->nElem ++;

AssertTree(tree,FALSE);

PopErrorMacro();
return ins;
} // _InsertNodeTree()


//----------------------------------------------------------
P_NODE_TREE _RemoveNodeTree(P_TREE tree,P_NODE_TREE rem)
{
P_NODE_TREE   parent; // le parent
P_NODE_TREE   left;   // le fils de gauche
P_NODE_TREE   right;  // le fils de droite
PP_NODE_TREE  pHold;  // celui qui pointe sur <rem>


AssertTree(tree,FALSE);
AssertNodeTree(tree,rem);

// pour la suppression d'un element on distingue
// trois cas :
// cas #1 : l'element n'a aucun fils
// cas #2 : l'element n'a qu'un fils
// cas #3 : l'element a deux fils
// 

left   = rem->left;
right  = rem->right;
parent = rem->parent;
pHold  = holdNode(tree,rem);
// il n'y a aucun fils
if(NULL == left && NULL == right)
  {
  *pHold = NULL;
  }
// il n'y a que le fils gauche (cas #2)
else if(NULL != left && NULL == right)
  {
  AssertNodeTree(tree,left);
  left->parent = parent;
  *pHold       = left;
  }
// il n'y a que le fils droit (cas #2)
else if(NULL == left && NULL != right)
  {
  AssertNodeTree(tree,right);
  right->parent = parent;
  *pHold        = right;
  }
// il y a les deux fils (cas #3)
else
  {
  P_NODE_TREE next; // le successeur

  AssertNodeTree(tree,left);
  AssertNodeTree(tree,right);
  // ce cas est le plus difficile
  // on supprime le successeur qui existe
  // forcement car il a un fils droit
  // donc le successeur est le minimum
  // du fils droit (la suppression
  // releve du cas #1 ou cas #2 car
  // le minimum ne peut avoir un fils gauche)
  // apres il suffit de substituer le successeur
  // a l'element sans modifier la validite de l'arbre
  next = minNode(rem->right);
  AssertNodeTree(tree,next);
  Assert(NULL == next->left);
  RemoveNodeTree(tree,next);

  // le membre de droite a peut-etre change
  // et est peut-etre nul
  // en revanche le membre de gauche est non-nul
  right = rem->right;
    
  if(NULL != right)
    right->parent  = next;    // nouveau parent pour le fils droit
  left->parent     = next;    // nouveau parent pour le fils gauche
  next->parent     = parent;  // nouveau parent pour le successeur
  *pHold           = next;    // nouveau fils pour le pere du successeur
  next->left       = left;    // nouveau fils gauche pour le successeur
  next->right      = right;   // nouveau fils droit pour le successeur
  tree->nElem ++;
  }

tree->nElem --;

AssertTree(tree,FALSE);

PopErrorMacro();
return rem;
} // _RemoveNodeTree()


//----------------------------------------------------------
P_NODE_TREE _SearchNodeTree(P_TREE tree,void *key)
{
P_NODE_TREE res,cur;

AssertTree(tree,FALSE);

res = NULL;
cur = tree->root;

while(NULL != cur)
  {
  int r;

  AssertNodeTree(tree,cur);

  r = tree->cmpFunc(key,cur->key,tree->param);
  // BINGO !
  if(CMP_EQUAL == r)
    {
    res = cur;
    break;
    }
  // l'element que l'on recherche est plus petit que l'element courant
  // donc celui que l'on recherche est necessairement a gauche
  else if(CMP_LESS == r)
    {
    cur = cur->left;
    }
  // l'element que l'on recherche est plus grand que l'element courant
  // donc celui que l'on recherche est necessairement a droite
  else
    {
    Assert(CMP_MORE == r);
    cur = cur->right;
    }
  }

PopErrorMacro();
return res;
} // _SearchNodeTree()


//----------------------------------------------------------
// 
//   x                 y
//  / \               / \
// a   y      ==>    x   c
//    / \           / \
//   b   c         a   b
//   
P_NODE_TREE _LeftRotationNodeTree(P_TREE tree,P_NODE_TREE x)
{
P_NODE_TREE   y;
P_NODE_TREE   b;
PP_NODE_TREE  pHold;

AssertTree(tree,FALSE);
AssertNodeTree(tree,x);

y = x->right;
AssertNodeTree(tree,y);

b = y->left;
Assert(NULL == b || (AssertNodeTree(tree,b),TRUE));

pHold     = holdNode(tree,x);   // le pointeur qui pointe sur <x>
*pHold    = y;                  // maintenant on le remplace pas <y>
y->parent = x->parent;          // le parent de <y> est l'ancien parent de <x>
y->left   = x;                  // le fils gauche de <y> est <x>
x->parent = y;                  // le parent de <x> est <y>
x->right  = b;                  // <b> est maintenant le fils droit de <x>
if(NULL != b) b->parent = x;    // le nouveau pere de <b> est <x>

PopErrorMacro();
return y;
} // _LeftRotationNodeTree()


//----------------------------------------------------------
// 
//     y              x
//    / \            / \
//   x   c    ==>   a   y
//  / \                / \
// a   b              b   c
//   
P_NODE_TREE _RightRotationNodeTree(P_TREE tree,P_NODE_TREE y)
{
P_NODE_TREE   x;
P_NODE_TREE   b;
PP_NODE_TREE  pHold;

AssertTree(tree,FALSE);
AssertNodeTree(tree,y);

x = y->left;
AssertNodeTree(tree,x);

b = x->right;
Assert(NULL == b || (AssertNodeTree(tree,b),TRUE));

pHold     = holdNode(tree,y);   // le pointeur qui pointe sur <y>
*pHold    = x;                  // maintenant on le remplace pas <x>
x->parent = y->parent;          // le parent de <x> est l'ancien parent de <y>
x->right  = y;                  // le fils droit de <x> est <y>
y->parent = x;                  // le parent de <y> est <x>
y->left   = b;                  // <b> est maintenant le fils gauche de <y>
if(NULL != b) b->parent = y;    // le nouveau pere de <b> est <y>

PopErrorMacro();
return x;
} // _RightRotationNodeTree()