Вставить метод дерева AVL?

Question

Я выставляю вам код для использования AVL tree, который я разработал. Метод для вставки, метод avlinsert приведен ниже. Я разработал этот код на бумаге, и он не протестирован, но я надеюсь, что это сработает. Основная проблема, которую я хочу обсудить, заключается в том, что фактор баланса узлов сначала просматривает код. Таким образом, станет ясно, что я пытаюсь спросить. Так вот код:

treeNode* avlinsert(treeNode* tree, int info) 
    { 
     treeNode* newNode=new treeNode; 
     newNode->setinfo(info); 
     newNode->setbalance(0); 
     treeNode* p,*q; 
     bool duplicate=false; 
     p=q=tree; 
     stack s; //I have made this stack already and now I am using it here. 
     //Now the the while loop block will check for duplicate nodes, this block prevents the duplicate insertion. 
     while (q!=NULL) 
     { 
      p=q; 
      if (info < p -> getinfo()) 
       q=p->getleft(); 
      else if (info>p->getinfo()) 
       q=p->getright(); 
      else 
      { 
       duplicate=true; 
       cout<<"Trying to insert duplicate"; 
       break; 
      } 
     }//while loop ended. 
     //Now checking for duplicates. 
     if (duplicate) 
      return tree; 
     p=q=tree; 
     //Now below is the main block of while loop which calculates the balance factors of nodes and helps in inserting nodes at proper positions. 
     while (q!=NULL) 
     { 
      p=q; 
      if (info < p -> getinfo()) 
      { 
       p->setbalance(p -> getbalance()+1); 
       s.push(p);//pushing into stack 
       q=p->getleft(); 
      } 

      else if (info > p -> getinfo()) 
      { 

       p->setbalance(p->getbalance()-1); 
       q=p->getright(); 
      } 

     }//while loop ended 
     //Now the below code block will actually inserts nodes. 
     if (info < p -> getinfo()) 
      p->setleft(newNode); 
     else if (info > p -> getinfo()) 
      p->setright(newNode); 
     //After this insertion we need to check the balance factor of the nodesand perform the approprite rotations. 

     while (!s.isempty()) 
     { 
      treeNode node; 
      node=s.pop(); 
      int balance; 
      balance=node.getbalance(); 
      if (balance==2) 
      { 
       s.Makeempty(); // We have found the node whoes balance factor is violating avl condition so we don't need other nodes in the stack, therefor we are making stack empty. 
       treeNode* k1,*k3; 
       k1=&node; //This is the node whoes balance factor is violating AVL condition. 
       k3=&(k1 -> getleft()); //Root of the left subtree of k1. 
       //Identifying the cases of insertion 
       if (info < k3 -> getinfo()) //This is the case of insertion in left subtree of left child of k1 here we need single right rotation. 
        root=Rightrotation(k1); //Here root is the private data member. 

       //Next case is the insertion in right subtree of left child of k1. 
       if (info > k3 ->getinfo()) 
        root=LeftRightrotation(k1); 
      }//end of if statement. 
     }//while loop ended 

Это не весь код, но этого достаточно, чтобы показать, что я пытаюсь сделать. Вы видели в этом коде, что я устанавливаю коэффициент баланса узлов во время вставки (второй в блоке цикла). Хорошо, это нормально. Но после этой вставки мне нужно выполнить повороты. У меня также есть код поворота, но главная проблема заключается в том, когда узлы повернуты, тогда мне нужно сбросить коэффициенты баланса узлов в коде вращения. Это проблема со мной. Как я могу это сделать? И какой будет фрагмент кода?

Answer 1

"... Мне нужно сбросить весовые коэффициенты узлов в код поворота."

Если вы хотите добавить что-то внутри кода вращения, то, возможно, вам также следует отправить код функций вращения, чтобы получить справку.

В противном случае, если вы просто хотите обновить факторы баланса каждого узла после поворота, то это рекурсивная функция может помочь (просто назвать его и передать корневой узел дерева):

int updateBalanceFactors(treeNode *node) 
{ 
    if(node == NULL) 
     return 0; 
    node->setbalance(updateBalanceFactors(node->getright()) - updateBalanceFactors(node->getleft())); 
    return ((node->getbalance() < 0 ? -node->getbalance() : node->getbalance()) + 1); 
} 

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

1. Я не уверен, как ваша реализация стека работает, но я вижу, что вы толкаете в стек указатель, а затем вы поп объект:

   сек. толкать (р);

   treenode node = s.pop();

2. Вы вставляете узлы в стек, только когда вы пересекаете левое поддерево вашего дерева AVL, а не когда вы идете вправо. Почему это?

3. Когда вы вставляете newNode в дерево, не забудьте установить слева и справа детей newNode в NULL (возможно, вы уже делаете это в своем конструкторе, но я не уверен).

4. Как правило, в деревьях AVL, когда левое поддерево выше правого поддерева узла, коэффициент баланса этого узла отрицательный. Возможно, вы захотите изменить это в своем коде. Если вы хотите оставить это так, вам придется изменить рекурсивную функцию.

5. Последнее, но не менее важное: вы проверяете, равен ли коэффициент баланса 2 (если ваше дерево нуждается в ротации). Помните, что коэффициент баланса может принимать и отрицательные значения (если левое поддерево выше правого поддерева).

С Новым годом для всех :-)