C++ 맵 구현해보기

역시 STL 사용법은 패스

이진트리, 입력시 정렬을 보장함, 검색에 유리함

자식 방문후 돌아과정이 있어 추가 삭제시 리스트 보다 느림

#pragma once
#include <iostream>
 
template<typename TKey, typename TValue>
class MyMap {
private:
    template<typename TKey, typename TValue>
    class Node {
    public:
        Node() : key(nullptr), value(nullptr), left(nullptr), right(nullptr), parent(nullptr) {}
        Node(TKey* data, TValue* value) : key(data), value(value), left(nullptr), right(nullptr), parent(nullptr) {}
        Node(TKey* data, TValue* value, Node* left, Node* right) :key(data), value(value), left(left), right(right), parent(nullptr) {}
        ~Node() {
            delete key;
            delete value;
        }
        TKey* key;
        TValue* value;
        Node* left;
        Node* right;
        Node* parent;
    };
    size_t size;
    Node<TKey, TValue>* root;
    bool Sort(Node<TKey, TValue>* parent, Node<TKey, TValue>* node);
    void Print(Node<TKey, TValue>* node, int indent);
public:
    MyMap();
    ~MyMap();
    void Insert(TKey key, TValue value);
    void Remove(TKey key);
    size_t Size();
    void Print();
};
template<typename TKey, typename TValue>
MyMap<TKey, TValue>::MyMap() {
    root = nullptr;
    size = 0;
}
template<typename TKey, typename TValue>
MyMap<TKey, TValue>::~MyMap() {
}
template<typename TKey, typename TValue>
void MyMap<TKey, TValue>::Insert(TKey key, TValue value) {
    TKey* temp_key = new TKey(key);
    TValue* temp_value = new TValue(value);
    Node<TKey, TValue>* node = new Node<TKey, TValue>(temp_key, temp_value);
    if (root == nullptr) {
        root = node;
    }
    else {
        Sort(root, node);
    }
    size++;
}
template<typename TKey, typename TValue>
bool MyMap<TKey, TValue>::Sort(Node<TKey, TValue>* parent, Node<TKey, TValue>* node) {
    if (parent == nullptr) {
        return true;
    }
    if (*parent->key > *node->key) {
        node->parent = parent;
        if (Sort(parent->left, node) == true) {
            parent->left = node;
        }
    }
    else if (*parent->key < *node->key) {
        node->parent = parent;
        if (Sort(parent->right, node) == true) {
            parent->right = node;
        }
    }
    else {
        node->parent = parent->parent;
        node->left = parent->left;
        node->right = parent->right;
        if (node->parent != nullptr) {
            if (*node->parent->key > *node->key) {
                node->parent->left = node;
            }
            else if (*node->parent->key < *node->key) {
                node->parent->right = node;
            }
        }
        else {
            root = node;
        }
        if (node->left != nullptr) {
            node->left->parent = node;
        }
        if (node->right != nullptr) {
            node->right->parent = node;
        }
        delete parent;
        parent = node;
        size--;
    }
    return false;
}
template<typename TKey, typename TValue>
void MyMap<TKey, TValue>::Remove(TKey key) {
    Node<TKey, TValue>* node = root;
    while (true)
    {
        if (node == nullptr) {
            std::cout << "key not found" << std::endl;
            return;
        }
        if (*node->key > key) {
            node = node->left;
        }
        else if (*node->key < key) {
            node = node->right;
        }
        else {
            break;
        }
    }
    if (node->left == nullptr && node->right == nullptr)
    {
        if (node->parent != nullptr)
        {
            if (node->parent->left == node) {
                node->parent->left = nullptr;
            }
            else {
                node->parent->right = nullptr;
            }
        }
        else {
            root = nullptr;
        }
    }
    else if ((node->left == nullptr) || (node->right == nullptr))
    {
        Node<TKey, TValue>* child = (node->left != nullptr) ? node->left : node->right;
        if (node->parent != nullptr)
        {
            if (node->parent->left == node) {
                node->parent->left = child;
            }
            else {
                node->parent->right = child;
            }
        }
        else {
            root = child;
        }
        child->parent = node->parent;
    }
    else
    {
        Node<TKey, TValue>* child = node->left;
        while (child->right != nullptr)
        {
            child = child->right;
        }
        if (child == node->left) {
            child->parent = node->parent;
            if (child->parent != nullptr) {
                child->parent->right = child;
            }
            child->right = node->right;
            child->right->parent = child;
        }
        else {
            if (child->left != nullptr) {
                child->parent->right = child->left;
                child->left->parent = child->parent;
                child->right = node->right;
                child->right->parent = child;
            }
            else {
                child->parent->right = nullptr;
                child->parent = node->parent;
                child->right = node->right;
                child->right->parent = child;
 
                child->left = node->left;
                child->left->parent = child;
            }
        }
        if (node->parent == nullptr) {
            root = child;
        }
    }
    delete node;
    size--;
    std::cout << "--------------------Remove-----------------" << std::endl;
}
template<typename TKey, typename TValue>
size_t MyMap<TKey, TValue>::Size() {
    return size;
}
 
template<typename TKey, typename TValue>
void MyMap<TKey, TValue>::Print(Node<TKey, TValue>* node, int indent) {
    if (node != nullptr) {
        if (node->right) Print(node->right, indent + 4);
        if (indent) {
            for (int i = 0; i < indent; i++) std::cout << ' ';
        }
        if (node->right) {
            std::cout << " /\n";
            for (int i = 0; i < indent; i++) std::cout << ' ';
        }
        std::cout << *node->key << "," << *node->value << "\n";
        if (node->left) {
            for (int i = 0; i < indent; i++) std::cout << ' ';
            std::cout << " \\\n";
            Print(node->left, indent + 4);
        }
    }
}
template<typename TKey, typename TValue>
void MyMap<TKey, TValue>::Print() {
    Print(root, 0);
}