Search_Engine/AVLTree.java at master · deepanshurathi553/Search_Engine · 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

public class AVLTree
{
    private AVLNode root;

    public AVLTree()
    {
        root = null;
    }
    public boolean isEmpty()
    {
        return root == null;
    }

    public AVLNode getRoot()
    {
	    return root;
    }
    public void insert(Position data)
    {
        root = insert1(root, data);
    }
    public int height(AVLNode node)
    {
        if (node == null)
            return 0;
        return node.getHeight();
    }

    public int max(int first, int second)
    {
        if(first>second) return first;
        else return second;
    }
    public boolean search(int wordIndex,PageEntry page)
    {
        return search(root,wordIndex,page);
    }

    public int isThisCorrect(AVLNode node)
    {
        if (node == null)
            return 0;
        return height(node.getLeft()) - height(node.getRight());
    }

    private boolean search(AVLNode r, int wordIndex,PageEntry page)
    {
        if(r==null)
            return false;
        Position current = r.getPosition();
        int cIndex=current.getWordIndex();
        if (wordIndex< cIndex)
            return search(r.getLeft(),wordIndex,page);
        else if (wordIndex >cIndex)
             return search(r.getRight(),wordIndex,page);
        else  if(page.equals(current.getPageEntry()))
            return true;
        else return search(r.getRight(),wordIndex,page) || search(r.getLeft(),wordIndex,page);

    }

    public AVLNode insert1( AVLNode node, Position key)
    {
        if (node == null)
            return(new AVLNode(key));

        if (key.getWordIndex()<=node.getPosition().getWordIndex())
            node.setLeft(insert1(node.getLeft(), key));
        else
            node.setRight(insert1(node.getRight(), key));
        node.setHeight( max(height(node.getLeft()), height(node.getRight())) + 1);

        int is = isThisCorrect(node);
        if (is > 1 && key.getWordIndex() <= node.getLeft().getPosition().getWordIndex())
            return rightRotate(node);

        if (is < -1 && key.getWordIndex() >node.getRight().getPosition().getWordIndex())
            return leftRotate(node);

        if (is > 1 && key.getWordIndex() > node.getLeft().getPosition().getWordIndex())
        {
            node.setLeft(leftRotate(node.getLeft()));
            return rightRotate(node);
        }

        if (is < -1 && key.getWordIndex() <= node.getRight().getPosition().getWordIndex())
        {
            node.setRight(rightRotate(node.getRight()));
                return leftRotate(node);
        }
        return node;
    }

    public AVLNode leftRotate(AVLNode node)
    {
        AVLNode n = node.getRight();
        AVLNode r = n.getLeft();
        n.setLeft(node);
        node.setRight(r);

        node.setHeight(max(height(node.getLeft()), height(node.getRight()))+1);
        n.setHeight(max(height(n.getLeft()), height(n.getRight()))+1);

        return n;
    }
    public AVLNode rightRotate(AVLNode node)
    {
        AVLNode l = node.getLeft();
        AVLNode r = l.getRight();
        l.setRight(node);
        node.setLeft(r);
        node.setHeight(max(height(node.getLeft()), height(node.getRight()))+1);
        l.setHeight(max(height(l.getLeft()), height(l.getRight()))+1);
        return l;
    }
 }