Arbres equilibres rouges et noirs

Soyez le premier à donner votre avis sur cette source.

Vue 9 722 fois - Téléchargée 1 074 fois

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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
3
on devrait demander cette nouvelle denomination a l'academie francaise !
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
23
oeuvres "open source", encore une de bonne, je note.
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

il y a des chances que ça ait à voir avec les oeuvres littéraires open source du bonhomme, je pense ^^.
Messages postés
921
Date d'inscription
vendredi 20 décembre 2002
Statut
Membre
Dernière intervention
23 septembre 2010

Et dans toutes ces méditations métaphysiques, pourquoi on appelle ça les arbres de Stendhal ?
C'est un jeu de mots ?
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

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 ^^.
Afficher les 17 commentaires

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.