c++ - AVL 二叉搜索树旋转 C++

Question

我正在研究一棵 avl 树，我认为我做对了一切，但我不确定这是我的右旋转函数，我做的是否正确？

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;
}

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

顺便说一句，rotateRight 通常可以成为静态方法。