#include <windows.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include <time.h>

//структура для хранения узла дерева
struct Node
{
 int  key;  //ключ
 Node *parent; //ссылка на родителя, для root = 0
 Node *left;  //ссылка на левого потомка
 Node *right;  //ссылка на правого потомка
 Node *next;  //начало кольца одинаковых ключей
 char *str;  //адрес строки
};

//структура для отображения дерева
struct OutTree
{
 Node *node;  //узел
 int  level;  //уровень узла, 0 (корень), 1, 2,... 
 int  offset;  //индексы поля, 0 для 0, 0,1 для 1, 0-3 для 2 и т.д.
};

//структуры для расчета времени выполнения
struct performance
{
 _LARGE_INTEGER  start;
 _LARGE_INTEGER  stop;
 _LARGE_INTEGER frequency;
};

struct key_perfomance
{
 int  key;
 char str[16];
 double mks;
};

//-------------------------------------------------
//Глобалльная переменная
//-------------------------------------------------
Node *root = NULL; //корень дерева

//-------------------------------------------------
//п/п для расчета времени выполнения
//-------------------------------------------------
#define Start(perf) QueryPerformanceCounter(&perf.start)
#define Stop(perf) QueryPerformanceCounter(&perf.stop)

bool QueryPerfCounter(performance * perf)
{
 return (0 != QueryPerformanceFrequency(&perf->frequency));
}

double Duration(performance * perf)
{
 return (((double)(perf->stop.QuadPart - perf->start.QuadPart) * 1.0e6 / 
  (double) perf->frequency.QuadPart));
}

//-------------------------------------------------
//п/п работы с деревом
//-------------------------------------------------

//поиск узла с указанным ключом в дереве, начиная с указанного
Node * TreeSearch(Node * node, int iKey)
{
 // Если узел равен NULL, то нечего в нем искать. Так же и возвращаем. 
 // Это нужно для поиска по несуществующим потомкам
 if (node == NULL)
  return node; 
 
 // Если нашли, то возвращаем указатель на найденный узел.
 if (node->key == iKey)
  return node;
 
 // Если ключ найденного узла больше того, который мы ищем
 if (node->key > iKey)
  // То искать в левом поддереве
  return TreeSearch(node->left, iKey);
 else 
  // Иначе в правом поддереве
  return TreeSearch(node->right, iKey);
}

//поиск узла с минимальным ключом
//т.к. дерево двоичное, то достаточно пройти до конца по левым веткам
Node * TreeMinimum(Node * node)
{
 while (node->left)  // Пока есть левый потомок
  node = node->left; // Перейти к нему
 return node;
}

//поиск узла с максимальным ключом
//т.к. дерево двоичное, то достаточно пройти до конца по правым веткам
Node * TreeMaximum(Node * node)
{
 while (node->right)  // Пока есть правый потомок
  node = node->right; // Перейти к нему
 return node;
}

//поиск очередного узла при поперечном обходе (по возрастанию ключей)
Node * TreeNext(Node * node)
{
 Node *nodeParent;

 // Если правое поддерево не пусто, то возвратить 
 // узел с минимальным значением ключа из правого поддерева
 if (node->right)
  return TreeMinimum(node->right);
  
 nodeParent = node->parent;

 // Перебирать родителей, пока не найден узел, 
 // являющаяся левым потомком своего родителя 
 // или пока не закончатся родители.
 while (nodeParent && (node == nodeParent->right))
 {
  node = nodeParent;
  nodeParent = nodeParent->parent;
 }
 
 // Возвратить родителя узла, являющегося левым потомком своего родителя
 return nodeParent;
}

Node * CreateNode(int iKey, char * sInfo)
{
 Node * node = new Node;

 //обнулим пока пустые указатели
 node->left = NULL;
 node->right = NULL;
 node->next = NULL;
 node->parent = NULL;

 //заполняем поля
 node->key = iKey;      //ключ
 node->str = new char[strlen(sInfo)+1]; //Info
 strcpy(node->str, sInfo);
 node->next = node;
 return node;
}

//вставка узла с указанным ключом и данными
void NodeInsert(int iKey, char * sInfo)
{
 Node *nodeParent = NULL;  //родитель текущего узла
 Node *node = root;   //некущий узел
 Node *nodeNew;    //новый узел
 Node *nodeRing;
 int  iRing = 0;
  
 nodeNew = CreateNode(iKey, sInfo); //создаем новый узел
 // Пока ещё есть узлы, которые надо просмотреть, 
 // то есть пока мы не добрались до “листочков” дерева
 while (node)
 {
  nodeParent = node;   //текущий узел для потомков является родителем
  // Выбираем узел, в зависимости от того,
  // меньше или больше вставляемый ключ относительно текущего узла
  if (iKey < node->key)
   node = node->left;
  else if (iKey > node->key)
   node = node->right;
  //если равно, то добавляем в конец кольца
  else
  {
   if (iRing == 0)
   {
    for (nodeRing=node->next; nodeRing->next!=node; nodeRing=nodeRing->next);
    nodeRing->next = nodeNew;
    nodeNew->next = node;
    iRing = 1;
   }
   if (NULL == node->left)
   {
    iRing = 2;
    node = node->left;
   }
   else
   {
    iRing = 3;
    node = node->right;
   }
  }
 }
            //добавляем узел в дерево
 nodeNew->parent = nodeParent;    //родитель

 if (nodeParent == NULL)  //если в дереве ещё нет узлов
  root = nodeNew;   //то запомним, как корень
 else
 {
  // Если ключ узла, который мы хотим вставить, 
  // меньше ключа узла, потомком которого должна стать 
  // вставляемый узел
  if ((iRing == 2) || (iKey < nodeParent->key))
   nodeParent->left = nodeNew; //то добавить в дерево как левого потомка
  else
   nodeParent->right = nodeNew;//иначе добавить в дерево как правого потомка
 }
}

//освободить память узла
void FreeTree(Node * node)
{
 if (node)     //если он есть, конечно
 {
  delete [] node->str; //память поля инфо
  FreeTree(node->left); //левого потомка
  FreeTree(node->right); //правого потомка
  delete node;   //память самого узла
 }
}

void ShiftRing(Node ** node)
{
 Node *nodeNext, *nodePrev, *nodePrevPrev;
 char *str;

 if ((*node)->next != (*node)) //признак отсутствия кольца - ссылка на себя
 {
  str = (*node)->str; //сохраним поле info удаляемого поля (удалим потом)
  //перепишем поля info узлов кольца на уровень выше, не меняя структуры дерева
  //пока не дойдем до коца кольца
  for (nodePrev=*node,nodeNext=(*node)->next; nodeNext!=(*node); 
   nodeNext=nodeNext->next)
  {
   nodePrev->str = nodeNext->str; //сдвигаем поле info по уздам кольца
   nodePrevPrev = nodePrev;  //сохраним адрес предпоследнего узла 
           //(он станет последним)
   nodePrev = nodeNext;   //для следующего шага
  }
  //nodePrev - адрес последнего (который мы удалим) узла в кольце
  //сохраним info в последнем узле кольца, чтобы удалить вместе с узлом
  nodePrev->str = str;
  //закрываем кольцо ссылкой на начало у предпоследнего узла
  nodePrevPrev->next = *node;
  *node = nodePrev;     //последний узел кольца удаляем
 }
}

//Удаление узла по ключу
//Необходимо сохранить свойство упорядоченности ДДП. 
//При удалении возможны три случая: 
//1) у удаляемого узла нет потомков, 
//2) у удаляемого узла есть один потомок и 
//3) у удаляемого узла два потомка. 
//Если потомков нет, то узел можно просто удалить. 
//Если потомок один, то удаляемый узел можно “вырезать”, 
//указав его родителю в качестве потомка единственного 
//имеющегося потомка удаляемого узла. 
//Если же потомков два, требуются дополнительные действия. 
//Нужно найти следующий за удаляемым (по порядку ключей) узлом, 
//скопировать его содержимое (ключ и данные) в удаляемый узел 
//и удалить найденный узел (у него не будет левого потомка). 
//
//при наличии кольца удаляем "самого старого", т.е. того,
//который основной (в дереве). Заместо него ставим первого в кольце
bool NodeDelete(int iKey)
{
 Node *del, *nodeNext;
 Node *node = TreeSearch(root, iKey); //ищем узел с указанным ключом

 if (node)  //проверим, есть ли такой
 {
  //проверим, есть ли кольцо
  ShiftRing(&node);

  //удаляем узел
  
  // Если потомков не более одного
  if ((node->left == NULL) || (node->right == NULL))
   del = node;    // физически удаляем текущий узел
  else
  {
   del = TreeNext(node); // Иначе следующий
   ShiftRing(&del);
  }
  
  if (del->left)    // Пытаемся найти хоть одного потомка
   nodeNext = del->left;
  else
   nodeNext = del->right;
  
  // Если есть, родителем потомка делаем родителя 
  // удаляемого узла
  if (nodeNext)
   nodeNext->parent = del->parent;
  
  // Если удаляем корень дерева, надо указать новый корень дерева
  if (del->parent == NULL)
   root = nodeNext;
  else
  {
   // Указываем родителю удаляемого узла в качестве потомка 
   // потомок удаляемого узла
   if (del->parent->left == del)
    del->parent->left = nodeNext;
   else
    del->parent->right = nodeNext;
  }

  if (del != node)   //удаляемый узел с двумя потомками
  {
   if (node->right && (node->right->key == del->key))
   {
    nodeNext = node->right;
    node->next = nodeNext->next;
    for (; nodeNext->next!=node->next; nodeNext=nodeNext->next);
    nodeNext->next = node;
   }
   else if (node->left && (node->left->key == del->key))
   {
    nodeNext = node->left;
    node->next = nodeNext->next;
    for (; nodeNext->next!=node->next; nodeNext=nodeNext->next);
    nodeNext->next = node;
   }
   delete [] node->str; //освободим память под Info
   node->key = del->key; //скопировать ключ
   node->str = del->str; //Info со следующего узла
  }
  else      //с одним или ни одного потомка
   delete [] del->str;  //освободим память под Info
  delete del;     //освободим память узла
  return 1;     //удалили!
 }
 return 0;      //ключ не найден
}
//----------------------------------------
//подпрограммы, вызываемые из меню
//----------------------------------------

int GetKey(void)     //ввод ключа
{
 int  i, iLen, iKey;
 char sText[256];    //буфер, чтобы забрать все лишнее

 printf("\nEnter key: ");  //приглашение
 while(1)      //бесконечный цикл, пока не получим ключ
 {
  gets(sText);    //введем строку
  iLen = strlen(sText);  //длина
  iKey = 1;     //флаг корректности
  for (i=0; i<iLen; i++)  //проверим на цифры
   if (0 == isdigit(sText[i]))
   {
    iKey = 0;   //увы, есть нецифры
    break;
   }
  if (iKey && iLen)   //цифры и введена строка
  {
   sscanf(sText, "%d", &iKey); //преобразовываем
   break;
  }
  else
   printf("Reenter key: "); //повторить ввод
 }
 return iKey;     //введенный ключ
}

//добавление узла 
void AddKey(void)
{
 int  iKey;
 char sInfo[256];

 //запросим ключ
 iKey = GetKey();

 //и Info
 printf("Enter info: ");
 do
 {
  gets(sInfo);
 }while(0==sInfo[0]);   //строка должна быть непустой!
 
 NodeInsert(iKey, sInfo);  //заносим в дерево
 printf("Node added");
}

//удаление узла
void DeleteKey(void)
{
 int  iKey;

 if (root)      //проверим на существование дерева
 {
  iKey = GetKey();

  if (NodeDelete(iKey))  //удаляем
   printf("Node deleted");
  else
   printf("Key not found");
 }
 else
  printf ("\nNo tree");
}

//вывод содержимого одного узла
void PrintNode(Node * node)
{
 //ключ и Info основного узла
 printf("Key = %d, Info = %s", node->key, node->str);
}

//поиск ключа в дереве
void SearchKey(void)
{
 int  iKey;
 Node *node;

 if (root)      //проверим на существование дерева
 {
  iKey = GetKey();   //введем ключ
 
  node = TreeSearch(root, iKey); //ищем ключ
  if (node)
   PrintNode(node);  //выводим ключ и Info
  else
   printf("Key not found");
 }
 else
  printf ("\nNo tree");
}

//поиск узла наиболее отличающегося по значению к заданному ключу
//т.к. имеем бинарное дерево, то достаточно проверить
//только самый левый и самый правый узлы
void SearchFarKey(void)
{
 int  iKey, iMax;
 Node *nodeMin, *nodeMax;

 if (root)      //проверим на существование дерева
 {
  iKey = GetKey();
  
  nodeMin = TreeMinimum(root);//найдем самого левого, он же минимальный
  iMax = abs(nodeMin->key - iKey); //расстояние от введенного ключа
  nodeMax = TreeMaximum(root);//найдем самого правого, он же максимальный

  if (iMax > abs(nodeMax->key - iKey)) //сравним
   PrintNode(nodeMin);  //минимальный дальше
  else
   PrintNode(nodeMax);  //максимальный дальше
 }
 else
  printf ("\nNo tree");
}
//вывод в порядке ключей
//идем от минимального до максимального
/*
void PrintSequential(void)
{
 Node *node;

 if (root)      //проверим на существование дерева
 {
  for(node=TreeMinimum(root);node;node=TreeNext(node))
  {
   printf("\n");
   PrintNode(node);  //выводим
  }
 }
 else
  printf ("\nNo tree");
}
*/

void Pr(Node * node)
{
 if (node)
 {
  Pr(node->left);    //обойти левое поддерево
  printf("\n");
  PrintNode(node);   //выводим
  Pr(node->right);   //обойти правое поддерево
 }
}

void PrintSequential(void)   //вывод в порядке ключей, используя
{         // рекурсивную п/п Pr
 if (root)      //проверим на существование дерева
  Pr(root);
 else
  printf ("\nNo tree");  //пустое дерево
}

//формирование и вывод строки при выводе дерева в виде дерева
//параметры: заполненная структура OutTree и количество значений
void PrintLine(OutTree * ot, int count)
{
 char line[84];    //буфер для вывода (84, чтобы было кратно 4)
 char sNum[16];    //буфер для преобразования числа в строку
 int  i, j, k;

 for (i=0; i<80; i++)
  line[i] = ' ';    //опробелим 80 позиций
 line[80] = 0;     //закроем строку
 for (i=0; i<count; i++)   //по всем выводимым значаениям
 {
  //k - позиция в строке, начиная с которой будем выводить число
  //для уменьшения ошибок округления считается как вещественное (80.),
  //затем округляется до целого
  k = (int)((80./(1<<(ot[i].level+1))) * ((ot[i].offset<<1)+1) - 1);
  //сформируем строку с ключом и Info
  sprintf(sNum,"%d(%s)", ot[i].node->key, ot[i].node->str);
  //скопируем в нужное место
  for(j=0; sNum[j] && (k<80); j++,k++)
   line[k] = sNum[j];
 }
 //выведем
 printf("\n");
 printf(line);
}

//вывод дерева в виде дерева
//испольуюся два массива и два счетчика:
//один набор используется, как исходный, второй - результат,
//потом наоборот. Переключаются переменной k
void PrintTree(void)
{
 OutTree ot[2][20];    //массив струтур для кодирования данных
 int  count[2];    //количество
 int  i, j;
 int  k = 0;     //начинаем с массива 0

 if (root)      //проверим на существование дерева
 {
  //сформируем одну запись для корня
  ot[k][0].node = root;  //узел
  ot[k][0].level = 0;   //уровень
  ot[k][0].offset = 0;  //поле
  count[k]=1;     //количество

  while (1)     //бесконечный цикл
  {
   PrintLine(ot[k],count[k]); //выведем
 
   //формируем информацию для следующей строки
   for (j=i=0; i<count[k]; i++)
   {
    //k - индекс предыдущего массива
    //k^1 - индекс формируемого массива
    //если есть левый потомок
    if (ot[k][i].node->left)
    {
     //адрес потомка
     ot[k^1][j].node = ot[k][i].node->left;
     //уровень на 1 больше
     ot[k^1][j].level = ot[k][i].level + 1;
     //поле в 2 раза больше
     ot[k^1][j++].offset = ot[k][i].offset << 1;
    }
    //если есть правый потомок
    if (ot[k][i].node->right)
    {
     //адрес потомка
     ot[k^1][j].node = ot[k][i].node->right;
     //уровень на 1 больше
     ot[k^1][j].level = ot[k][i].level + 1;
     //поле = * 2 + 1
     ot[k^1][j++].offset = (ot[k][i].offset << 1) + 1;
    }
   }
   k ^= 1;     //меняем индекс
   count[k] = j;   //сохраняем количество
   if (j==0)    //если ничего нет, то выход
    break;
  }
 }
 else
  printf ("\nNo tree");
}

//ввод данных из текстового файла
//Ключ 1
//Информация 1
//Ключ 2
//......
void GetTextFile(void)
{
 char filename[256];
 char line[256];
 int  key;

 printf ("\nInput file name: "); //запрашиваем имя файла
 gets(filename);
 if (filename[0])    //если имя введено
 {
  FILE* file = fopen (filename, "r"); //открываем
 
  if (file)     //если открыто
  {
   FreeTree(root);   //освобождаем старое дерево
   root = NULL;   //обнуляем корень
   while(1)    //бесконечный цикл
   {
    if (fgets(line, 256, file)) //читаем строку с ключом
    {
     key = atoi(line);//преобразуем в число
     if (fgets(line, 256, file)) //читаем строку с Info
     {
      if (line[strlen(line)-1] == 0x0a)
       line[strlen(line)-1] = 0;//удаляем последний код 0ah
      NodeInsert(key, line); //добавляем узел
     }
     else
      break;
    }
    else
     break;
   }
   fclose (file);   //закрываем файл
   printf ("Success.");
  }
  else
   printf ("Error. File not found.");
 }
 else
  printf("Reenter file name.");
}

int Menu () //вывод меню
{
 int  c;
 
 printf("1. Add new key.\n2. Delete key.\n");
 printf("3. Search any key\n4. Search far key\n");
 printf("5. Print on sequential order.\n6. Print tree structure.\n");
 printf("7. Get tree from file.\n8. Reorganization.\n9. Timing.\n0. Exit.\n");
 printf("Enter menu item: ");
 
 c = getch();     //читаем код
 putch(c);      //выведем
 
 while (c<'0' || c>'9')   //проверим на допустимость
 {
  printf("\nUncorrect! Reenter: ");
  c = getch();
  putch(c);
 }
 return c-'0';
}

//рекурентная подпрограмма формирования сбалансированного дерева
//параметры: адрес массива узлов, индексы начала и конца
void NodeInsertNew(Node ** NodeArr, int iBegin, int iEnd)
{
 int  iMiddle = (iBegin + iEnd)/2; //середина
 Node *node = NodeArr[iMiddle];  //узел середины участка

 NodeInsert(node->key, node->str);  //заносим в дерево

 //отработаем левый участок
 if (iBegin != iMiddle)
  NodeInsertNew(NodeArr, iBegin, iMiddle);
 //правый участок
 if (iEnd > iMiddle+1)
  NodeInsertNew(NodeArr, iMiddle+1, iEnd);
}

//балансировка дерева
void Reorganisation(void)
{
 Node *node;
 Node *rootOld = root;  //корень старого дерева
 Node **nodeArr;    //массив адресов узлов
 int  i, count;

 if (root)      //проверим на существование дерева
 {
  //посчитаем количество
  for(count=0,node=TreeMinimum(root);node;node=TreeNext(node))
   count++;
  //запросим память под массив
  nodeArr = new Node* [count];
  //сохраним, для удобства, адреса узлов м обычном массиве
  for(i=0,node=TreeMinimum(root);node;node=TreeNext(node))
   nodeArr[i++] = node;

  root = NULL;    //строим новое дерево
  
  NodeInsertNew(nodeArr, 0, count); //извлекаем данные из массива и создаем новое дерево

  FreeTree(rootOld);     //освободим память
  printf ("\nComplete.");
  delete [] nodeArr;
 }
 else
  printf ("\nNo tree");
}

void SortIdx(int * idx, int iMax)
{
 int  i, j, k;
 int  *old = new int[iMax];

 for (i=0; i<iMax; i++)
  old[i] = 0;
 for (i=0; i<iMax; i++)
 {
  j = rand()%iMax;
  if (old[j] == 0)
  {
   old[j] = 1;
   idx[i] = j;
  }
  else
  {
   if (rand()&1 == 0)
   {
    for (k=1; j>=k; k++)
    {
     if (old[j-k]==0)
     {
      old[j-k] = 1;
      idx[i] = j-k;
      break;
     }
    }
    if (j < k)
    {
     for (k=1; j+k<iMax; k++)
     {
      if (old[j+k]==0)
      {
       old[j+k] = 1;
       idx[i] = j+k;
       break;
      }
     }
    }    
   }
   else
   {
    for (k=1; j+k<iMax; k++)
    {
     if (old[j+k]==0)
     {
      old[j+k] = 1;
      idx[i] = j+k;
      break;
     }
    }
    if (j+k >= iMax)
    {
     for (k=1; j>=k; k++)
     {
      if (old[j-k]==0)
      {
       old[j-k] = 1;
       idx[i] = j-k;
       break;
      }
     }
    }
   }
  }
 }
 delete [] old;
}

void SaveNodes(key_perfomance * kp, int iMax)
{
 HANDLE  hFile ;
 DWORD  dwLen ;
 int   i;
 char  sLine[80];

 sprintf(sLine, "Nodes%d.txt", iMax);
 hFile = CreateFile(sLine, GENERIC_WRITE, 0, NULL, OPEN_ALWAYS, 0, NULL) ;
 if (hFile != INVALID_HANDLE_VALUE)
 {
  for (i=0; i<iMax; i++)
  {
   sprintf(sLine, "%d\n", kp[i].key);
   WriteFile(hFile, sLine, strlen(sLine), &dwLen, NULL) ;
   sprintf(sLine, "%s\n", kp[i].str);
   WriteFile(hFile, sLine, strlen(sLine), &dwLen, NULL) ;
  }
  CloseHandle(hFile) ;
 }
}

void SaveIdx(int * idx, int iMax)
{
 HANDLE  hFile ;
 DWORD  dwLen ;
 int   i;
 char  sLine[80];

 sprintf(sLine, "Idx%d.txt", iMax);
 hFile = CreateFile(sLine, GENERIC_WRITE, 0, NULL, OPEN_ALWAYS, 0, NULL) ;
 if (hFile != INVALID_HANDLE_VALUE)
 {
  for (i=0; i<iMax; i++)
  {
   sprintf(sLine, "%d\r\n", idx[i]);
   WriteFile(hFile, sLine, strlen(sLine), &dwLen, NULL) ;
  }
  CloseHandle(hFile) ;
 }
}

void Timing(void)
{
 int    i, k, iMax, iMax2;
 performance  perf;
 double   fTotal, fMin, fMax;
 key_perfomance *kp_insert;
 key_perfomance *kp_search;
 int    *idx;

 if (QueryPerfCounter(&perf))
 {
  FreeTree(root);     //освободим память
  root = NULL;
  kp_insert = new key_perfomance[1000000];
  kp_search = new key_perfomance[5000];

  for (i=0; i<1000000; i++)
  {
   kp_insert[i].key = rand()%100000;
   sprintf(kp_insert[i].str,"str%d",i);
  }
  for (i=0; i<5000; i++)
   kp_search[i].key = rand()%100000;
  
  for (iMax = 0; iMax<20; iMax++)
  {
   iMax2 = (iMax+1)*50000;
   printf ("\n\nTiming %d items...", iMax2);
   
//   printf ("\nSave Nodes to file ""Nodes""%d.txt...",iMax);
//   SaveNodes(kp, iMax);

   printf ("\nInserting 50000 nodes...");
   fMin = 1000000.; fTotal = fMax = 0;
   for (i=0; i<50000; i++)
   {
    k = iMax*50000 + i;
    Start(perf);
    NodeInsert(kp_insert[k].key, kp_insert[k].str); //добавляем узел
    Stop(perf);
    kp_insert[k].mks = Duration(&perf);
    fTotal += kp_insert[k].mks;
    if (kp_insert[k].mks < fMin)
     fMin = kp_insert[k].mks;
    if (kp_insert[k].mks > fMax)
     fMax = kp_insert[k].mks;
   }
   printf ("\nTotal: %-.0f mks, min: %-.0f mks, max: %-.0f mks, average: %-.0f mks.", 
    fTotal, fMin, fMax, fTotal/50000);
   
   printf ("\nSearching 5000 nodes...");
   fMin = 1000000.; fTotal = fMax = 0;
   for (i=0; i<5000; i++)
   {
    Start(perf);
    TreeSearch(root, kp_search[i].key);  //ищем узел
    Stop(perf);
    kp_search[i].mks = Duration(&perf);
    fTotal += kp_search[i].mks; 
    if (kp_search[i].mks < fMin)
     fMin = kp_search[i].mks;
    if (kp_search[i].mks > fMax)
     fMax = kp_search[i].mks;
   }
   printf ("\nTotal: %-.0f mks, min: %-.0f mks, max: %-.0f mks, average: %-.0f mks.", 
    fTotal, fMin, fMax, fTotal/5000);
   
   idx = new int[iMax2];
   SortIdx(idx, iMax2);
//   SaveIdx(idx, iMax);

   printf ("\nDeleting 5000 nodes...");
    fMin = 1000000.; fTotal = fMax = 0;
   for (i=0; i<5000; i++)
   {
    Start(perf);
    NodeDelete(kp_insert[idx[i]].key);
    Stop(perf);
    kp_insert[idx[i]].mks = Duration(&perf);
    fTotal += kp_insert[idx[i]].mks; 
    if (kp_insert[i].mks < fMin)
     fMin = kp_insert[i].mks;
    if (kp_insert[i].mks > fMax)
     fMax = kp_insert[i].mks;
   }
   printf ("\nTotal: %-.0f mks, min: %-.0f mks, max: %-.0f mks, average: %-.0f mks.", 
    fTotal, fMin, fMax, fTotal/5000);
   
   FreeTree(root);     //освободим память
   root = NULL;
   for (i=0; i<iMax2; i++)
    NodeInsert(kp_insert[i].key, kp_insert[i].str); //добавляем узел

   delete [] idx;
  }
  delete [] kp_search;
  delete [] kp_insert;
 }
 else
  printf ("\nNo perfomence");
}

int main(int argc, char* argv[])
{
 //инициализация последовательности псевдослучайных чисел
 srand( (unsigned)time( NULL ) );

 while (1)
 {
  system ("cls");    //очистка экрана
  switch (Menu())    //вывод меню и получение кода выбора
  { 
   case 1: 
    AddKey();   //добавление узла с ключом
    break;
   case 2: 
    DeleteKey();  //удаление узла с ключом
    break;
   case 3: 
    SearchKey();  //поиск ключа
    break;
   case 4: 
    SearchFarKey();  //поиск самого дальнего ключа
    break;
   case 5: 
    PrintSequential(); //последовательный вывод
    break;
   case 6: 
    PrintTree();  //вывод в виде дерева
    break;
   case 7: 
    GetTextFile();  //ввод из некстового файла
    break;
   case 8:
    Reorganisation(); //балансировка дерева
    break;
   case 9: 
    Timing();   //анализ работы дерева
    break;
   case 0: 
    printf("\n");  //выход
    return 0;
  }
  printf ("\nPress any key to continue.");
  getch ();
 }
 FreeTree(root);     //освободим память
 return 0;
}