Arbres equilibres rouges et noirs

Télécharger le projet
Commenter

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 / Exemple : 


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
  //
Télécharger le projet

Codes Sources

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)