SHARE
TWEET

Untitled

a guest Dec 14th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "RN_arbre.h"
  2. #include <vector>
  3. #include "Noeud.h"
  4.  
  5. using namespace std;
  6.  
  7. const int BLACK = 0;
  8. const int RED = 1;
  9.  
  10. vector<int>::iterator ptr;
  11.  
  12. RN_arbre::RN_arbre()
  13. {
  14. }
  15.  
  16. RN_arbre::RN_arbre(vector<int> tableau)
  17. {
  18.     this->nil = new Noeud(BLACK);
  19.     this->root = new Noeud(BLACK);
  20.  
  21.     for (ptr = tableau.begin(); ptr < tableau.end(); ptr++) {
  22.         arbre_inserer(tableau[*ptr]);
  23.     }
  24.  
  25.  
  26. }
  27.  
  28. RN_arbre::~RN_arbre()
  29. {
  30. }
  31.  
  32. void RN_arbre::affiche()
  33. {
  34.     cout << "Les noeuds de l'arbre sont: ";
  35. }
  36.  
  37. void RN_arbre::arbre_inserer(int i) {
  38.     Noeud* n = new Noeud(i, RED, 0, this->nil, this->nil, this->nil, this->nil, this->nil);
  39.  
  40.     Noeud* tempNil = new Noeud(0, BLACK, 0, this->nil, this->nil, this->nil, this->nil, this->nil);
  41.     tempNil = this->nil;
  42.     Noeud* tempRoot = new Noeud(0, RED, 0, this->nil, this->nil, this->nil, this->nil, this->nil);
  43.     tempRoot = this->root;
  44.     while (tempRoot != this->nil) { //x part de la racine et descend jusqu'à nil
  45.         tempNil = tempRoot;
  46.         if (n->getKey() < tempRoot->getKey()) {
  47.             tempRoot = tempRoot->getEnfantGauche();
  48.         }
  49.         else {
  50.             tempRoot = tempRoot->getEnfantDroit();
  51.         }
  52.     }
  53.     n->setParent(tempNil);
  54.     if (tempNil == this->nil){ // Arbre est vide (n est la racine)
  55.         this->root = n;
  56.     }
  57.     else if (n->getKey() < tempNil->getKey()) { // Si la clé de n est plus petite que celle de son noeud parent
  58.         tempNil->setEnfantGauche(n);
  59.     }
  60.     else { // Si la clé de n est plus petite que celle de son noeud parent
  61.         tempNil->setEnfantDroit(n);
  62.     }
  63.     n->setEnfantGauche(this->nil);
  64.     n->setEnfantDroit(this->nil);
  65.     n->setCouleur(RED);
  66.     inserer_correction_rn(this->root);
  67. }
  68.  
  69. void RN_arbre::inserer_correction_rn(Noeud* n) {
  70.     Noeud* y = this->nil;
  71.     while (n->getParent()->getCouleur() == RED) {
  72.         if (n->getParent() == n->getParent()->getParent()->getEnfantGauche()) {
  73.             y = n->getParent()->getParent()->getEnfantDroit();
  74.             if (y->getCouleur() == RED) {
  75.                 n->getParent()->setCouleur(BLACK);
  76.                 y->setCouleur(BLACK);
  77.                 n->getParent()->getParent()->setCouleur(RED);
  78.                 n = n->getParent()->getParent();
  79.             }
  80.             else if (n == n->getParent()->getEnfantDroit()) {
  81.                 n = n->getParent();
  82.                 //left rotate
  83.                 n->getParent()->setCouleur(BLACK);
  84.                 n->getParent()->getParent()->setCouleur(RED);
  85.                 //right rotate
  86.             }
  87.         }
  88.         else {
  89.                 //
  90.                 y = n->getParent()->getParent()->getEnfantGauche();
  91.                 if (y->getCouleur() == RED) {
  92.                     n->getParent()->setCouleur(BLACK);
  93.                     y->setCouleur(BLACK);
  94.                     n->getParent()->getParent()->setCouleur(RED);
  95.                     n = n->getParent()->getParent();
  96.                 }
  97.                 else if (n == n->getParent()->getEnfantGauche()) {
  98.                     n = n->getParent();
  99.                     //right rotate
  100.                     n->getParent()->setCouleur(BLACK);
  101.                     n->getParent()->getParent()->setCouleur(RED);
  102.                     //left rotate
  103.                 }
  104.         }
  105.     }
  106.    
  107.     this->root->setCouleur(BLACK);
  108. }
  109.  
  110. /*int RN_arbre::lire_rang(int x) {
  111.    
  112. }*/
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top