InvertedIndex/BST.cpp at master · adhamhesham97/InvertedIndex · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <vector>
using namespace std;

struct node
{
    vector<int> index;
    int document_number;
    string word;
    node *left;
    node *right;
};

class BST
{

private:
    node *root;

    void addleafprivate(int document_number, string word, node *ptr)
    {
        if (root == NULL)
        {

            root = createleaf(document_number, word);
        }
        else if (word < ptr->word)
        {
            if (ptr->left != NULL)
            {
                addleafprivate(document_number, word, ptr->left);
            }
            else
            {
                ptr->left = createleaf(document_number, word);
            }
        }
        else if (word > ptr->word)
        {
            if (ptr->right != NULL)
            {
                addleafprivate(document_number, word, ptr->right);
            }
            else
            {
                ptr->right = createleaf(document_number, word);
            }
        }
        else if (word == ptr->word)
        {
            if (document_number != ptr->index.back())
            {
                ptr->index.push_back(document_number);
                cout << word;
                cout << ptr->index.back() << endl;
            }
        }
    }

public:
    BST() { root = NULL; }
    node *createleaf(int document_number, string word)
    {
        node *n = new node;
        n->index.push_back(document_number);
        n->word = word;
        n->left = n->right = NULL;
        cout << n->word;

        for (int i = 0; i < n->index.size(); i++)
        {
            cout << n->index[i];
        }
        cout << endl;
        return n;
    }
    void addleaf(int document_number, string word)
    {
        addleafprivate(document_number, word, root);
    }

    bool search(string word, vector<int> &document)
    {
        node *current;
        current = root;
        while (current != NULL)
        {
            if (current->word == word)
            {
                document = current->index;
                return true;
            }
            else if (word < current->word)
            {
                current = current->left;
            }
            else if (word > current->word)
            {
                current = current->right;
            }
        }
        return false;
    }
};
int main()
{
    BST tree;
    vector<int> index;
    tree.addleaf(2, "yara");
    tree.addleaf(5, "aya");
    tree.addleaf(3, "yara");
    tree.addleaf(4, "aya");
    tree.addleaf(3, "hi");

    if (tree.search("yara", index))
    {

        for (int i = 0; i < index.size(); i++)
        {
            cout << index[i] << " ";
        }
    }
    else
    {
        cout << "NOT FOUND" << endl;
    }
    return 0;
}