C++ метод удаления AVLtree

Question

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

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

Любые и все советы будут оценены. Большое спасибо заранее!

----- EDIT -----

Найти метод узла:

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; 
     } 

Answer 1

Интернет имеет many примеры таких алгоритмов объяснил абстрактно.

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