插入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 

这不是整个代码，但它足以向您展示我正在尝试做什么。你已经在这段代码中看到，我正在设置插入期间节点的平衡因子（while while循环块）。好的，这很好。但是在插入之后，我需要进行旋转。我也有旋转代码，但主要问题是当节点旋转时，我需要重置旋转代码中节点的平衡因子。这是我的问题。我如何做到这一点？代码片段会是什么？

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. 我不知道你的堆栈执行是如何工作的，但我看到你推入堆栈指针，然后你弹出一个对象：

   秒。推（p）;

   treenode node = s.pop（）;

2. 你推节点入堆栈只有当你穿过你的AVL树的左子树，当你走不正确的。这是为什么？

3. 将newNode插入到树中时，请记得将newNode的左右子节点设置为NULL（也许您已经在构造函数中这样做了，但我不确定）。

4. 通常，在AVL树，当左子树比一个节点的右子树越高，则该节点的平衡因子为负。你可能想在你的代码中改变它。如果你想离开它，你必须改变我的递归函数。

5. 最后但并非最不重要的，你检查，看看是否平衡因子等于2（如果你的树需要旋转）。请记住，平衡因子也可以取负值（如果左子树高于右子树）。

新年快乐给大家:-)