Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- template<typename T>
- class Set {
- public:
- struct Node {
- T value;
- Node* left;
- Node* right;
- Node* parent;
- };
- Set() : root_(nullptr), size_(0) {}
- Set(const initializer_list<T>& list) : root_(nullptr), size_(0) {
- for (const T& element : list) {
- insert(element);
- }
- }
- Set(const Set& other) : root_(copy(other.root_, nullptr)), size_(other.size_) {}
- Set(Set&& other) : root_(other.root_), size_(other.size_) {
- other.root_ = nullptr;
- }
- Set& operator=(const Set& other) {
- if (this != &other) {
- clear();
- size_ = other.size_;
- root_ = copy(other.root_, nullptr);
- }
- return *this;
- }
- Set& operator=(Set&& other) {
- if (this != &other) {
- clear();
- size_ = other.size_;
- root_ = other.root_;
- other.root_ = nullptr;
- }
- return *this;
- }
- void insert(const T& val) {
- if (root_ == nullptr) {
- root_ = new Node{ val, nullptr, nullptr, nullptr };
- size_++;
- return;
- }
- Node* parent = nullptr;
- Node* node = root_;
- while (node != nullptr && node->value != val) {
- parent = node;
- node = node->value > val ? node->left : node->right;
- }
- if (node == nullptr) {
- node = new Node{ val, nullptr, nullptr, parent };
- parent->value > val ? parent->left = node : parent->right = node;
- size_++;
- }
- }
- void erase(const T& val) {
- Node* parent = nullptr;
- Node* node = root_;
- while (node != nullptr && node->value != val) {
- parent = node;
- node = node->value > val ? node->left : node->right;
- }
- if (node != nullptr) {
- if (node->left == nullptr && node->right == nullptr) {
- if (node == root_) {
- root_ = nullptr;
- }
- else {
- node == parent->right ? parent->right = nullptr : parent->left = nullptr;
- }
- delete node;
- }
- else if (node->left == nullptr) {
- node->right->parent = node->parent;
- if (node == root_) {
- root_ = node->right;
- }
- else {
- node == parent->right ? parent->right = node->right : parent->left = node->right;
- }
- delete node;
- }
- else if (node->right == nullptr) {
- node->left->parent = node->parent;
- if (node == root_) {
- root_ = node->left;
- }
- else {
- node == parent->right ? parent->right = node->left : parent->left = node->left;
- }
- delete node;
- }
- else {
- Node* temp = min(node->right);
- node->value = temp->value;
- if (temp->right != nullptr) {
- temp->right->parent = temp->parent;
- }
- temp == temp->parent->right ? temp->parent->right = temp->right : temp->parent->left = temp->right;
- delete temp;
- }
- size_--;
- }
- }
- Node* min(Node* node) {
- if (node != nullptr) {
- while (node->left != nullptr) {
- node = node->left;
- }
- }
- return node;
- }
- Node* max(Node* node) {
- if (node != nullptr) {
- while (node->right != nullptr) {
- node = node->right;
- }
- }
- return node;
- }
- void print() {
- print(root_);
- cout << endl;
- }
- int size() const {
- return size_;
- }
- void clear() {
- clear(root_);
- root_ = nullptr;
- size_ = 0;
- }
- Node* find(const T& val) {
- Node* node = root_;
- while (node != nullptr && node->value != val) {
- node = node->value > val ? node->left : node->right;
- }
- return node;
- }
- Node* begin() {
- return min(root_);
- }
- Node* end() {
- return max(root_);
- }
- bool operator==(const Set& other) {
- return size_ == other.size_ ? compare(min(root_), min(other.root_)) : false;
- }
- bool operator!=(const Set& other) {
- return !(*this == other);
- }
- ~Set() {
- clear(root_);
- }
- private:
- // вариант сравнения деревьев на случай разной топологии но одинакового размера
- bool compare(Node* a, Node* b) {
- if (a == nullptr && b == nullptr) {
- return true;
- }
- return a->value == b->value && compare(next(a), next(b));
- }
- Node* next(Node* node) {
- if (node != nullptr) {
- if (node->right != nullptr) {
- return min(node->right);
- }
- Node* temp = node->parent;
- while (temp != nullptr && node->value > temp->value) {
- temp = temp->parent;
- }
- return temp;
- }
- return node;
- }
- Node* prev(Node* node) {
- if (node != nullptr) {
- if (node->left != nullptr) {
- return max(node->left);
- }
- Node* temp = node->parent;
- while (temp != nullptr && node->value < temp->value) {
- temp = temp->parent;
- }
- return temp;
- }
- return node;
- }
- Node* copy(Node* node, Node* parent) {
- if (node == nullptr) {
- return nullptr;
- }
- Node* temp = new Node{ node->value, nullptr, nullptr, parent };
- temp->left = copy(node->left, temp);
- temp->right = copy(node->right, temp);
- return temp;
- }
- void clear(Node* node) {
- if (node != nullptr) {
- clear(node->left);
- clear(node->right);
- delete node;
- }
- }
- void print(Node* node) {
- if (node != nullptr) {
- print(node->left);
- cout << node->value << " ";
- // раскомментировать для проверки построения дерева
- /* cout << " value " << node->value << " ";
- if (node->parent) {
- cout << " parent " << node->parent->value;
- }
- else {
- cout << '\t';
- }
- if (node->left) {
- cout << " left " << node->left->value;
- }
- else {
- cout << '\t';
- }
- if (node->right) {
- cout << " right " << node->right->value;
- }
- else {
- cout << '\t';
- }
- cout << " " << node << endl;*/
- print(node->right);
- }
- }
- Node* root_;
- int size_;
- };
- int main() {
- setlocale(LC_ALL, "ru");
- Set<int> st{ 45,30,50,27,39,90,15,70,103 };
- st.print();
- cout << st.size() << endl;
- st.print();
- cout << st.size() << endl;
- Set<int> st2(st);
- st2.print();
- cout << st2.size() << endl;
- cout << (st == st2) << endl;
- st2.erase(45);
- st2.insert(45);
- st.print();
- st2.print();
- cout << (st == st2) << endl;
- auto node = st2.find(30);
- if (node != nullptr) {
- cout << node->value << endl;
- }
- Set<string> st3{ "один", "два", "три", "четыре" };
- st3.print();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement