Arbre binaire (non-equilibre)

Commenter

Contenu du snippet

programme qui montre comment programmer les operations usuelles
sur les arbres binaires equilibres

Source / Exemple : 


//----------------------------------------------------------
  //	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()

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_JCDjcd)