我正在研究 AVL 树。我想我已经让所有的旋转功能正常工作了。我有一个 rotatleft、rotateright、rotatleftright 和 rotaterightleft 函数。它们都以一个节点作为参数。我不知道传递给那些参数的是什么节点。你能看看我的 AVL 树重新平衡函数并告诉我它是否正确,以及我需要传递给每个函数的内容。到目前为止,我有根节点或顶级节点,但我认为我错了。我如何告诉我需要传递给这些函数的内容?
函数如下:
void BinaryTree::rebalance(Node *N)
{
int count = 1;
if((N->getLeft()->getHeight()) > (N->getRight()->getHeight() + 1))
{
if(N->getLeft()->getLeft()->getHeight() > N->getLeft()->getRight()->getHeight())
{
rotateRight(root);
recalculate(root, count);
}
else
{
rotateLeftRight(root);
recalculate(root, count);
}
}
else if(N->getRight()->getHeight()> N->getLeft()->getHeight() + 1)
{
if(N->getRight()->getRight()->getHeight() > N->getRight()->getLeft()->getHeight())
{
rotateLeft(root);
recalculate(root, count);
}
else
{
rotateRightLeft(root);
recalculate(root, count);
}
}
}
这是我的左右旋转
Node* BinaryTree::rotateLeftRight(Node *N)
{
Node *newNode = new Node();//declares a new Node
newNode = N->getLeft();//sets the node
N->setLeft(rotateLeft(newNode->getLeft());//sets the left subtree
recalculate(root);//recalculates the height
root->setHeight(NULL);//sets the height of the root node
return rotateRight(N);//retuns the tree rotated right
}
这是我的向左旋转功能。:
Node* BinaryTree::rotateLeft(Node *N)
{
Node *newNode = new Node();//declares a new node
newNode = N->getRight();//sets the new node to the right child of N
N->setRight(newNode->getLeft());//sets the right of N equal to new nodes left child
newNode->setLeft(N);//sets the left child of the new node to N
return newNode;//retuns the newNode
}
如果我有树 50 20 10 和 15 我应该将什么传递给这些函数中的每一个来重新平衡树?
最佳答案
您的代码中有一些您在另一个问题中提交的代码中没有做的错误,即您没有检查代码中的空指针:
- 在方法的开头不检查
N
是否为NULL
如果左右节点为
,则不检查下面的行(及其对称的兄弟行)NULL
if((N->getLeft()->getHeight()) > (N->getRight()->getHeight() + 1))
关于算法本身,它取决于旋转函数的行为。 wikipedia entry中描述的算法说明嵌套 if 中的第二种情况(rotateLeftRight
和 rotateRightLeft
方法)应该执行 2 次旋转。如果您的旋转功能符合该描述,那么您应该没问题。
recalculate
的情况已在另一个问题中得到处理,但在这种情况下,您实际上不需要重新计算整个子树的高度,正如您在对该问题的评论。唯一发生变化的节点是其子节点已更改的节点。您应该在每种特定的旋转方法中执行该计算,因为每种情况都准确描述了哪些节点得到更新。
关于c++ - C++ 中的 AVL 树再平衡,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15885896/