Полное двоичное дерево, заменяющее дочернюю и родительскую ошибку - PullRequest
Новая
       29

Полное двоичное дерево, заменяющее дочернюю и родительскую ошибку

0 голосов
/ 09 апреля 2020

Я делаю проект для школы, и у меня странная ошибка. Я использую Complete Binary Tree, и у меня возникают проблемы с заменой узла на его родителя.

Во время тестирования я обнаружил, что 1 случай не работает должным образом.

Это: Broken case

Все остальные операции подкачки работают нормально, кроме этого случая

Структура моего дерева такова 

typedef struct TreeNode {
    void * data;
    struct TreeNode * left;
    struct TreeNode * right;
    struct TreeNode * parent;
} TNode;

typedef struct CompleteBinaryTree {
    TNode * root;
    TNode * last;
    int numelm;
} CBTree;

CBTree * newCBTree(void)
{
    CBTree * ret = malloc(sizeof(CBTree));

    if( ret )
    {
        ret->root = NULL;
        ret->last = NULL;

        ret->numelm = 0;
    }
}

TNode * newTNode( void * data )
{
    TNode *ret = malloc(sizeof(TNode));
    if( ret )
    {
        ret->data = data;
        ret->parent = ret->left = ret->right = NULL;
    }

    return ret;
}

Это мой функция обмена: 

void CBTreeSwap(CBTree* tree, TNode* parent, TNode* child)
{
  assert(parent != NULL && child != NULL && (child == parent->left || child == parent->right));

  if (child == tree->last)
    tree->last = parent;

  if(child == parent->left)
  {        
    if(child->left != NULL)
      child->left->parent = parent;

    parent->left = child->left;
    child->left = parent;

    if (child->right != NULL)
      child->right->parent = parent;

    if (parent->right != NULL)
      parent->right->parent = child;

    TNode * tmp = child->right;
    child->right = parent->right;
    parent->right = tmp;

    if (parent != tree->root)
    {
      parent->parent->left = child;
      child->parent = parent->parent;
      parent->parent = child;
    }
    else
    {
      child->parent = NULL;
      tree->root = child;
      parent->parent = child;
    }
  }
  else
  {
    if(child->right != NULL)
      child->right->parent = parent;

    parent->right = child->right;
    child->right = parent;

    if(child->left != NULL)
      child->left->parent = parent;

    if(parent->left != NULL)
      parent->left->parent = child;

    TNode * tmp = child->left;
    child->left = parent->left;
    parent->left = tmp;

    if(parent != tree->root)
    {
      parent->parent->right = child;
      child->parent = parent->parent;
      parent->parent = child;
    }
    else
    {
      child->parent = NULL;
      tree->root = child;
      parent->parent = child;
    }
  }
}

Для вставки в используемое дерево используется следующее: 

void CBTreeInsert(CBTree* tree, void* data)
{
  TNode * tmp = newTNode(data);
  TNode * curr = tree->last;

  if(tree->root == NULL)
  { //empty
    tree->root = tmp;
  }
  else if(tree->last == tree->root)
  { //one node
    tree->last->left = tmp;
    tmp->parent = tree->root;
  }
  else if(tree->last->parent->right == NULL)
  { //general
    tree->last->parent->right = tmp;
    tmp->parent = tree->last->parent;
  }
  else if (tree->last == tree->last->parent->right)
  { //degenarated
    curr = tree->last->parent ;

    while (1)
    {
      if (curr == tree->root)
        break ;

      if (curr == curr->parent->left)
      {
        curr = curr->parent->right ;
        assert(curr != NULL) ;
        break ;
      }
      curr = curr->parent ;
   }

   while (curr->left != NULL) 
   {
      assert(curr->right != NULL) ;
      curr = curr->left ;
   }
    assert(curr->right == NULL) ;
    tmp->parent = curr ;
    curr->left  = tree->last = tmp;
  }
  else 
  {
    fprintf(stderr,"Error\n");
  }
  tree->last = tmp;
  tree->numelm++;
}

Поэтому я строю свой тест следующим образом: 

void main(){
  int * i[15], j;

  CBTree * tree  = newCBTree(); //create tree

  for(j=0; j<15; j++)
  {
    i[j] = malloc(sizeof(int));
    *(i[j]) = j+1;

    CBTreeInsert(tree, (int*) i[j]);
  }

    //All these work
    CBTreeSwap(T, T->root->left, T->root->left->left);
    CBTreeSwap(T, T->root, T->root->left);
    CBTreeSwap(T, T->root->right, T->root->right->right);
    CBTreeSwap(T, T->root, T->root->right);
    CBTreeSwap(T, T->last->parent, T->last);

    //This one is broken
    CBTreeSwap(T, T->root->left, T->root->left->right);
}

Когда я запускаю этот тест и попытка просмотреть мое дерево. Я получаю все ветви моего дерева, за которыми следует ошибка сегмента.

Это всего лишь часть большого проекта, если вам нужно больше моего кода, не стесняйтесь спроси

Спасибо!

1 Ответ

1 голос
/ 11 апреля 2020

Ваша проблема приводит к повреждению дерева не только тогда, когда T->left и T->left->right поменялись местами (повреждает все T->left оставленное поддерево), но также и когда T->right и T->right->left поменялись местами.

Проблема находится где-то в CBTreeSwap() функции.

Ее реализация на самом деле хитрая. Это нелегко понять, поэтому я предложу свою реализацию. Я могу просто сказать, что проблема root заключается, вероятно, в том, что где-то в процессе замены вы присваиваете некоторые поля parent / child, не обращая внимания на тот факт, что они уже изменены!

Исправление

Ниже приведена исправленная версия CBTreeSwap(). Это правильное различие между случаем, в котором ребенок является либо parent->left, либо parent->right, но многие другие действия являются общими в этих двух случаях. Код прокомментирован. 

void CBTreeSwap(CBTree* tree, TNode* parent, TNode* child)
{
    assert(parent != NULL && child != NULL && (child == parent->left || child == parent->right));

    if (child == tree->last)
        tree->last = parent;

    /* Save child's childs */
    TNode *tmpL = child->left, *tmpR = child->right;

    /* Link child (new parent!) to parent's parent */
    if(parent != tree->root)
    {
        TNode *parpar = parent->parent;
        child->parent = parpar;

        /* Is parent left or right child of his parent? */
        if( parent->parent->left == parent)
          parpar->left = child;
        else
          parpar->right = child;
    }
    else
    {
        child->parent = NULL;
        tree->root = child;
    }

    /* In order to actually swap nodes we need to know if child is at parent's left or right*/       
    if(child == parent->left)
    {        
        /* Link parent's other child to child */
        parent->right->parent  = child;
        child->right  = parent->right;

        /* Link former parent to child's right (making it its new right child) */
        child->left = parent;
        parent->parent = child;
    }
    else /* child == parent->right */
    {
        /* Link parent's other child to child */
        parent->left->parent  = child;
        child->left  = parent->left;

        /* Link former parent to child's right (making it its new right child) */
        child->right = parent;
        parent->parent = child;
    }

    /* Link child's childs to former parent */
    parent->left  = tmpL;
    parent->right = tmpR;
    if(tmpL != NULL)
        tmpL->parent = parent;
    if(tmpR != NULL)
        tmpR->parent = parent;
}

Итак:

  1. Сохранить дочерние элементы child.
  2. Свяжите дочерний (новый родительский) с родительским родительским элементом управление делом, в котором parent является узлом root. Нам нужно понять, находится ли parent слева или справа от его родителя.
  3. Поменяйте местами parent и child в соответствии с их первоначальной взаимной позицией. Если мы ошибемся, мы можем испортить целое поддерево.
  4. Восстановить дочерние элементы child

Я проверил приведенный выше код, и он заработал, как и ожидалось.

PS : хотя это не связано с этим вопросом, рассмотрите возможность использования массива и al oop для инициализации. Код ниже ведет себя как ваша инициализация. Разве это не более элегантно? 

  int * i[15], j;

  CBTree * tree  = newCBTree(); //create tree

  for(j=0; j<15; j++)
  {
    i[j] = malloc(sizeof(int));
    *(i[j]) = j+1;

    CBTreeInsert(tree, (int*) i[j]);
  }

Альтернативное решение

Но есть более простое решение для достижения вашей конкретной c цели: зачем менять целые поддеревья, когда в конце программы нужно поменять местами только узлы содержимое ?

Таким образом, ваша функция обмена становится: 

void CBTreeSwap(CBTree* tree, TNode* parent, TNode* child)
{
    assert(parent != NULL && child != NULL && (child == parent->left || child == parent->right));

    void *tmpData = parent->data;
    parent->data = child->data;
    child->data = tmpData;
}
...