C++ AVLtree插入方法

Question

所以我遇到的問題是AVLtree的插入方法。我的鳥類存儲着城市物體，我用城市的名字來決定它們應該去的地方。

我的城市的.cpp類：

#include "City.h" 
#include <iostream> 

    using namespace std;    


    City::City(string name, string country, double lat, double lon){ 
     this->name = name; 
     this->country = country; 
     this->latitude = lat; 
     this->longtitude = lon; 
      } 

    double City::getLatOfCity(void){ 
     return this->latitude; 
     } 

    double City::getLonOfCity(void){ 
     return this->longtitude; 
     } 

    string City::getName(void){ 
     return this->name; 
     } 

    string City::getCountry(void){ 
     return this->country; 
     } 

在我avltree .cpp文件的方法。

我向左旋轉法：

Node* AVLtree::rotateLeft(Node* node){ 
     Node* tempParent= node->getParent(); 
     Node* tempNode = node->getChildL(); 
     node->setChildL(tempNode->getChildR()); 
     tempNode->setChildR(node); 

     if(tempParent==0){tempNode->removeParent();this->rootNode=tempNode;} 
     else{tempParent->setChildL(tempNode); 
      //tempNode->updateParent(tempParent); 
      } 

     return tempNode; 
     } 

向右旋轉法：

Node* AVLtree::rotateRight(Node* node){ 
     Node* tempParent = node->getParent(); 
     if(tempParent!=0){cout<<"IHN";cout<<"temp parent: " << tempParent->getCity()->getName();} 
     Node* tempNode = node->getChildR(); 
     node->setChildR(tempNode->getChildL()); 
     tempNode->setChildL(node); 

     if(tempParent==0){tempNode->removeParent();this->rootNode=tempNode;} 
     else{tempParent->setChildR(tempNode);} 

     return tempNode; 
     } 

我的第一雙右旋轉的方法。這個不能正常工作，因爲當我傳遞給rotate方法的指針在方法內部時是不同的。

/* 
    Node* AVLtree::rotateTwoRights(Node* node){ 
     node = rotateRight(node->getChildR()); 
     node = rotateRight(node->getParent()); 
     return node; 
     } */ 

我知道這是非常混亂，但它似乎正確地旋轉節點周圍。

Node* AVLtree::rotateTwoRights(Node* node){ 
     Node* tempParent = node; 
     Node* tempNode = node->getChildR(); 
     Node* tempTempNode = tempNode->getChildL(); 
     tempNode->setChildL(tempTempNode->getChildL()); 
     tempTempNode->setChildR(tempNode); 
     tempParent->setChildR(tempTempNode); 
     Node* tempTempParent = tempParent->getParent(); 
     tempTempParent->setChildR(tempParent->getChildL()); 
     tempParent->setChildL(tempTempParent); 
     Node* newTempParent = tempParent->getParent(); 

     if(newTempParent==0){tempParent->removeParent();this->rootNode=tempParent;} 
     else{newTempParent->setChildR(tempParent);} 

     return tempParent; 
     }  

與我第一次旋轉雙右方法相同，但左側。同樣的問題：

Node* AVLtree::rotateTwoLefts(Node* node){ 
     node = rotateRight(node->getChildL()); 
     node = rotateLeft(node); 
     return node; 
     } 

我的插入方法：

Node* AVLtree::insertNode(Node* parent, Node* node, City *city, int side){ 
     if(node == 0){ 
       if(side==0){ 
        node = parent->setChildL(new Node(city)); 
       }else if(side==1){ 
        node = parent->setChildR(new Node(city)); 
       } 
     }else if(node->getCity()->getName().compare(city->getName())<0){ //Right case 
      parent = node; 
      node = insertNode(parent, node->getChildR(), city, 1); 
      if(parent->getBalance()==2){ 
        if(parent->getChildR()->getCity()->getName().compare(city->getName())<0){ 
         node = rotateRight(parent); 
        }else{ 
         node = rotateTwoRights(parent); 
        }         
      } 
     }else if(node->getCity()->getName().compare(city->getName())>0){ //Left case 
      parent = node; 
      node = insertNode(parent, node->getChildL(), city, 0); 
      if(parent->getBalance()==-2){ 
        if(parent->getChildL()->getCity()->getName().compare(city->getName())>0){ 
         node = rotateLeft(parent); 
        }else{ 
         node = rotateTwoLefts(parent); 
        } 
      }  
     }else{ 
      node=0; 
     } 
     return node; 
     } 

所以，問題是我想嘗試插入 'CA' 時。

所以樹是這樣的：

B 
/\ 
A C 
     \ 
     D 

和插入 'CA' 之後，應該遵循以下步驟：

1）

B 
/\ 
A C 
     \ 
     D 
    /
    CA 

2）

B 
/\ 
A C 
     \ 
     CA 
     \ 
     D 

3）

C 
/\ 
    B CA 
/ \ 
A  D 

什麼錯誤是，當我在其上運行的測試，該樹的根還是B. 我相信這是由於parent，因爲當我以後再平衡的樹就沒有更新遞歸調用。但是，當我將parent分配給方法的返回值時，我甚至無法將「C」添加到樹中。

我會很感激任何幫助。我在這上面花了很多時間，並且真的想完成這件事。

我很抱歉這個帖子太亂，代碼亂，請提前致謝！

Answer 1

鑑於節點C是其中左子樹（0）和右子樹（2）相差2的深度的深度，我認爲有應該只是一個簡單的左旋轉的第一個節點，得到

B 
/\ 
A CA 
/\ 
    C D 

當不平衡的修補達到B時，樹足夠平衡。我沒有仔細查看你的代碼，但你的假設結果似乎並不正確，即代碼實際上有可能是。