ARBRES EQUILIBRES ROUGES ET NOIRS arbre, équilibré, rouge, noir, Source N°33374

Information sur la source

Catégorie :Maths & Algorithmes Classé sous : arbre, équilibré, rouge, noir Niveau : Débutant Date de création : 22/08/2005 Vu / téléchargé: 3 583 / 534

Auteur : JCDjcd

Ecrire un message privé

Ce membre participe au partage de revenus publicitaires

Note :
Aucune note

Commentaire sur cette source (17)

Ajouter un commentaire et/ou une note

Description

voici une implementation des arbres rouges et noirs
la hauteur maximale pour un arbre rouge et noir est h=2.log(n+1)
ceci se demontre avec une petite recurrence sur la "hauteur noire"

la hauteur noire d'une arbre est le nombre de noirs sur tout un chemin (jusqu'en bas de la genealogie)

les proprietes des arbres rouges et noirs sont :
1) les fils eventuels d'une noeud rouge sont noirs
2) les hauteurs noires a gauche et a droite de chaque noeud sont egales

Source

l'API des arbres rouges et noirs est :
* RB_TREE pour un arbre
* NODE_RB_TREE pour un noeud d'arbre rouge et noir
//----------------------------------------------------------
// RB_TREE
//----------------------------------------------------------
//
// permet de gerer les arbres equilibres rouges et noirs
// les operations possibles sur les arbres sont :
//
// * InitRBTree : initialise un arbre
// * SetKeyNodeRBTree : attribu une cle
// * GetKeyNodeRBTree : donne la valeur une cle
// * IsEmptyRBTree : est-ce-que l'arbre est vide
// * CloseRBTree : ferme un arbre
// * NextNodeRBTree : l'element suivant (plus grand), le successeur
// * PrevNodeRBTree : l'element precedant (plus petit), le predecesseur
// * MinNodeRBTree : l'element le plus petit
// * MaxNodeRBTree : l'element le plus grand
// * InsertNodeRBTree : insert un nouvel element
// * RemoveNodeRBTree : enleve un element
// * SearchNodeRBTree : recherche un element
//

l'API des arbres rouges et noirs est :

  * RB_TREE pour un arbre
  * NODE_RB_TREE pour un noeud d'arbre rouge et noir

  //----------------------------------------------------------
  //	RB_TREE
  //----------------------------------------------------------
  // 
  // permet de gerer les arbres equilibres rouges et noirs
  // les operations possibles sur les arbres sont :
  // 
  //  * InitRBTree              : initialise un arbre
  //  * SetKeyNodeRBTree        : attribu une cle
  //  * GetKeyNodeRBTree        : donne la valeur une cle
  //  * IsEmptyRBTree           : est-ce-que l'arbre est vide
  //  * CloseRBTree             : ferme un arbre
  //  * NextNodeRBTree          : l'element suivant (plus grand), le successeur
  //  * PrevNodeRBTree          : l'element precedant (plus petit), le predecesseur
  //  * MinNodeRBTree           : l'element le plus petit
  //  * MaxNodeRBTree           : l'element le plus grand
  //  * InsertNodeRBTree        : insert un nouvel element
  //  * RemoveNodeRBTree        : enleve un element
  //  * SearchNodeRBTree        : recherche un element
  //

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

data.c 56 875 octets
data.h 19 932 octets

Télécharger le zip

Sources du même auteur

Toutes les sources de JCDjcd

Sources de la même categorie

Toutes les sources de la catégorie Maths & Algorithmes

Sources en rapport avec celle ci

Commentaires

Commentaire de AlexMAN le 22/08/2005 16:30:24

J'ai cru entendre que tous ces Assert() nuisaient aux perfs, est ce bien vrai ? Et pis faut dire (sans mechanceté) que ca ne facilite pas la lecture
Commentaire de JCDjcd le 22/08/2005 16:54:34

c'est vrai que ils nuisent aux perfs, mairs seulement en DEBUG
en RELEASE il s'enleve, et le programme va normalement
le temps d'execution perdu en DEBUG vaut bien le temps en moins pour debugger le programme
Commentaire de BruNews le 22/08/2005 23:32:23 administrateur CS

Ce sont les arbres de Stendhal.
Commentaire de Saros le 23/08/2005 18:45:55

J'ai quelques petits problèmes pour compiler :(
Ca passe pas sous DevCPP et VC, faut télécharger un compilateur C uniquement ?
J'en ai essayé un, ça marche pas non plus
Commentaire de BruNews le 23/08/2005 19:20:40 administrateur CS

Normal il n'y a pas de prog de test, tu peux juste compiler en librairie.
Commentaire de JCDjcd le 23/08/2005 19:39:37

// un test qui martirise les arbres
InitLibUtil();
  {
  int               i,n;
  RB_TREE           tree;
  P_NODE_RB_TREE    node;

  SetRandom(GetTickCount());
  InitRBTree(&tree,cmpInt,NULL);

  n     = 10000;
  node  = Malloc(NODE_RB_TREE,n);

  for(i=0;i<n;i++)
    {
    do
      {
      int k;
      k = RandomInt(1,100*n);
      if(NULL == SearchNodeRBTree(&tree,(void*)k))
        {
        SetKeyNodeRBTree(node + i,(void*)k);
        InsertNodeRBTree(&tree,node + i);
        break;
        }
      }while(TRUE);
    }

  AssertRBTree(&tree,TRUE);

  while(0 < tree.tree.nElem)
    {
    P_NODE_RB_TREE rem;
    rem = randNode(&tree);
    RemoveNodeRBTree(&tree,rem);
    AssertRBTree(&tree,TRUE);
    }

  Free(node);

  CloseRBTree(&tree);
  }
CloseLibUtil();
Commentaire de Saros le 23/08/2005 20:58:41

Je vais peut-être paraître philistin, mais comment on l'utilise ta librairie pour que ton exemple fonctionne ?
On la traite à part, on l'intègre au projet, ... ?
Commentaire de JCDjcd le 23/08/2005 22:40:10

il faut faire :

un projet contenant tout le .c et .h qui sont a telecharger PLUS un fichier main.c que tu crées avec dedans :
//-------------------------------------------------
#ifndef _UTIL_H_
#include "util.h"
#endif // _UTIL_H_

#ifndef _MATH_H_
#include "math.h"
#endif // _MATH_H_

#ifndef _DATA_H_
#include "data.h"
#endif // _DATA_H_

//-------------------------------------------------
int main(iot argc,char **argv)
{
// ici le code que je t'ai mis plus haut
} // main()

et puis ton compile ton projet
les fichiers data.c et data.h sont a interger dans le projet
Commentaire de Kirua le 03/09/2005 01:59:52

"Ce sont les arbres de Stendhal"

Euh, je veux bien qu'il ait écrit le bouquin, mais à mon avis ça ne parlait pas de ça ^^ C'était juste un trait d'humour, ou on appelle vraiment ça comme ça?
Commentaire de JCDjcd le 03/09/2005 09:45:03

Je crains que ce ne soit pas Julien Sorel qui est invente les arbres Rouges et Noirs ...
Commentaire de Kirua le 03/09/2005 12:47:20

hmm, je ne savais pas que Nix avait un frère...
Commentaire de JCDjcd le 03/09/2005 13:10:19

c'était facile ...
Commentaire de Kirua le 03/09/2005 13:12:04

Atta, avec mon départ en vacances pendant un mois tout ça, j'ai mis bien 20 secondes avant de mon souvenir d'où je connaissais ce nom ^^.
Commentaire de Saros le 03/09/2005 15:52:19

Et dans toutes ces méditations métaphysiques, pourquoi on appelle ça les arbres de Stendhal ?
C'est un jeu de mots ?
Commentaire de Kirua le 03/09/2005 16:02:40

il y a des chances que ça ait à voir avec les oeuvres littéraires open source du bonhomme, je pense ^^.
Commentaire de BruNews le 03/09/2005 16:33:30 administrateur CS

oeuvres "open source", encore une de bonne, je note.
Commentaire de JCDjcd le 03/09/2005 21:09:28

on devrait demander cette nouvelle denomination a l'academie francaise !