AVL树的倒置索引算法，每次都重复键 c++

Question

我创建了一个倒置索引算法来存储AVL树中的索引，但每次我调用该函数时，它都会用新的键和已经在树中的键重新填充树。

下面是函数

void IdeaBank::AVLTreeIndexing(){
    for (int loop = 0; loop < newIdea.size(); loop++) {
        vector<string> keywords = newIdea[loop].getKeyword();
        for (int i = 0; i < keywords.size(); i++) {
            Index input;
            input.key = keywords[i]; 
            for (int j = 0; j < newIdea.size(); j++) {
                if (newIdea[j].foundWordInBoth(keywords[i])) {
                    input.idList.push_back(newIdea[j].getID());
                    //removeDuplicates(input.idList);

                }
            } 
            tree.AVL_Insert(input);
        }
    }
}

上面的代码搜索我的想法库中的匹配，并将有匹配的想法的ID推回到我的AVL树中，我每次创建一个新的想法时都会调用这个函数，但是它存储了新的键以及所有以前的键。

这是我试图做的：在插入AVL树之前，我有一个函数从我的向量中删除重复的内容，然后插入到我的树中，但是这并没有解决这个问题。

下面是我删除重复的函数

void removeDuplicates(vector<int> &v){
            auto end = v.end();
            for (auto it = v.begin();it !=end;it++){
                end = remove(it+1,end,*it);
            }
            v.erase(end,v.end());
        }

这段代码是从另一个被标记为正确的堆栈溢出问题中复制过来的，我正在寻找一种方法来检查一个键是否已经存在于树中，如果存在，则忽略它，而不是用重复的键重新填充树。

我正在寻找一种方法来检查一个键是否已经存在于树中，如果存在则忽略它，而不是用重复的键重新填充树。

EDIT：下面是我的插入函数的代码。我想可能有一种方法可以代替删除重复的内容？

template <class TYPE>
struct NODE 
    {
     TYPE    data;
     NODE   *left;
     NODE   *right;
     int     bal;
     int     count;
    } ; // NODE

template <class TYPE, class KTYPE>
bool   AvlTree<TYPE, KTYPE> :: AVL_Insert (TYPE dataIn) 
{
//  Local Definitions 
    NODE<TYPE>  *newPtr;
    bool         taller;

//  Statements 
    if (!(newPtr = new NODE<TYPE>))
       return false;
    newPtr->bal    = EH;
    newPtr->right  = NULL;
    newPtr->left   = NULL;
    newPtr->data   = dataIn;

    tree = _insert(tree, newPtr, taller);
    count++;
    return true;
}   //  Avl_Insert   

/*  ======================= _insert =======================
    This function uses recursion to insert the new data into 
    a leaf node in the AVL tree.
       Pre    application has called AVL_Insert, which passes 
              root and data pointers
       Post   data have been inserted
       Return pointer to [potentially] new root
*/

template <class TYPE, class KTYPE>
NODE<TYPE>*  AvlTree<TYPE,  KTYPE> 
         ::  _insert (NODE<TYPE>  *root, 
                      NODE<TYPE>  *newPtr, 
                      bool&        taller)
{
//  Statements   
    if (!root)
    {
        root    = newPtr;
        taller  = true;
        return  root;
    } //  if NULL tree 

    {
        return newPtr->data;
    }

    if (newPtr->data.key < root->data.key)
       {
        root->left = _insert(root->left, 
                             newPtr, 
                             taller);
        if (taller)
           //  Left subtree is taller 
           switch (root->bal)
              {
               case LH: // Was left high--rotate 
                        root = leftBalance (root, taller);
                        break;

               case EH: // Was balanced--now LH 
                        root->bal = LH;
                        break;

               case RH: // Was right high--now EH 
                        root->bal = EH;
                        taller    = false;
                        break;
              } // switch 
       } //  new < node 
    else 
       //  new data >= root data 
       {
        root->right = _insert (root->right, 
                               newPtr, 
                               taller);
        if (taller)
           // Right subtree is taller
           switch (root->bal)
               {
                case LH: // Was left high--now EH 
                         root->bal = EH;
                         taller    = false;
                         break;

                case EH: // Was balanced--now RH
                         root->bal = RH;
                         break;

                case RH: // Was right high--rotate 
                         root = rightBalance (root, taller);
                         break;
               } //  switch 
       } //  else new data >= root data 
    return root;
}   //  _insert 

Answer 1

首先，我会添加一个条件，以确保你没有将它与自身进行比较。所以，只要添加。

if(loop != j)