我正在向您发布使用 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 循环 block )。好的,这很好。但是在插入之后我需要执行旋转。我也有旋转代码,但主要问题是当节点旋转时,我需要在旋转代码中重置节点的平衡因子。这是我的问题。我该怎么做?代码片段是什么?
最佳答案
“...我需要在旋转代码中重置节点的平衡因子。”
如果您想在旋转代码中添加一些东西,那么也许您还应该发布旋转函数的代码以获得帮助。
否则,如果您只想在旋转后更新每个节点的平衡因子,那么这个递归函数可能会对您有所帮助(只需调用它并传递树的根节点):
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);
}
另外,我在您的代码中发现了一些错误,但我很确定您在尝试运行程序时会发现它们。一些需要记住的事情:
我不确定你的堆栈实现是如何工作的,但我看到你将一个指针压入堆栈,然后弹出一个对象:
s.push(p);
树节点节点 = s.pop();
只有在遍历 AVL 树的左子树时才将节点压入堆栈,而在向右遍历时则不会。这是为什么?
当您将 newNode 插入树中时,请记住将 newNode 的左右子节点设置为 NULL(也许您已经在构造函数中这样做了,但我不确定)。
通常,在AVL树中,当一个节点的左子树高于右子树时,则该节点的平衡因子为负。您可能想在代码中更改它。如果你想保留它,你将不得不更改我的递归函数。
最后但同样重要的是,您检查平衡因子是否等于 2(如果您的树需要轮换)。请记住,平衡因子也可以取负值(如果左子树高于右子树)。
祝大家新年快乐:-)
关于c++ - AVL树的插入方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1985172/