Красно-Черное дерево вставки бесконечной петли - PullRequest
Новая
       57

Красно-Черное дерево вставки бесконечной петли

1 голос
/ 31 марта 2020

Для класса, в котором я учусь, я реализую некоторые методы дерева RB. Когда я запускаю свое дерево на этом наборе данных: 372 245 491 474 440 122 418 125 934 752 в этом порядке, я попадаю в бесконечное число l oop, когда вставляется 474. Я с нетерпением жду второго взгляда на это, потому что по какой-то причине я не могу найти ошибку. После нескольких отладок я обнаружил, что бесконечный l oop находится в моем методе insertFixup. Вот код, который я написал: 

void RBTree ::RBinsert(NodePtr z)
{
   NodePtr y = nil;
   NodePtr x = root;

   // You supply the rest of the code

   while(x != nil) {
      y = x;
      if(z->key < x->key) {
         x = x->left;
      }
      else {
         x = x->right;
      }
   }

   z->p = y;

   if(y == nil) {
      root = z;
   }
   else if(z->key < y->key) {
      y->left = z;
   }
   else {
      y->right = z;
   }

   z->left = nil;
   z->right = nil;

   z->color = 'R';

   insertFixup(z);
}

void RBTree ::insertFixup(NodePtr z)
{
   //this method may not be right yet
   NodePtr y;

   //this is an infinite loop, need to fix
   while (z->p->color == 'R')
   {
      if (z->p == z->p->p->left)
      {
         // You fill this in
         y = z->p->p->right;
         if(y->color == 'R') {
            z->p->color = 'B';
            y->color = 'B';
            z->p->p->color = 'R';
            z = z->p->p;
         }
         else if(z == z->p->right) {
            z = z->p;
            leftRotate(z);
         }
         z->p->color = 'B';
         z->p->p->color = 'R';
         rightRotate(z->p->p);
      }
      else
      {  
         y = z->p->p->left; //uncle
         if(y->color == 'R') {
            z->p->color = 'B';
            y->color = 'B';
            z->p->p->color = 'R';
            z = z->p->p;
         }
         else if(z == z->p->left) {
            z = z->p;
            rightRotate(z); //may need to be left rotate
         }
         z->p->color = 'B';
         z->p->p->color = 'R';
         leftRotate(z->p->p); //may need to be right rotate
      }
   }
   root->color = 'B';
}

void RBTree ::rightRotate(NodePtr x)
{
   NodePtr y = x->left;
   // You write the rest of this
   x->left = y->right;

   if(x->left != nil) {
      x->left->p = x;
   }

   y->p = x->p;

   if(x->p == nil) {
      root = y;
   }
   else if(x == x->p->left) {
      x->p->left = y;
   }
   else {
      x->p->right = y;
   }

   y->right = x;
   x->p = y;
}

void RBTree ::leftRotate(NodePtr x)
{
   //this may not be right yet
   NodePtr y = x->right;
   // You write the rest of this
   x->right = y->left;      
   if(y->left != nil) {     
      y->left->p = x;       
   }
   y->p = x->p;             
   if(x->p == nil) {        
      root = y;             
   }
   else if(x == x->p->left) { 
      x->p->left = y;         
   }
   else {
      x->p->right = y;
   }
   x->left = x;
   x->p = y;
}
...