указатели — метод вставки C ++ AVLtree

Так что проблема у меня заключается в методе вставки для дерева AVL. Мое 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’ к дереву.

Я был бы очень благодарен за любую помощь. Я потратил много времени на это и очень хочу это сделать.

Я прошу прощения за длинный пост и грязный код, и заранее благодарю!

  B
/ \
A   CA
/ \
C   D