AVL二进制搜索树的旋转C++

我正在一个AVL树上，我认为我得到了一切正确的，但我不知道这里是我的旋转权函数，我正在纠正？AVL二进制搜索树的旋转C++

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

来源

2013-04-03 compprog254

那么这将泄漏内存... – user1520427

我觉得你的代码可能会造成内存泄漏后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; 
}

来源

2013-04-03 06:52:35

我的作品，并没有给我任何内存泄漏。按照你的建议。你将指针分配给N的左节点。同时给出了我的指示，这就是我应该这样做的。 – compprog254

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

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

因此，除了不必要的分配新节点和分配给root用户之外，你几乎是正确的。

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

来源

2013-04-03 07:15:21 john

随着你有它的方式，我得到一个内存泄漏，如果我只有一个树的一面与一些信息。 – compprog254

我的代码没有分配任何内存（与你的不同）。如果你的代码存在内存泄漏，那是因为你的代码中有其他地方存在bug。 – john

ive追踪它的方法之前，我改变它像你的它很好，但现在它不does – compprog254

AVL二进制搜索树的旋转C++

回答

相关问题