Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- class Set {
- public:
- struct Node {
- int value;
- Node* left;
- Node* right;
- Node* parent;
- };
- Set() : root_(nullptr), size_(0) {}
- // другой вариант конструктора копирования
- /*Set(const Set& other) : root_(nullptr), size_(0) {
- copy(other.root_);
- }*/
- Set(const Set& other) : root_(copy(other.root_, nullptr)), size_(other.size_) {}
- void insert(const int& 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 int& 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;
- }
- ~Set() {
- clear(root_);
- }
- private:
- // другой вариант copy
- /*void copy(Node* node) {
- if (node != nullptr) {
- insert(node->value);
- copy(node->left);
- copy(node->right);
- }
- }*/
- 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() {
- int arr[]{ 45,30,50,27,39,90,15,70,103 };
- Set st;
- for (int i = 0; i < 9; i++) {
- st.insert(arr[i]);
- }
- st.print();
- cout << st.size() << endl;
- st.erase(15);
- st.erase(50);
- st.erase(45);
- st.print();
- cout << st.size() << endl;
- Set st2(st);
- st2.print();
- cout << st2.size() << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement