Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- template<typename T, typename S>
- class Map {
- public:
- struct Node {
- T key;
- S value;
- Node* left;
- Node* right;
- Node* parent;
- };
- Map() : root_(nullptr), size_(0) {}
- void insert(const T& key, const S& val) {
- if (root_ == nullptr) {
- root_ = new Node{ key, val, nullptr, nullptr, nullptr };
- size_++;
- return;
- }
- Node* parent = nullptr;
- Node* node = root_;
- while (node != nullptr && node->key != key) {
- parent = node;
- node = node->key > key ? node->left : node->right;
- }
- if (node == nullptr) {
- node = new Node{ key, val, nullptr, nullptr, parent };
- parent->key > key ? parent->left = node : parent->right = node;
- size_++;
- }
- }
- void erase(const T& key) {
- Node* parent = nullptr;
- Node* node = root_;
- while (node != nullptr && node->key != key) {
- parent = node;
- node = node->key > key ? 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->key = temp->key;
- 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_;
- }
- private:
- void print(Node* node) {
- if (node != nullptr) {
- print(node->left);
- cout << node->key << " " << node->value << endl;;
- print(node->right);
- }
- }
- Node* root_;
- int size_;
- };
- int main() {
- setlocale(LC_ALL, "ru");
- Map<string, string> book;
- book.insert("Оля", "+71111111111");
- book.insert("Гена", "+71111114444");
- book.insert("Вася", "+71111115555");
- book.insert("Аня", "+71111116666");
- book.print();
- book.erase("Гена");
- book.print();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement