C++中的AVL树重新平衡

Question

我正在研究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我通过什么传递给这些函数来重新平衡树？

Answer 1

有在你的代码的一些错误，你没有在你的另一个问题提交一个做的，那是你不检查你的代码无参指针：

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

• 你不低于（并在其对称的兄弟姐妹），如果左边和右边节点是线检查NULL

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

关于算法本身，它取决于旋转函数的行为。在wikipedia entry中描述的算法解释说，嵌套if（rotateLeftRight和rotateRightLeft方法）中的第二种情况应执行2次旋转。如果你的旋转函数符合那个描述，你应该没问题。

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