tree_visualizer/cartesiantree.cpp at main · sinfillo/tree_visualizer · 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
#include "cartesiantree.h"

Cartesiantree::Node* Cartesiantree::merge(Cartesiantree::Node* left_tree, Cartesiantree::Node* right_tree) {
    if (left_tree == nullptr) {
        return right_tree;
    }
    if (right_tree == nullptr) {
        return left_tree;
    }
    if (left_tree->priority > right_tree->priority) {
        left_tree->right = merge(left_tree->right, right_tree);
        return left_tree;
    } else {
        right_tree->left = merge(left_tree, right_tree->left);
        return right_tree;
    }
}

std::pair<Cartesiantree::Node*, Cartesiantree::Node*> Cartesiantree::split(Cartesiantree::Node *tree, int value) {
    if (tree == nullptr) {
        return { nullptr, nullptr };
    }

    if (tree->value <= value) {
        std::pair<Cartesiantree::Node*, Cartesiantree::Node*> cur = split(tree->right, value);
        tree->right = cur.first;

        return { tree, cur.second };
    } else {
        std::pair<Cartesiantree::Node*, Cartesiantree::Node*> cur = split(tree->left, value);
        tree->left = cur.second;

        return { cur.first, tree };
    }
}

void Cartesiantree::insert(Cartesiantree::Node*& tree, int value) {
    std::pair<Cartesiantree::Node*, Cartesiantree::Node*> cur = split(tree, value);
    Cartesiantree::Node* it = new Cartesiantree::Node(value);
    tree = merge(cur.first, merge(it, cur.second));

    return;
}

void Cartesiantree::erase(Cartesiantree::Node*& tree, int value) {
    std::pair<Cartesiantree::Node*, Cartesiantree::Node*> cur = split(tree, value);
    std::pair<Cartesiantree::Node*, Cartesiantree::Node*> cur_left = split(cur.first, value - 1);
    tree = merge(cur_left.first, cur.second);

    return;
}

bool Cartesiantree::is_exists(Cartesiantree::Node* tree, int value) {
    bool ans = false;
    std::pair<Cartesiantree::Node*, Cartesiantree::Node*> cur = split(tree, value);
    std::pair<Cartesiantree::Node*, Cartesiantree::Node*> cur_left = split(cur.first, value - 1);
    if (cur_left.second == nullptr) {
        ans = false;
    } else {
        ans = true;
    }

    tree = merge(merge(cur_left.first, cur_left.second), cur.second);

    return ans;
}