AVL

avl.c

#include<stdio.h>
#include<malloc.h>
#include"avl.h"

/*------------------------------------------------------*/

/*
  Noeud de l'ABR.
 */

typedef struct nd
{
  /*
    key est la cle du noeud courant.
   */
  int key;

  /*
    pointeur vers l'element de cle key
   */
  void* data;

  /*
    hauteur du sous-arbre : 
    0 si ce noeud est une feuille. 
   */
  int height;
  
  /*
    Pointeur vers le sous-arbre droit.
   */
  struct nd * left;

  /*
    Pointeur vers le sous-arbre gauche.
   */
  struct nd * right;  
}node;

/*------------------------------------------------------*/

/*
  Retourne la hauteur de l'arbre de racine l, 
  -1 si l est vide.
 */

int getHeight(node* l)
{
  if (l == NULL)
    return -1;
  return l->height;
}

/*------------------------------------------------------*/

/*
  Retourne la plus grande des deux valeurs i et j.
 */

int max(int i, int j)
{
  if (i < j)
    return j; 
  return i;
}

/*------------------------------------------------------*/

/*
  Met a jour la hauteur de la racine l en fonction des 
  hauteurs des racines des deux sous-arbres.
 */

void setHeight(node* l)
{
  if (l != NULL)
    {
        l->height = 1 + max(getHeight(l->left), getHeight(l->right));
    }
}

/*------------------------------------------------------*/

/*
  Cree un noeud contenant la donnee data, 
  ayant pour sous-arbre gauche l et 
  pour sous-arbre droit r.
*/

node* nodeCreate(int (*getKey)(void*), node* l, void* data, node* r)
{
  node* n = (node*)malloc(sizeof(node));
  if (n == NULL)
    error();
  n->data = data;
  n->left = l;
  n->right = r;
  n->key = getKey(data);
  setHeight(n);
  return n;
}

/*------------------------------------------------------*/

/*
  Retourne un avl vide
*/

avl* avlCreate(int (*getKey)(void*), void (*freeData)(void*))
{
  avl* a = (avl*)malloc(sizeof(avl));
  if (!a)
    error();
  a->getKey = getKey;
  a->freeData = freeData;
  a->root = NULL;
  return a;
}

/*------------------------------------------------------*/

/*
  Fait de freeData la fonction de destruction des donnees.
*/

void avlSetFreeFunction(avl* a, void (*freeData)(void*))
{
  a->freeData = freeData;
}

/*------------------------------------------------------*/

/*
  Affiche toutes les cles du sous-arbre de racine n dans 
  l'ordre croissant.
*/

void nodePrintKeys(node* n)
{
  if(n)
    {
      printf("(");
      nodePrintKeys(n->left);
      printf(", %d, ", n->key );
      nodePrintKeys(n->right);
      printf(")");
    }
}

/*------------------------------------------------------*/

/*
  Affiche pour tous les noeuds du sous-arbre de racine n
  la difference entre les hauteurs du sous-arbre droit et 
  gauche.
*/

void nodePrintLevels(node* n)
{
  if(n)
    {
      printf("(");
      nodePrintLevels(n->left);
      printf(", %d, ", getHeight(n->left)- getHeight(n->right));
      nodePrintLevels(n->right);
      printf(")");
    }
}

/*------------------------------------------------------*/

/*
  Effectue une rotation droite de l'arbre de racine x, 
  retourne la racine de l'arbre apres rotation.
 */

node* rotateRight(node* x)
{
  node* y = x->left;
  node* b = y->right;
  y->right = x;
  x->left = b;
  setHeight(x);
  setHeight(y);  
  return y;
}

/*------------------------------------------------------*/

/*
  Effectue une rotation gauche de l'arbre de racine x, 
  retourne la racine de l'arbre apres rotation.
 */

node* rotateLeft(node* x)
{
  node* y = x->right;
  node* b = y->left;
  y->left = x;
  x->right = b;
  setHeight(x);
  setHeight(y);  
  return y;
}

/*------------------------------------------------------*/

/*
  Effectue une rotation gauche-droite de l'arbre de racine x, 
  retourne la racine de l'arbre apres rotation.
 */

node* rotateLeftRight(node* x)
{
  x->left = rotateLeft(x->left);
  return rotateRight(x);
}

/*------------------------------------------------------*/

/*
  Effectue une rotation droite-gauche de l'arbre de racine x, 
  retourne la racine de l'arbre apres rotation.
 */

node* rotateRightLeft(node* x)
{
  x->right = rotateRight(x->right);
  return rotateLeft(x);
}

/*------------------------------------------------------*/

/*
  Reequilibre l'arbre de racine x, retourne la racine de 
  l'arbre apres reequilibrage. On part du principe 
  que les hauteurs des sous-arbres droit et gauche different 
  de au plus 1.
*/

node* balance(node* x)
{
  if (x != NULL)
    {
      setHeight(x);
      if (getHeight(x->left) + 2 == getHeight(x->right))
	{
	  if(getHeight(x->left) + 1 == getHeight(x->right->right))
	    return rotateLeft(x);
	  else
	    return rotateRightLeft(x);
	}
      if (getHeight(x->left) == getHeight(x->right) + 2)
	{
	  if(getHeight(x->left->left) == getHeight(x->right) + 1)
	    return rotateRight(x);
	  else
	    return rotateLeftRight(x);
	}
    }
  return x;
}

/*------------------------------------------------------*/

/*
  Insere la donnee v dans l'arbre de racine n 
  et reequilibre l'arbre, retourne la racine de 
  l'arbre apres insertion et reequilibrage.
 */

node* nodeInsert(int (*key)(void*), node* n, void* v)
{
  if(n == NULL)
    return nodeCreate(key, NULL, v, NULL);
  if(key(v) == n->key)
    return n;
  if(key(v) < n->key)
    n->left = nodeInsert(key, n->left, v);
  else
    n->right = nodeInsert(key, n->right, v);
  return balance(n);
}

/*------------------------------------------------------*/

/*
  Insere la donnee v dans l'arbre a, O(log n).
*/

void avlInsert(avl* a, void* v)
{
  a->root = nodeInsert(a->getKey, (node*)a->root, v);
}

/*------------------------------------------------------*/
 
/*
  Affiche les cles de l'AVL a dans l'ordre croissant, O(n)
*/

void avlPrintKeys(avl* a)
{
  nodePrintKeys((node*)a->root);
  printf("\n");
}

/*------------------------------------------------------*/
 
/*
  Affiche pour chaque noeud la difference entre les hauteurs 
  des sous-arbres droit et gauche de l'AVL. 
*/

void avlPrintLevels(avl* a)
{
  nodePrintLevels((node*)a->root);
  printf("\n");
}

/*------------------------------------------------------*/

/*
  Retourne la donnee de cle k si elle se trouve dans le sous-arbre 
  de racine n, NULL sinon.
*/

void* findNode(node* n, int k)
{
  if (n == NULL)
    return NULL;
  if (n->key == k)
    return n->data;
  if (k < n->key)
    return findNode(n->left, k);
  else
    return findNode(n->right, k);
}
 
/*------------------------------------------------------*/
 
/*
  Retourne la donnee de cle x si elle se trouve dans l'AVL a,
  NULL sinon, O(log n)
*/

void* avlFind(avl* a, int x)
{
  return findNode((node*)a->root, x);
}

/*------------------------------------------------------*/

/*
  Fait pointer *max vers le noeud de cle maximale dans 
  le sous-arbre de racine n, detache le noeud *max de l'arbre
  et retourne la racine de l'arbre apres suppression.
*/

node* removeMax(node* n, node** max)
{
  if (n == NULL)
    {
      *max = NULL;
      return NULL;
    }
  if (n->right == NULL)
    {
      *max = n;
      return NULL;
    }
  n->right = removeMax(n->right, max);
  return balance(n);
}

/*------------------------------------------------------*/

/*
  Fait pointer *min vers le noeud de cle minimale dans 
  le sous-arbre de racine n, detache le noeud *min de l'arbre
  et retourne la racine de l'arbre apres suppression.
*/

node* removeMin(node* n, node** min)
{
 if (n == NULL)
    {
      *min = NULL;
      return NULL;
    }
  if (n->left == NULL)
    {
      *min = n;
      return NULL;
    }
  n->left = removeMin(n->left, min);
  return balance(n);
}

/*------------------------------------------------------*/

/*
  Supprime le noeud de cle k du sous-arbre de racine n,
  applique la fonction de destruction a la donnee de ce noeud,
  et retourne la racine de l'arbre apres la suppression.  
*/

node* removeNode(node* n, int k, void (*freeData)(void*))
{
  node* p;
  if (n == NULL)
    return NULL;
  if (k == n->key)
    {
      p = NULL;
      n->left = removeMax(n->left, &p);
      if (p == NULL)
	n->right = removeMin(n->right, &p);
      if (p != NULL)
	{
	  p->left = n->left;
	  p->right = n->right;
	}
      freeData(n->data);
      free(n);
      return balance(p);
    }
  if (k < n->key)
    n->left = removeNode(n->left, k, freeData);
  else
    n->right = removeNode(n->right, k, freeData);
  return balance(n);
}

/*------------------------------------------------------*/
 
/*
  Supprime le noeud de cle k de l'AVL a, applique la fonction 
  de destruction a la donnee de cle k, O(log n).
*/

void avlRemove(avl* a, int k)
{
  a->root = removeNode((node*)a->root, k, a->freeData);
}

/*------------------------------------------------------*/

/*
  Place dans la liste chainee l toutes les donnees 
  du sous-arbre de racine n dans l'ordre croissant.
 */

void nodeToList(node* n, linkedList* l)
{
  if (n != NULL)
    {
      nodeToList(n->left, l);
      linkedListAppend(l, n->data);
      nodeToList(n->right, l);      
    }
}

/*------------------------------------------------------*/

/*
  Retourne une liste chainee contenant toutes les donnees
  de l'AVL a disposees dans l'ordre croissant, O(n).
 */

linkedList* avlToList(avl* a)
{
  linkedList* l = linkedListCreate();
  nodeToList((node*)a->root, l);
  return l;
}

/*------------------------------------------------------*/

/*
  Detruit tous les noeuds du sous-arbre de racine n, 
  applique la fonction de destruction fr a toutes les 
  donnees du sous-arbre.
*/

void nodeDestroy(node* n, void (*fr)(void*))
{
  if (n != NULL)
    {
      nodeDestroy(n->left, fr);
      nodeDestroy(n->right, fr);      
      fr(n->data);
      free(n);
    }
}
  
/*------------------------------------------------------*/

/*
  Detruit l'AVL a, applique la fonction de destruction a 
  toutes les donnees du sous-arbre, O(n).
*/

void avlDestroy(avl* a)
{
  nodeDestroy((node*)a->root, a->freeData);
  free(a);
}

/*------------------------------------------------------*/
/*------------------------------------------------------*/

/*
Pour tester les algorithmes
*/

void destroyInt(void* i)
{
  free((int*)i);
}

int getIntKey(void* i)
{
  return *((int*)i);
}

void doNothing()
{
  
}

int main()
{
  int i;
  int* d;
  linkedList* l;
  link* m;
  avl* a = avlCreate(getIntKey, destroyInt);
  for (i = 0 ; i < 40 ; i++)
    {
      d = (int*)malloc(sizeof(int));
      *d = i;
      avlInsert(a, d);
    }
  avlPrintKeys(a);
  avlPrintLevels(a);
  for(i = 0 ; i < 40 ; i+=5)
    avlRemove(a, i);
  avlPrintKeys(a);
  avlPrintLevels(a);
  l = avlToList(a);
  for(m = linkedListGetFirst(l); m != NULL ; m = m->next)
    printf("%d -> ", *(int*)(m->data));  
  printf("\n");
  linkedListDestroy(l, doNothing);
  avlSetFreeFunction(a, destroyInt);
  avlDestroy(a);
  return 0;
}