Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - [C++] Red Black Tree : problema inserimento e cancellazione
Forum - C/C++ - [C++] Red Black Tree : problema inserimento e cancellazione

Avatar
light00 (Normal User)
Newbie


Messaggi: 1
Iscritto: 25/01/2017

Segnala al moderatore
Postato alle 23:24
Mercoledì, 25/01/2017
Buonasera, sto implementando un RBT per un progetto universitario, ma il codice ha un paio di bug..

Quando provo ad inserire nell'albero la sequenza di numeri 1 2 3 4 5 6 7 .. arrivati all'8 mi da segmentation fault!
Inoltre quando inserisco una quindicina di nodi, mi da sempre errore di segmentation fault.

L'altro bug è nel delete : A volte quando cancello la radice mi da segment, a volte non riesce proprio a cancellarla..
Per favore, se potete datemi na mano, perchè sto sbattendo la testa ma non riesco a capire dove siano gli errori :/

Questo il codice :
Codice sorgente - presumibilmente C/C++

  1. Metodo insert
  2. Codice: Seleziona tutto
  3. void RBtree::insert()
  4. {
  5.      int z,i=0;
  6.      cout<<"\nEnter key of the node to be inserted: "; cin>>z;
  7.      node *p,*q;
  8.      node *t=new node;
  9.      t->key=z;
  10.      t->left=NULL;
  11.      t->right=NULL;
  12.      t->color='r';
  13.      p=root;
  14.      q=NULL;
  15.      if(root==NULL)
  16.      {
  17.            root=t;
  18.            t->parent=NULL;
  19.      }
  20.      else
  21.      {
  22.          while(p!=NULL)
  23.          {
  24.               q=p;
  25.               if(p->key<t->key)
  26.                   p=p->right;
  27.               else
  28.                   p=p->left;
  29.          }
  30.          t->parent=q;
  31.          if(q->key<t->key)
  32.               q->right=t;
  33.          else
  34.               q->left=t;
  35.      }
  36.      insertfix(t);
  37. }
  38.  
  39.  
  40. Metodo insertfix
  41. Codice: Seleziona tutto
  42. void RBtree::insertfix(node *t)
  43. {
  44.      node *u;
  45.      if(root==t)
  46.      {
  47.          t->color='b';
  48.          return;
  49.      }
  50.      while(t->parent!=NULL&&t->parent->color=='r')
  51.      {
  52.            node *g=t->parent->parent;
  53.            if(g->left==t->parent)
  54.            {
  55.                         if(g->right!=NULL)
  56.                         {
  57.                               u=g->right;
  58.                               if(u->color=='r')
  59.                               {
  60.                                    t->parent->color='b';
  61.                                    u->color='b';
  62.                                    g->color='r';
  63.                                    t=g;
  64.                               }
  65.                         }
  66.                         else
  67.                         {
  68.                             if(t->parent->right==t)
  69.                             {
  70.                                  t=t->parent;
  71.                                  leftrotate(t);
  72.                             }
  73.                             t->parent->color='b';
  74.                             g->color='r';
  75.                             rightrotate(g);
  76.                         }
  77.            }
  78.            else
  79.            {
  80.                         if(g->left!=NULL)
  81.                         {
  82.                              u=g->left;
  83.                              if(u->color=='r')
  84.                              {
  85.                                   t->parent->color='b';
  86.                                   u->color='b';
  87.                                   g->color='r';
  88.                                   t=g;
  89.                              }
  90.                         }
  91.                         else
  92.                         {
  93.                             if(t->parent->left==t)
  94.                             {
  95.                                    t=t->parent;
  96.                                    rightrotate(t);
  97.                             }
  98.                             t->parent->color='b';
  99.                             g->color='r';
  100.                             leftrotate(g);
  101.                         }
  102.            }
  103.            root->color='b';
  104.      }
  105. }
  106.  
  107.  
  108. Metodo delete
  109.  
  110. Codice: Seleziona tutto
  111. void RBtree::del()
  112. {
  113.      if(root==NULL)
  114.      {
  115.            cout<<"\nEmpty Tree." ;
  116.            return ;
  117.      }
  118.      int x;
  119.      cout<<"\nEnter the key of the node to be deleted: "; cin>>x;
  120.      node *p;
  121.      p=root;
  122.      node *y=NULL;
  123.      node *q=NULL;
  124.      int found=0;
  125.      while(p!=NULL&&found==0)
  126.      {
  127.            if(p->key==x)
  128.                found=1;
  129.            if(found==0)
  130.            {
  131.                  if(p->key<x) p=p->right;
  132.                  else
  133.                     p=p->left;
  134.            }
  135.      }
  136.      if(found==0)
  137.      {
  138.             cout<<"\nElement Not Found.";
  139.             return ;
  140.      }
  141.      else
  142.      {
  143.          cout<<"\nDeleted Element: "<<p->key;
  144.          cout<<"\nColour: "; if(p->color=='b')
  145.      cout<<"Black\n";
  146.     else
  147.      cout<<"Red\n"; if(p->parent!=NULL)
  148.                cout<<"\nParent: "<<p->parent->key;
  149.          else
  150.                cout<<"\nThere is no parent of the node. "; if(p->right!=NULL)
  151.                cout<<"\nRight Child: "<<p->right->key;
  152.          else
  153.                cout<<"\nThere is no right child of the node. "; if(p->left!=NULL)
  154.                cout<<"\nLeft Child: "<<p->left->key;
  155.          else
  156.                cout<<"\nThere is no left child of the node.  ";
  157.          cout<<"\nNode Deleted."; if(p->left==NULL||p->right==NULL)
  158.               y=p;
  159.          else
  160.               y=successor(p);
  161.          if(y->left!=NULL)
  162.               q=y->left;
  163.          else
  164.          {
  165.               if(y->right!=NULL)
  166.                    q=y->right;
  167.               else
  168.                    q=NULL;
  169.          }
  170.          if(q!=NULL)
  171.               q->parent=y->parent;
  172.          if(y->parent==NULL)
  173.               root=q;
  174.          else
  175.          {
  176.              if(y==y->parent->left)
  177.                 y->parent->left=q;
  178.              else
  179.                 y->parent->right=q;
  180.          }
  181.          if(y!=p)
  182.          {
  183.              p->color=y->color;
  184.              p->key=y->key;
  185.          }
  186.          if(y->color=='b' && q != NULL )
  187.              delfix(q);
  188.      }
  189. }
  190.  
  191.  
  192. Metodo delete fix
  193.  
  194. Codice: Seleziona tutto
  195. void RBtree::delfix(node *p)
  196. {
  197.     node *s;
  198.     while(p!=root&&p->color=='b')
  199.     {
  200.           if(p->parent->left==p)
  201.           {
  202.                   s=p->parent->right;
  203.                   if(s->color=='r')
  204.                   {
  205.                          s->color='b';
  206.                          p->parent->color='r';
  207.                          leftrotate(p->parent);
  208.                          s=p->parent->right;
  209.                   }
  210.                   if(s->right->color=='b'&&s->left->color=='b')
  211.                   {
  212.                          s->color='r';
  213.                          p=p->parent;
  214.                   }
  215.                   else
  216.                   {
  217.                       if(s->right->color=='b')
  218.                       {
  219.                              s->left->color=='b';
  220.                              s->color='r';
  221.                              rightrotate(s);
  222.                              s=p->parent->right;
  223.                       }
  224.                       s->color=p->parent->color;
  225.                       p->parent->color='b';
  226.                       s->right->color='b';
  227.                       leftrotate(p->parent);
  228.                       p=root;
  229.                   }
  230.           }
  231.           else
  232.           {
  233.                   s=p->parent->left;
  234.                   if(s->color=='r')
  235.                   {
  236.                         s->color='b';
  237.                         p->parent->color='r';
  238.                         rightrotate(p->parent);
  239.                         s=p->parent->left;
  240.                   }
  241.                   if(s->left->color=='b'&&s->right->color=='b')
  242.                   {
  243.                         s->color='r';
  244.                         p=p->parent;
  245.                   }
  246.                   else
  247.                   {
  248.                         if(s->left->color=='b')
  249.                         {
  250.                               s->right->color='b';
  251.                               s->color='r';
  252.                               leftrotate(s);
  253.                               s=p->parent->left;
  254.                         }
  255.                         s->color=p->parent->color;
  256.                         p->parent->color='b';
  257.                         s->left->color='b';
  258.                         rightrotate(p->parent);
  259.                         p=root;
  260.                   }
  261.           }
  262.        p->color='b';
  263.        root->color='b';
  264.     }
  265. }
  266.  
  267.  
  268. Ringrazio in anticipo chi mi aiuterà  :D  :D
  269. Top


Ultima modifica effettuata da light00 il 04/02/2017 alle 19:31
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1452
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 12:58
Giovedì, 26/01/2017
Fai il debug di insertfix: http://www.pierotofy.it/pages/guide_tutorials/CPlusPlus/Co ...

E..... Se hai problemi chiedi a chi ha scritto il codice: http://www.coders-hub.com/2015/07/red-black-tree-rb-tree-u ...

PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 413
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 15:48
Sabato, 28/01/2017
Testo quotato

Postato originariamente da TheDarkJuster:

Fai il debug di insertfix: http://www.pierotofy.it/pages/guide_tutorials/CPlusPlus/Co ...

E..... Se hai problemi chiedi a chi ha scritto il codice: http://www.coders-hub.com/2015/07/red-black-tree-rb-tree-u ...



Non ci posso credere.

PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 413
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 16:29
Sabato, 28/01/2017
Con 10 minuti di ricerca su google a partire dal tuo nick si trova dove abiti, il tuo nome e cognome e quale università frequenti.
Ho le mail dei professori che tengono "Algoritmi e Strutture Dati e Laboratorio di Algoritmi e Strutture Dati" nel tuo corso, dammi un buon motivo per non fare niente dopo che ho perso tempo a cercare i bug in un codice che non era nemmeno scritto da te.

Ultima modifica effettuata da lumo il 28/01/2017 alle 16:35
PM Quote