CODEWITHSUNDEEP
c++nodes
user1926913
user1926913

Reputation:

AVL binary search tree rotation c++

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

Upvotes: 0

Views: 4825

Answers (2)

john
john

Reputation: 87959

rotateRight does not need to allocate a new node. It works by manipulating the pointers to existing nodes only. Like this

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

So you were almost right apart from needlessly allocating a new node, and assigning to root for some reason.

BTW rotateRight can normally be made a static method.

Upvotes: 2

Vishwanath Kamath
Vishwanath Kamath

Reputation: 360

I think your code might create memory leak after newNode = N->getLeft();

Here's my implementation which I wrote directly over here. You can check it if its correct. I have not tested.

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

Upvotes: 0

Related Questions