Удаление дерева AVL c ++ - PullRequest
       22

Удаление дерева AVL c ++

0 голосов
/ 29 апреля 2020

У меня проблемы с удалением элемента в моем дереве AVL.

Вот моя функция удаления

template <class TYPE, class KTYPE>
bool  AvlTree <TYPE, KTYPE> :: AVL_Delete (KTYPE  dltKey)
{
//  Local Definitions 
    bool shorter;
    bool success;

    NODE<TYPE>  *newRoot;

//  Statements 
    newRoot = _delete (tree, dltKey, shorter, success);
    if (success)
       {
        tree = newRoot;
        count--;
       } // if 
    return success;
}   // AVL_Delete

template <class TYPE, class KTYPE>
NODE<TYPE>*  AvlTree<TYPE,  KTYPE> 
          :: _delete (NODE<TYPE> *root, 
                      KTYPE       dltKey,
                      bool&       shorter,
                      bool&       success) 
{
//  Local Definitions 
    NODE<TYPE> *dltPtr;
    NODE<TYPE> *exchPtr;
    NODE<TYPE> *newRoot;

//  Statements 
    if (!root)
       {
        shorter = false;
        success = false;
        return NULL;
       } //  if -- base case 

    if (dltKey < root->data.key)
        {
         root->left = _delete (root->left, dltKey, 
                               shorter,    success);
         if (shorter)
             root   = dltRightBalance (root, shorter);
        } // if less 
    else if (dltKey > root->data.key)
        {
         root->right = _delete (root->right, dltKey,
                                shorter,     success);
         if (shorter)
             root = dltLeftBalance (root, shorter);
        } //  if greater 
    else
        //  Found equal node 
        {
         dltPtr  = root;
         if (!root->right)
             // Only left subtree 
             {
              newRoot  = root->left;
              success  = true;
              shorter  = true;
              delete (dltPtr);
              return newRoot;            //  base case 
             } //  if true 
         else
             if (!root->left)
                 //  Only right subtree 
                 {
                  newRoot  = root->right;
                  success  = true;
                  shorter  = true;
                  delete (dltPtr);
                  return newRoot;        // base case 
                } //  if 
             else
                 //  Delete NODE has two subtrees 
                 {
                  exchPtr = root->left;
                  while (exchPtr->right)
                      exchPtr = exchPtr->right;

                  root->data = exchPtr->data;
                  root->left = _delete (root->left, 
                                        exchPtr->data.key,
                                        shorter, 
                                        success); 
                  if (shorter)
                      root = dltRightBalance (root, shorter); 
                 } //  else 

        } // equal node 
    return root; 
}   // _delete 

И это то, чего я пытаюсь достичь

for (int loop=0;loop<newIdea.size();loop++)
    {
     for (int j = 0; j < newIdea[loop].getKeyword().size(); j++) {
                key = newIdea[loop].getKeyword()[j];

                Index modIndex;
                if (tree.AVL_Retrieve(key, modIndex)){
                    for (int i = 0; i < modIndex.idList.size(); i++) {
                        if (ID == modIndex.idList[i]){
                            modIndex.idList.erase(modIndex.idList.begin()+i);
                            tree.AVL_Delete(modIndex);
                        }
                    }
                }
            }
    }

это ошибка, которую я получаю

[Ошибка] нет соответствующей функции для вызова 'AvlTree> :: AVL_Delete (Index &)'

это моя структура для вставки в мое дерево, которое работает

struct Index {
string key;
vector<int> idList;
};

, где ключ представляет слово, а idList представляет целочисленный идентификатор, где слово было найдено. Мой код выше предназначен для поиска слова в дереве, удаления его из списка Id в моей структуре, а затем удаления этого слова и идентификатора из моего дерева AVL.

...