Movie-Manager-DS-Project/SplayTree.cpp at main · Arian84aw/Movie-Manager-DS-Project · 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
#include "SplayTree.h"


SplayNode* SplayTree::rightRotate(SplayNode* x) {
    SplayNode* y = x->left;
    x->left = y->right;
    y->right = x;
    return y;
}


SplayNode* SplayTree::leftRotate(SplayNode* x) {
    SplayNode* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}


SplayNode* SplayTree::splay(SplayNode* root, const string& targetKey) {
    if (root == nullptr || root->key == targetKey)
        return root;


    if (targetKey < root->key) {
        if (root->left == nullptr)
            return root;


        if (targetKey < root->left->key) {
            root->left->left = splay(root->left->left, targetKey);
            root = rightRotate(root);
        }

        else if (targetKey > root->left->key) {
            root->left->right = splay(root->left->right, targetKey);
            if (root->left->right != nullptr)
                root->left = leftRotate(root->left);
        }

        return (root->left == nullptr) ? root : rightRotate(root);
    }

    else {
        if (root->right == nullptr)
            return root;


        if (targetKey < root->right->key) {
            root->right->left = splay(root->right->left, targetKey);
            if (root->right->left != nullptr)
                root->right = rightRotate(root->right);
        }

        else if (targetKey > root->right->key) {
            root->right->right = splay(root->right->right, targetKey);
            root = leftRotate(root);
        }

        return (root->right == nullptr) ? root : leftRotate(root);
    }
}


void SplayTree::insert( string key) {
    if (root == nullptr) {
        root = new SplayNode(key);
        _size++;
        return;
    }


    root = splay(root, key);

    if (root->key == key)
        return;

    SplayNode* newNode = new SplayNode(key);
    _size++;


    if (key < root->key) {
        newNode->right = root;
        newNode->left = root->left;
        root->left = nullptr;
    }
    else {
        newNode->left = root;
        newNode->right = root->right;
        root->right = nullptr;
    }


    root = newNode;
}


void SplayTree::display() {
    if (root == nullptr) {
        cout << "tree is empty!" << endl;
        return;
    }

    queue<SplayNode*> q;
    q.push(root);

    while (!q.empty()) {
        SplayNode* current = q.front();
        q.pop();

        cout << "movie: " << current->key << endl;

        if (current->left != nullptr)
            q.push(current->left);
        if (current->right != nullptr)
            q.push(current->right);
    }
}