дерево поиска Т1 для дерева Т

#include "exception.h"
#include "node.h"

// конструктор
Node::Node(double e)
{
    element = e;
    left = NULL;
    right = NULL;
}

// конструктор копирования
Node::Node(Node& other)
{
    element = other.element;
    left = NULL;
    right = NULL;
    if(other.left) left = new Node(*other.left);
    if(other.right) right = new Node(*other.right);
}

// деструктор
Node::~Node()
{
    // рекурсивное удаление всех узлов левого поддерева
    // благодаря автоматическому вызову их деструкторов
    delete left;

    // рекурсивное удаление всех узлов правого поддерева
    // благодаря автоматическому вызову их деструкторов
    delete right;
}

// оператор присваивания
Node& Node::operator=(Node& other)
{
    element = other.element;
    delete left;
    delete right;
    left = NULL;
    right = NULL;
    if(other.left) left = new Node(*other.left);
    if(other.right) right = new Node(*other.right);
    return *this;
}

// оператор сравнения
bool Node::operator==(Node& other)
{
    if(element != other.element) return false;

    if(left && !other.left) return false;
    if(!left && other.left) return false;

    if(right && !other.right) return false;
    if(!right && other.right) return false;

    if(left && other.left && !(*left == *other.left)) return false;
    if(right && other.right && !(*right == *other.right)) return false;

    return true;
}

// размер поддерева (число элементов)
int Node::size()
{
    int size = 1;

    // рекурсивный подсчет размеров поддеревьев
    if(left) size += left->size();
    if(right) size += right->size();

    return size;
}

// балансировка для поддержания дерева
// в идеально сбалансированном состоянии
void Node::balance()
{
    int left_size = 0;
    if(left) left_size = left->size();

    int right_size = 0;
    if(right) right_size = right->size();

    // если левое поддерево больше, чем на 1 от правого
    if(left_size - right_size > 1)
    {
        // если правого узла нет, то создание правого узла с текущим элементом
        if(right == NULL) right = new Node(element);
        // иначе добавление текущего элемента в правый узел
        else *right += element;

        // поиск указателя на максимальный элемент в левом поддереве
        Node** p = &left;
        while((*p)->right) p = &(*p)->right;

        // этот максимальный элемент становится текущим
        element = (*p)->element;

        // удаление узла с максимальным элементом
        // с удочерением его левого поддерева
        Node* removed = (*p);
        (*p) = (*p)->left;
        removed->left = NULL;
        delete removed;
    }
    // если правое поддерево больше, чем на 1 от левого
    else if(right_size - left_size > 1)
    {
        // если левого узла нет, то создание левого узла с текущим элементом
        if(left == NULL) left = new Node(element);
        // иначе добавление текущего элемента в левый узел
        else *left += element;

        // поиск указателя на минимальный элемент в правом поддереве
        Node** p = &right;
        while((*p)->left) p = &(*p)->left;

        // этот минимальный элемент становится текущим
        element = (*p)->element;

        // удаление узла с минимальным элементом
        // с удочерением его правого поддерева
        Node* removed = (*p);
        (*p) = (*p)->right;
        removed->right = NULL;
        delete removed;
    }

    // рекурсивная балансировка поддеревьев
    if(left) left->balance();
    if(right) right->balance();
}

// оператор добавления элемента
void Node::operator+=(double e)
{
    // если добавляемый элемент меньше текущего, то добавление влево
    if(e < element)
    {
        // если левого узла нет, то создание левого узла
        if(left == NULL) left = new Node(e);
        // иначе добавление элемента в левый узел
        else *left += e;
    }
    // иначе добавление вправо
    else
    {
        // если правого узла нет, то создание правого узла
        if(right == NULL) right = new Node(e);
        // иначе добавление элемента в правый узел
        else *right += e;
    }
}

// печать узла
void Node::print(int depth)
{
    // печать левого поддерева (если есть)
    if(left) left->print(depth + 1);

    // печать пробелов до нужной глубины текущего узла
    for(int i = 0; i < depth; i++) cout << "  ";

    // печать элемента
    cout << element << endl;

    // печать правого поддерева (если есть)
    if(right) right->print(depth + 1);
}

// определение максимальной глубины
int Node::max_depth()
{
    // своя глубина
    int depth = 1;

    // глубина левого поддерева
    int left_depth = 1;
    if(left) left_depth = 1 + left->max_depth();

    // глубина правого поддерева
    int right_depth = 1;
    if(right) right_depth = 1 + right->max_depth();

    // возвращение максимума из трех глубин
    if(left_depth > depth) depth = left_depth;
    if(right_depth > depth) depth = right_depth;
    return depth;
}

// определение есть ли в поддереве хотя бы 2 одинаковых элемента
bool Node::contains_same_elements()
{
    // определение совпадает ли текущий элемент с левым/правым
    if(left && left->element == element) return true;
    if(right && right->element == element) return true;

    // рекурсивное определение по дочерним узлам
    if(left && left->contains_same_elements()) return true;
    if(right && right->contains_same_elements()) return true;

    // ничего не найдено
    return false;
}