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

代码是从另一个标记为正确的堆栈溢出问题中复制的。

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

编辑：下面是我的插入函数代码。我在想可能有一种方法可以删除其中的重复项？

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)

AVL树的倒排索引算法每次重复键c ++

inverted index algorithm for AVL tree duplicates key each time c++

c++

avl-tree