1

我正在研究 AVL 树。我想我已经让所有的旋转功能都正常工作了。我有一个 rotateleft、rotateright、rotateleftright 和 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 我将传递给这些函数中的每一个以重新平衡树吗？

4

1 回答 1

1

您的代码中有一些错误是您在另一个问题中提交的错误，即您没有检查代码中的空指针：

  • 你不检查是否N在NULL方法的开头

  • 如果左右节点是NULL

    if((N->getLeft()->getHeight()) > (N->getRight()->getHeight() + 1))

关于算法本身，它取决于旋转函数的行为。维基百科条目中描述的算法解释了嵌套 if （rotateLeftRight和方法）中的第二种情况rotateRightLeft应该执行 2 次旋转。如果您的旋转功能符合该描述，那么您应该没问题。

的情况recalculate已在另一个问题中得到解决，但在这种情况下，您实际上不需要重新计算整个子树的高度，正如您在该问题的评论中正确告诉我的那样。唯一更改的节点是其子节点已更改的节点。您应该在每种特定的旋转方法中执行该计算，因为每种情况都准确地描述了哪些节点得到更新。

于 2013-04-10T07:41:13.963 回答