c++ - AVL binary search tree rotation c++

Question

i am working on an avl tree and i think ive got the everything right, but im not sure here is my rotate right function am i doing it correcty?

Node* BinaryTree::rotateRight(Node *N)
{
    Node *newNode = new Node();
    newNode = N->getLeft();
    N->setLeft(newNode->getRight());
    newNode->setRight(N);
    root = newNode;
    return newNode;
}

Answer 1

rotateRight 不需要分配新节点。它仅通过操作指向现有节点的指针来工作。像这样

Node* BinaryTree::rotateRight(Node *N)
{
    Node *pivot = N->getLeft();
    N->setLeft(pivot->getRight());
    pivot->setRight(N);
    return pivot;
}

因此，除了不必要地分配一个新节点并出于某种原因分配给 root 之外，您几乎是正确的。

BTW rotateRight 通常可以做成静态方法。

Answer 2

我认为您的代码可能会在之后造成内存泄漏newNode = N->getLeft();

这是我直接在此处编写的实现。你可以检查它是否正确。我没有测试过。

Node* BinaryTree::rotateRight(Node *N)
{
    Node *newNode = new Node();
    Node *prevLeft = N->getLeft();

    prevLeft->setRight(newNode);
    newNode->setLeft(prevLeft);
    newNode->setRight(N);
    N->setLeft(newNode);

    root = newNode;
    return newNode;
}