Деревья

#include <iostream>
#include <conio.h>
#include <fstream>
using namespace std;
 
struct  bin_tree
{
   int value;
   bin_tree *left, *right;
}*pHead = NULL; // указатель на вершину равен нулю
 
// добавление конкретного узла дерева
void add_node(bin_tree*, int); 
// проверка на "пустоту" дерева, если указатель на вершину равен нулю, создает узел
void add_bin_tree(int);
// обход
void print(bin_tree*);
void traversal(bin_tree*, ofstream&);
int h_tree(bin_tree *);
 
int main()
{
    setlocale (LC_ALL, "Russian");
    int choose, el;
    cout<< "1. Загрузить последовательность с файла\n"
        << "2. Ввести последовательность вручную\n\n"
        << "Ваш выбор: ";
    do{ cin>> choose;} while(choose != 1 && choose != 2);
    if (choose == 1)
    {        
        ifstream iz("bin.txt");
        if (iz.bad()) return 1;
        while(!iz.eof() && iz>> el)
            add_bin_tree (el);     
        iz.close();
    }
    
    if (choose == 2)
    {
        cout<< "Информационные поля вершин дерева:\n";
        while(cin>> el)
            add_bin_tree (el);
    }
    ofstream o("bin.txt");
    print (pHead);
    traversal (pHead, o);
    getch();
    o.close();
    return 0;
}
 
void add_node(bin_tree* tree, int value) // добавление конкретного узла дерева
{
    if(value < tree->value)
    { 
        if(tree->left != NULL) // если значение меньше, двигаемся по "левой ветке"
            add_node(tree->left, value);
        else
        {  
            tree->left = new bin_tree;
            tree->left->value = value;
            tree->left->left = NULL;
            tree->left->right = NULL;
        }
    }
 
    if(value > tree->value) // иначе двигаемся по правой 
    { 
        if(tree->right != NULL)
            add_node(tree->right, value);
        else
        {
            tree->right = new bin_tree;
            tree->right->value = value;
            tree->right->left=NULL;
            tree->right->right=NULL;
        }
    }
 
    if(value == tree->value)                
        cout<< value<< " is already in tree"<< endl;
}
 
void add_bin_tree(int value)
{
    if(pHead == NULL) // если дерево пустое - создадим первый узел
    {
       pHead = new bin_tree;
       pHead->value = value;
       pHead->left = NULL;
       pHead->right = NULL;
    }
    else
        add_node(pHead, value); // если в вершине уже что-то есть - добавляем слева или справа 
}
 
void traversal(bin_tree* tree, ofstream &o)
{     
    if (tree != NULL)
    { 
        traversal(tree->left, o);
        o<< tree->value<< " ";
        traversal(tree->right, o);
    }
}
 
void print(bin_tree* tree)
{     
    if (tree != NULL)
    { 
        print(tree->left);
        cout<< tree->value<< " ";
        print(tree->right);
    }
}
 
int h_tree(bin_tree* tree)
{
     int h = 1, m = 0, s;
     if (tree == NULL)
        return 0;
     s = h_tree(tree->left);
     if (s > m)
         m = s;
     s = h_tree(tree->right);
     if (s > m)
         m = s;
     return h + m;
}

#ifndef AVL_TREE_H
#define AVL_TREE_H
 
#include <iostream>
#include <iomanip>
 
using namespace std;
 
struct node
{
    int key;
    int height;
    node *parent;
    node *left_child;
    node *right_child;
 
    node (int, node*); 
    node(int, int, node*, node*, node*); 
    ~node();
 
    void calc_height(); //рассчитывает высоту узла (исходя из условия что высота потомков уже рассчитана).
    int get_balance_factor(); //возвращает балланс-фактор для данного узла.
};
 
class AVL_tree {
private:
    node *root;
    int num_nodes; //кол-во узлов в дереве.
 
    node *GetMinChild(node *_node); //возвращает указатель на минимального потомка узла.
    void RecursPrintTree(node *_node);
    void DeleteSimpleNode(node*); //удаление узла, у которого не более одного дочернего узла.
    void ClearRecursion(node*); //вызывается деструктором.
 
    void Rotate(node*, bool); //поворот поддерева относительно его корня (в какую сторону - определяется параметром bool).
    void Balance(node*); //баллансировка узла.
 
public:
    AVL_tree();
    ~AVL_tree();
 
    void Insert_node (int);
    bool Delete_node (int); 
    node* SearchByKey (int);
    void Clear_tree();
 
    void Print_tree();
};
 
#endif

#include "AVL_tree.h"
 
node::node (int _key, node *_parent) 
{
    key = _key;
    height = 1;
    parent = _parent;
    left_child = nullptr;
    right_child = nullptr;
}
 
node::~node()
{
}
 
void node::calc_height()
{
    if (left_child && right_child) {
        height = max(left_child->height, right_child->height) + 1;
    }
    else if (left_child) {
        height = left_child->height + 1;
    }
    else if (right_child) {
        height = right_child->height + 1;
    }
    else {
        height = 1;
    }
}
 
int node::get_balance_factor()
{
    int l_h = left_child ? left_child->height : 0;
    int r_h = right_child ? right_child->height : 0;
 
    return r_h - l_h;
}
 
 
AVL_tree::AVL_tree()
{
    root = new node(0, nullptr);
    num_nodes = 0;
}
 
AVL_tree::~AVL_tree()
{
    ClearRecursion(root);
}
 
void AVL_tree::Insert_node (int ins_key)
{
    if (!num_nodes) {
        root->key = ins_key;
        num_nodes++;
        return;
    }
        
    node *cur_node = root;
    while (true) {
        if (ins_key < cur_node->key) {
            if (cur_node->left_child) {
                cur_node = cur_node->left_child;
            }
            else {
                cur_node->left_child = new node(ins_key, cur_node); 
                break;
            }
        }
        else {
            if (cur_node->right_child) {
                cur_node = cur_node->right_child;
            }
            else {
                cur_node->right_child = new node(ins_key, cur_node);
                break;
            }
        }
    }
    num_nodes++;
 
    while (cur_node) { //баллансируем.
        cur_node->calc_height();
        Balance(cur_node);
        cur_node = cur_node->parent;
    }
}
 
bool AVL_tree::Delete_node(int del_key)  //дерево баллансируется в функции DeleteSimpleNode(...).
{
    node *del_node = SearchByKey(del_key);
 
    if (num_nodes && del_node) { //если такой узел присутствует в дереве.
        if (!del_node->left_child || !del_node->right_child) { //если у узла del_node не более одного дочерних узла.
            DeleteSimpleNode(del_node);
        }
        else {   //если у узла del_node два дочерних узла.
            node *successor_node = GetMinChild(del_node->right_child);
            del_node->key = successor_node->key;
 
            DeleteSimpleNode(successor_node);
        }
        num_nodes--;
        return true;
    }
    else {
        return false;
    }
 
} 
 
node* AVL_tree::SearchByKey(int seek_key)
{
    node *cur_node = root;
    while (cur_node && cur_node->key != seek_key) {
        if (seek_key < cur_node->key) {
            cur_node = cur_node->left_child;
        }
        else {
            cur_node = cur_node->right_child;
        }
    }
    return cur_node;
}
 
void AVL_tree::Clear_tree()
{
    ClearRecursion(root->left_child);
    ClearRecursion(root->right_child);
    num_nodes = 0;
    root->left_child = nullptr;
    root->right_child = nullptr;
    root->height = 1;
}
 
void AVL_tree::Print_tree()
{
    if (num_nodes) {
        RecursPrintTree(root);
    }
    else {
        cout <<"Дерево пусто.\n";
    }
}
 
void AVL_tree::RecursPrintTree(node *_node)
{
    node *cur_node = _node;
    cout <<cur_node->key <<"(" <<cur_node->height <<"): ";
    if (cur_node->left_child) {
        cout <<cur_node->left_child->key <<"(l) ";
    }
    else {
        cout <<"     ";
    }
    if (cur_node->right_child) {
        cout <<cur_node->right_child->key <<"(r) ";
    }
    cout <<'\n';
 
    if (cur_node->left_child) {
        RecursPrintTree(cur_node->left_child);
    }
    if (cur_node->right_child) {
        RecursPrintTree(cur_node->right_child);
    }
}
                                          
node* AVL_tree::GetMinChild(node *_node)
{
    node *cur_node = _node;
    
    while (cur_node->left_child) {
        cur_node = cur_node->left_child;
    }
 
    return cur_node;
}
 
void AVL_tree::DeleteSimpleNode(node *del_node) 
{
    if (!del_node->right_child) {  //если у узла del_node нет правого дочернего узла.
        if (del_node == root) {
            root = del_node->left_child;
            if (!root) {
                root = new node(0, nullptr);
            }
        }
        else if (del_node == del_node->parent->left_child) {
            del_node->parent->left_child = del_node->left_child;
        }
        else if (del_node == del_node->parent->right_child) {
            del_node->parent->right_child = del_node->left_child;
        }
 
        if (del_node->left_child) {
            del_node->left_child->parent = del_node->parent;
        }
    }
    else if (!del_node->left_child) {  //если у узла del_node нет левого дочернего узла.
        if (del_node == root) {
            root = del_node->right_child;
            if (!root) {
                root = new node(0, nullptr);
            }
        }
        else if (del_node == del_node->parent->left_child) {
            del_node->parent->left_child = del_node->right_child;
        }
        else if (del_node == del_node->parent->right_child) {
            del_node->parent->right_child = del_node->right_child;
        }
 
        if (del_node->right_child) {
            del_node->right_child->parent = del_node->parent;
        }
    }
    node *cur_node = del_node->parent;
    delete del_node;
 
    while (cur_node) {  //баллансируем.
        cur_node->calc_height();
        Balance(cur_node);
        cur_node = cur_node->parent;
    }
}
 
void AVL_tree::ClearRecursion(node *start_clear_node)
{
    node *cur_clear_node = start_clear_node;
    if (cur_clear_node) {
        ClearRecursion(cur_clear_node->left_child);
        ClearRecursion(cur_clear_node->right_child);
        delete cur_clear_node;
    }
}
 
void AVL_tree::Rotate(node *rotate_node, bool rl_flag)  //не доделана.
{
    if (rl_flag) { //поворачиваем вправо.
        node *l_ch = rotate_node->left_child;
        if (rotate_node->parent && rotate_node->parent->left_child == rotate_node) {
            rotate_node->parent->left_child = l_ch;
        }
        else if (rotate_node->parent && rotate_node->parent->right_child == rotate_node) {
            rotate_node->parent->right_child = l_ch;
        }
        node *save_right = l_ch->right_child;
        l_ch->right_child = rotate_node;
        rotate_node->left_child = save_right;
 
        l_ch->parent = rotate_node->parent;
        rotate_node->parent = l_ch;
        if (rotate_node->left_child) {
            rotate_node->left_child->parent = rotate_node;
        }
 
        rotate_node->calc_height();
        l_ch->calc_height();
 
        if (rotate_node == root) {
            root = l_ch;
        }
    }
    else { //поворачиваем влево.
        node *r_ch = rotate_node->right_child;
        if (rotate_node->parent && rotate_node->parent->left_child == rotate_node) {
            rotate_node->parent->left_child = r_ch;
        }
        else if (rotate_node->parent && rotate_node->parent->right_child == rotate_node) {
            rotate_node->parent->right_child = r_ch;
        }
        node *save_left = r_ch->left_child;
        r_ch->left_child = rotate_node;
        rotate_node->right_child = save_left;
 
        r_ch->parent = rotate_node->parent;
        rotate_node->parent = r_ch;
        if (rotate_node->right_child) {
            rotate_node->right_child->parent = rotate_node;
        }
        
        rotate_node->calc_height();
        r_ch->calc_height();
 
        if (rotate_node == root) {
            root = r_ch;
        }
    }
}
 
void AVL_tree::Balance(node *b_node)
{
    if (b_node->get_balance_factor() == -2) {
        if (b_node->left_child->get_balance_factor() < 0) {
            Rotate(b_node->left_child, true);
        }
        else if (b_node->left_child->get_balance_factor() > 0) {
            Rotate(b_node->left_child, false);
        }
        Rotate(b_node, true);
    }
    else if (b_node->get_balance_factor() == 2) {
        if (b_node->right_child->get_balance_factor() < 0) {
            Rotate(b_node->right_child, true);
        }
        else if (b_node->right_child->get_balance_factor() > 0) {
            Rotate(b_node->right_child, false);
        }
        Rotate(b_node, false);
    }
}

#include "AVL_tree.h"
 
#include <iostream>
#include <fstream>
#include <locale>
#include <string>
#include <iomanip>
#include <ctime>
 
using namespace std;
 
const int START_SIZE = 1000;
const int MAX_SIZE = 100000;
const int SIZE_STEP = 1000;
 
void Test_Tree();
void Get_Time(ofstream&);
 
int main()
{
    locale::global(locale("Russian"));
 
    ofstream results("D:\\AVL_functions.txt");
 
    string Command;
    cout <<"Список команд:\n"
         <<"\t\"Test_Tree\" - тестировать дерево;\n"
         <<"\t\"Get_Time\" - измерить время работы функций;\n"
         <<"Введите команду: ";
    cin >>Command;
 
    if (Command == "Test_Tree") {
        Test_Tree();
    }
    else if (Command == "Get_Time") {
        Get_Time(results);
    }
    else {
        cout <<"Неизвестная команда.\n";
    }
 
    return 0;
}
 
void Test_Tree()
{
    AVL_tree Tree;
    string Command;
    int key;
    bool success;
 
    while (true) {
        cout <<"Введите команду: ";
        cin >>Command;
 
        if (Command == "Insert_node") {
            cout <<"Введите ключ: ";
            cin >>key;
            Tree.Insert_node(key);
        }
        else if (Command == "Delete_node") {
            cout <<"Введите ключ: ";
            cin >>key;
            success = Tree.Delete_node(key);
            if (!success) {
                cout <<"Узла с таким ключом в дереве нет.\n";
            }
        }
        else if (Command == "Clear_tree") {
            Tree.Clear_tree();
        }
        else if (Command == "Print") {
            Tree.Print_tree();
        }
        else if (Command == "end_test") {
            break;
        }
        else {
            cout <<"Неизвестная команда\n";
        }
    }
}
 
void Get_Time(ofstream &res)
{
    AVL_tree Tree;
    double dur_insert, dur_delete, dur_search, dur_clear;
    int cur_size, i;
    clock_t start, finish;
 
    for (cur_size = START_SIZE; cur_size <= MAX_SIZE; cur_size += SIZE_STEP) {
        start = clock();
        for (i = 0;  i < cur_size; i++) {
            Tree.Insert_node(rand());
        }
        finish = clock();
        dur_insert = (double)(finish-start)/CLOCKS_PER_SEC;
 
        start = clock();
        for (i = 0; i < cur_size; i++) {
            Tree.Delete_node(rand());
        }
        finish = clock();
        dur_delete = (double)(finish-start)/CLOCKS_PER_SEC;
 
        Tree.Clear_tree();
        for (i = 0;  i < cur_size; i++) {
            Tree.Insert_node(rand());
        }
 
        start = clock();
        for (i = 0; i < cur_size; i++) {
            Tree.SearchByKey(rand());
        }
        finish = clock();
        dur_search = (double)(finish-start)/CLOCKS_PER_SEC;
 
        start = clock();
        Tree.Clear_tree();
        finish = clock();
        dur_clear = (double)(finish-start)/CLOCKS_PER_SEC;
 
        res <<left <<setw(15) <<cur_size <<setw(15) <<dur_insert <<setw(15) <<dur_delete <<setw(15) <<dur_search <<setw(15) <<dur_clear <<'\n';
    }
}