Бинарное дерево поиска. Его обслуживание, и поиск

///----------------------------------------------------------------------------|
/// Двоичное дерево поиска.
///----------------------------------------------------------------------------:
#include <iostream>
 
///-------------------|
/// Узел дерева.      |
///-------------------:
struct  node
{       node * m_left;
        node * m_right;
        node(int val)
        {   m_left  = NULL;
            m_right = NULL;
            m_data  = val ;
        }
    
    int m_data;
};
 
///-------------------|
/// Дерево.           |
///-------------------:
struct Map
{      Map(int);
      ~Map();
   
    void print();
    bool find(int);
    void insert(int);
    void erase(int);
    int  size();
 
 private:
    node * m_root;
    int m_size;
    void print_tree(node *);
    void delete_tree(node *);
};
 
///----------------------------------------------------------------------------|
/// Реализация методов.
///----------------------------------------------------------------------------:
Map::Map(int key)
{
    m_root = new node(key);
    m_size = 1;
}
 
Map::~Map()
{   delete_tree(m_root);
}
 
void Map::delete_tree(node * curr)
{   if (curr)
    {   delete_tree(curr->m_left);
        delete_tree(curr->m_right);
        delete curr;
    }
}
 
void Map::print()
{   print_tree(m_root);
    std::cout << std::endl;
}
 
void Map::print_tree(node * curr)
{   if (curr)
    {   print_tree(curr->m_left);
        std::cout << curr->m_data << " ";
        print_tree(curr->m_right);
    }
}
 
bool Map::find(int key)
{
    node* curr = m_root;
    while (curr && curr->m_data != key)
    {   if (curr->m_data > key) curr = curr->m_left;
        else                    curr = curr->m_right;
    }
    return curr != NULL;
}
 
void Map::insert(int key)
{
    node * curr = m_root;
    while (curr && curr->m_data != key)
    {   if (curr->m_data > key && curr->m_left == NULL)
        {   curr->m_left = new node(key);
            ++m_size;
            return;
        }
 
        if (curr->m_data < key && curr->m_right == NULL)
        {   curr->m_right = new node(key);
            ++m_size;
            return;
        }
        if (curr->m_data > key) curr = curr->m_left;
        else                    curr = curr->m_right;
    }
}
 
void Map::erase(int key)
{
    node * curr = m_root;
    node * parent = NULL;
    while (curr && curr->m_data != key)
    {   parent = curr;
        if (curr->m_data > key) curr = curr->m_left;
        else                    curr = curr->m_right;
    }
 
    if (!curr)return;
    if (curr->m_left == NULL)
    {   // Вместо curr подвешивается его правое поддерево
        if (parent && parent->m_left == curr)
            parent->m_left = curr->m_right;
        if (parent && parent->m_right == curr)
            parent->m_right = curr->m_right;
        --m_size;
        delete curr;
        return;
    }
    if (curr->m_right == NULL)
    {
        // Вместо curr подвешивается его левое поддерево
        if (parent && parent->m_left == curr)
            parent->m_left = curr->m_left;
        if (parent && parent->m_right == curr)
            parent->m_right = curr->m_left;
        --m_size;
        delete curr;
        return;
    }
    // У элемента есть два потомка, тогда на место элемента поставим
    // наименьший элемент из его правого поддерева
    node * replace = curr->m_right;
    while (replace->m_left)
        replace = replace->m_left;
    int replace_value = replace->m_data;
    erase(replace_value);
    curr->m_data = replace_value;
}
 
static int rrand(int range_min, int range_max)
{   return rand() % (range_max - range_min + 1) + range_min;
}
 
///----------------------------------------------------------------------------|
/// Тест.
///----------------------------------------------------------------------------:
int main()
{
    Map btree(0);
    for(int n = 10; n--;)
    {   btree.insert(rrand(-10,10));
    }
    btree.print();
 
    int key = 2;
    if(btree.find(key))
    {   btree.erase (key);
        btree.insert(777);
    }
    btree.print();
}