дерево avl — метод удаления дерева C ++ AVL

Я действительно застрял в том, как реализовать метод удаления для avltree в C ++.
Я не совсем уверен, с чего начать. У меня есть методы, чтобы найти узел, и методы вращения, и вставка, работающая, но я просто не знаю, как запустить этот метод удаления. Я знаю, что это расплывчато, и есть ресурсы онлайн, но я не нахожу их очень ясными. Может кто-нибудь объяснить, пожалуйста, процесс, пожалуйста?

Если есть какой-либо код, который вы хотели бы увидеть, пожалуйста, спросите 🙂

Любой совет будет принята с благодарностью.
Спасибо заранее!

—— РЕДАКТИРОВАТЬ ——

Метод поиска узла:

Node* AVLtree::findNode(string cityID){
Node *thisNode = this->rootNode;
while(thisNode!=0){
int location = thisNode->getCity()->getName().compare(cityID);
if(location==0){return thisNode;
}else if(location<0){//cout<<"NODE: " << thisNode->getCity()->getName()<<endl;
thisNode = thisNode->getChildR();
}else{thisNode = thisNode->getChildL();}
}
return thisNode;
}

Поверните влево:

  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;tempNode->getNewHeight();}
else{tempParent->setChildR(tempNode);
}
return tempNode;
}

Поворот вправо:

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

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

return tempNode;
}

Двойное вращение, для вставки в левое поддерево правого потомка узла дисбаланса:

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

Двойное вращение вправо, влево:

  Node* AVLtree::rotateTwoLefts(Node* node){
node = rotateRight(node->getChildL());
node = rotateLeft(node->getParent());
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);
parent->getNewHeight();
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);
parent->getNewHeight();
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;
}