Binary Search Tree 2024

// ConsoleApplication1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <optional>
#include <stack>
#include <string>
#include <functional>
#include <queue>

template <typename Key, typename Data>
class bst
{
    struct node
    {
        Key key;
        Data data;
        node* left = nullptr, * right = nullptr;
    } *root = nullptr;
    size_t count = 0;
    //возвращает адрес указателя, по которому должен располагаться узел с ключом k
    node** _find(const Key& k)const;
public:
    bst() {};
    ~bst();
    std::optional<std::reference_wrapper<Data>> find(const Key& k)const;
    void insert(const Key& k, const Data& d);
    std::optional<Key> findnext(const Key& k)const;
    std::optional<Key> findprev(const Key& k)const;
    void remove(const Key& k);
    void visit(std::function<void(const Key&, const Data&)> worker) const;
    size_t height() const; //вычисление высоты с помощью очереди
    size_t height2() const; //вычисление высоты с помощью стека
    std::vector<std::pair<Key, Data>> dump() const;
    bool is_bst_by_secondary_key() const;
    int width() const;
};



int main()
{
    bst<std::string, int> t;
    t.insert("one", 1);
    t.insert("two", 2);
    t.insert("three", 3);
    t.insert("four", 4);
    t.insert("five", 5);
    t.insert("six", 6);
    t.insert("seven", 7);
    t.insert("eight", 8);
    t.insert("nine", 9);
    t.insert("ten", 10);
    t.insert("eleven", 11);
    t.insert("twelve", 12);
    std::cout << t.width() << std::endl;
    std::cout << t.height() << " " << t.height2() << std::endl;
    auto dump = t.dump();
    for (auto [k, d] : dump)
        std::cout << k << " " << d << std::endl;

    std::cout << *t.find("five") << std::endl;
    (*t.find("five")).get() = 50;
    (int&)*t.find("five") = 500;
    std::cout << *t.find("five") << std::endl;

    std::cout << "Hello World!\n";
}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.

template<typename Key, typename Data>
typename bst<Key, Data>::node** bst<Key, Data>::_find(const Key& k) const
{
    node** p = (node**)&root;
    while (*p && (*p)->key != k)
        p = (*p)->key < k ? &((*p)->right) : &((*p)->left);
    return p;
}

template<typename Key, typename Data>
bst<Key, Data>::~bst()
{
    std::stack<node*> s;
    node* current = root;
    while (current || s.size())
    {
        if (current)
        {
            s.push(current);
            current = current->left;
        }
        else
        {
            current = s.top()->right;
            delete s.top();
            s.pop();
        }
    }
}

template<typename Key, typename Data>
std::optional<std::reference_wrapper<Data>> bst<Key, Data>::find(const Key& k) const
{
    auto p = _find(k);
    if (*p) return (*p)->data;
    return std::nullopt;
}

template<typename Key, typename Data>
void bst<Key, Data>::insert(const Key& k, const Data& d)
{
    auto p = _find(k);
    if (*p) (*p)->data = d;
    else
    {
        *p = new node{ k,d };
        ++count;
    }
}

template<typename Key, typename Data>
std::optional<Key> bst<Key, Data>::findnext(const Key& k) const
{
    node** p = (node**)&root;
    node** lastleft = nullptr;
    while (*p)
        p = k < (*p)->key ? (lastleft = p, &((*p)->left)) : &((*p)->right);
    return lastleft ? std::optional<Key>((*lastleft)->key) : std::nullopt;
}

template<typename Key, typename Data>
void bst<Key, Data>::remove(const Key& k)
{
    node** p = _find(k);
    if (*p == nullptr) return;
    --count;
    if (!(*p)->left || !(*p)->right)
    {
        auto tmp = *p;
        *p = tmp->left ? tmp->left : tmp->right;
        delete tmp;
    }
    else {
        auto nxt = &(*p)->right;
        while ((*nxt)->left) nxt = &(*nxt)->left;
        (*p)->key = (*nxt)->key;
        (*p)->data = (*nxt)->data;
        node* tmp = *nxt;
        *nxt = tmp->right;
        delete tmp;
    }
}

template<typename Key, typename Data>
void bst<Key, Data>::visit(std::function<void(const Key&, const Data&)> worker) const
{
    std::stack<node*> s;
    node* current = root;
    while (current || s.size())
    {
        if (current)
        {
            s.push(current);
            current = current->left;
        }
        else
        {
            current = s.top()->right;
            worker(s.top()->key, s.top()->data);
            s.pop();
        }
    }
}

template<typename Key, typename Data>
size_t bst<Key, Data>::height() const
{
    if (!root) return 0;
    std::queue<node*> Q;
    size_t h = 0;
    Q.push(root);
    while (Q.size())
    {
        ++h;
        size_t level_size = Q.size();
        for (size_t i = 0; i < level_size; i++)
        {
            auto p = Q.front();
            Q.pop();
            if (p->left) Q.push(p->left);
            if (p->right) Q.push(p->right);
        }
    }
    return h;
}

template<typename Key, typename Data>
size_t bst<Key, Data>::height2() const
{
    std::stack<std::pair<node*, size_t>> s;
    node* current = root;
    size_t current_level = 0, maxlevel = 0;
    while (current || s.size())
    {
        if (current)
        {
            s.push({ current,current_level });
            current = current->left;
            ++current_level;
        }
        else
        {
            maxlevel = std::max(maxlevel, s.top().second);
            current = s.top().first->right;
            current_level = s.top().second + 1;
            s.pop();
        }
    }
    return maxlevel;
}

template<typename Key, typename Data>
std::vector<std::pair<Key, Data>> bst<Key, Data>::dump() const
{
    std::vector<std::pair<Key, Data>> dmpvec;
    this->visit([&dmpvec](const Key& k, const Data& d) {dmpvec.push_back({ k,d }); return; });
    return dmpvec;
}

template<typename Key, typename Data>
bool bst<Key, Data>::is_bst_by_secondary_key() const
{
    std::optional<Data> prevdata;
    bool result = true;
    visit([&result, &prevdata](const Key& k, const Data& d) {
        if (prevdata && !(*prevdata < d))
            result = false;
        prevdata = d;
        });
    return result;
}

template<typename Key, typename Data>
int bst<Key, Data>::width() const
{
    std::stack<std::pair<node*, int>> s;
    node* current = root;
    int current_shift = 0;
    int minshift = 0, maxshift = 0;
    while (current || s.size())
    {
        if (current)
        {
            s.push({ current,current_shift });
            current = current->left;
            current_shift--;
        }
        else
        {
            minshift = std::min(minshift, s.top().second);
            maxshift = std::max(maxshift, s.top().second);
            current = s.top().first->right;
            current_shift = s.top().second + 1;
            s.pop();
        }
    }
    return maxshift - minshift;
}