BTree

#ifndef BTREE_H
#define BTREE_H
#include <cstdlib>

template<typename T>
class BTree
{
public:
    BTree(const T&);

    void add(const T&);

    BTree* find(const T&);

    BTree* min_key();

    BTree* max_key();

    BTree* next();

    BTree* remove(const T&);

private:
    T key_;
    BTree* left_;
    BTree* right_;
    BTree* parent_;
};


/**
 *____________________________________
 *|                                   |
 *| О СТРУКТУРЕ И КАК ЕЙ ПОЛЬЗОВАТЬСЯ |
 *|___________________________________|
 *
 *-------------------------О СТРУКТУРЕ-------------------------------------
 *
 * Бинарное дерево - это структура данных,
 * которая имеет корень, значение и две ветви - правую и левую,
 * которые, в свою очередь, также хранят значения и две ветви.
 * Ветви могут быть как пустыми, так и непустыми.
 * Так же ветвь хранит ссылку на отцовскую ветвь,
 * если та не является родителем (т.е. инициализированна через nullptr)
 * Значение представленно универсальным типом const T,
 * который может конвертироваться в любой машинный тип
 *
 * --------------ПРАВИЛА ХРАНЕНИЯ И ИСПОЛЬЗОВАНИЯ---------------------------
 *
 * В БИНАРНОМ ДЕРЕВЕ КЛЮЧИ ПРАВОГО ПОДДЕРЕВА БОЛЬШЕ КЛЮЧЕЙ ЛЕВОГО ПОДДЕРЕВА
 * Это освновопологающее правило размещения в дереве. Рассмотрим его подробнее:
 * Допустим, у нас есть ключ с неким значением и дерево (непустое)
 * Мы будем идти вглубь дерева, и на каждом вхождении проверять ключи ветвей
 * Если ключ меньше ключа ветви, то отправляемся в правую ветвь,
 * иначе идём в левую ветвь. Так идём, пока не дойдём то конца всей корневой системы
 * Когда дошли, то проверяем наш ключ и ключ ветви, выбираем нужную ветвь
 * и определяем родителя для новой ветви по указателю, тем самым мы можем ходить по дереву
 */

 //----------------------------------------------------------------------------

 /**
  * Конструктор класса BTree
  * @param key - ключ, по которому
  * будет оcосуществляться доступ
  * к ветвям дерева
  */
template<typename T>
BTree<T>::BTree(const T& key)
{
    key_ = key;
    parent_ = nullptr;
    right_ = nullptr;
    left_ = nullptr;
}

//--------------------------------------------------------------------------

/**
 * Метод add() добавляет новую ветвь в дерево
 * в соответствии с правилами (см. выше)
 * @param key - ключ новой ветви
 */

template<typename T>
void BTree<T>::add(const T& key)
{
    const auto new_node = new BTree(key);

    /**
     * Создаём новую ветвь. Так как ветвь новая,
     * То она не может содержать в себе другие ветви,
     * А значит правая и левая ветвь инициализируется через nullptr
     */

    BTree* root2 = this, * root3 = nullptr;

    /**
     * root2 для поиска по дереву
     * root3 для сохранения текущей позиции в дереве
     */

    while (root2 != nullptr)
    {
        root3 = root2;
        if (key < root2->key_) root2 = root2->left_;
        else root2 = root2->right_;
    }

    /**
     * Углубляемся в дерево и ищем подходящий ключ
     * Если key меньше ключа, то идём налево
     * Иначе направо
     */

    new_node->parent_ = root3;

    /**
     * Сохранили указатель на родителя
     * Для доступа и подъёма по дереву
     */

    if (key < root3->key_) root3->left_ = new_node;
    else root3->right_ = new_node;

    /**
     * Выбираем подходящую ветвь:
     * Если ключ меньше ключа ветви,
     * то отправляемся в правую ветвь,
     * иначе идём в левую ветвь.
     */

}

//---------------------------------------------------------------

/**
 * Метод find() ищет ближайшую от вершины ветвь,
 * ключ которой соответствует @param key
 * @return указатель на ветвь в случае успеха,
 * иначе @return nullptr.
 */

template<typename T>
BTree<T>* BTree<T>::find(const T& key)
{
    // Начинаем поиск с вершины дерева

    auto root2 = this;

    /**
    * Углубляемся в дерево (по правилам, описанным выше),
    * пока не найдём ветвь с искомым ключом.
    * Иначе возвращаем nullptr
    */

    while (root2 != nullptr)
    {
        if (key < root2->key_) root2 = root2->left_;        // Если искомый ключ меньше, то идём в левую ветвь,
        else if (key > root2->key_) root2 = root2->right_;  // Иначе если искомый ключ больше - в правую,
        else return root2;                                  // Иначе нашли и возвращаем
    }
    return nullptr;                                         // Если не нашли, то возвращаем nullptr
}

//-----------------------------------------------------------------

/**
 * Метод min_key() ищет ветвь с минимальным ключом.
 * Т.к. в дереве все наименьшие "элементы" расположены в левой части,
 * то смело шагаем налево
 */

template<typename T>
BTree<T>* BTree<T>::min_key()
{
    auto min = this;

    /**
    * Углубляемся в левую часть дерева,
    * пока не дойдём до конца корневой системы
    */

    while (min->left_ != nullptr) min = min->left_;

    return min;
}

//-----------------------------------------------------------------

/**
 * Метод max_key() ищет ветвь с максимальным ключом.
 * Т.к. в дереве все наибольшие "элементы" расположены в правой части,
 * то смело шагаем направо
 */

template<typename T>
BTree<T>* BTree<T>::max_key()
{
    auto max = this;

    /**
     * Углубляемся в правую часть дерева,
     * пока не дойдём до конца корневой системы
     */

    while (max->right_ != nullptr) max = max->right_;

    return max;
}

//-------------------------------------------------------------------

/**
 * Метод next() ищет ветвь,
 * значение которой является ближайшим и больше
 * или равно текущему.
 * @return найденную ветвь или nullptr
 */

template<typename T>
BTree<T>* BTree<T>::next()
{
    // Если есть правая ветка, то ищем минимальный элемент там

    if (this->right_ != nullptr)
        return this->right_->min_key();

    // Правое дерево пусто, идем по родителям до тех пор,
    // пока не найдем родителя, для которого наша ветка левая

    BTree* l = this->parent_; // ветка для поднятия
    BTree* p = this;          // ветка для контроля значения

    while ((l != nullptr) && (p == l->right_))
    {
        p = l;
        l = l->parent_;
    }

    return l;
}

//--------------------------------------------------------------------

/**
 * Метод remove() очищает ветвь по @param key.
 * Возможны 3 случая размещения удаляемой ветки:
 *
 * 1) Когда у ветви нет дочерних ветвей.
 * В этом случае мы просто удаляем ветвь,
 * предварительно обнулив её для родителей
 *
 * 2) Когда у ветви есть 1 дочерняя ветвь.
 * В этом случае просто удаляем узел,
 *  и на его место ставим дочернюю ветвь
 *
 * 3) Когда у ветви есть обе дочерние ветви.
 * В этом случае ищем такую ветвь,
 * что она будет следующей для текущей.
 * Ставим этот узел на место удаляемой.
 *
 */

template<typename T>
BTree<T>* BTree<T>::remove(const T& key)
{
    // Поиск удаляемого узла по ключу

    BTree* p = this, * l = nullptr, * m = nullptr;
    l = p->find(key);

    // Если не нашли, то возвращаем nullptr

    if (l == nullptr) return nullptr;

    // 1 случай

    if ((l->left_ == nullptr) && (l->right_ == nullptr))
    {
        m = l->parent_;
        if (l == m->right_) m->right_ = nullptr;
        else m->left_ = nullptr;
        delete l;
    }

    // 2 случай, 1 вариант - поддерево справа

    if ((l->left_ == nullptr) && (l->right_ != nullptr))
    {
        m = l->parent_;
        if (l == m->right_) m->right_ = l->right_;
        else m->left_ = l->right_;
        delete l;
    }
    // 2 случай, 2 вариант - поддерево слева
    if ((l->left_ != nullptr) && (l->right_ == nullptr))
    {
        m = l->parent_;
        if (l == m->right_) m->right_ = l->left_;
        else m->left_ = l->left_;
        delete l;
    }
    // 3 случай
    if ((l->left_ != nullptr) && (l->right_ != nullptr))
    {
        m = l->next();
        l->key_ = m->key_;
        if (m->right_ == nullptr)
            m->parent_->left_ = nullptr;
        else m->parent_->left_ = m->right_;
        delete m;
    }
    return this;
}


#endif // BTREE_H