AVL и Red-Black Tree

//Работа с АВЛ-деревом
//Демонстрационная программа     (С) Clgn, 18.04-26.02.2010
//Поддерживаются:
// -  произвольная последовательность на множестве с использованием массива ссылок
// -  генерация случайного АВЛ-дерева
// -  эффективные алгоритмы FIND, SEQ, AND, XOR, OR, MERGE, SPLIT,
//                          MUL, CONCAT, EXCL, ERASE, CHANGE, SUBST
//                          COPY, EQ
 
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
 
const int NN = 200; //Предельная мощность по умолчанию
const int N1 = 10, N2 = 7; //Мощности для эксперимента
const int FIRSTROW = 1, SECONDROW = 13, FIRSTCOL = 40,
      OFFSET = 40, MAXDEPTH = 5; //Константы управления выводом на экран
char bb[] = "-o+";
class Stack;
void Error(int); // Обработка ошибок
 
class A {   // Узел АВЛ-дерева
    int key;    //Значение (вес в узле)
    A * link[2];    //Левое и правое поддерево
    int b, k;       //Баланс: -1, 0, +1; кратность узла
    A **bkwd;       //Обратная ссылка на массив указателей
    void Erase();   //Метод: Рекурсивное удаление узла
public:
    void Display(int, int, int, A**); //Вывод узла на экран
    int El() {return key;}; //Доступ к значению веса узла (inline по умолчанию!)
    A(int k);       //Конструктор узла
    A(A *&);    //Конструктор копирования для узла
    ~A(){};
friend class AVL;
    };
 
class AVL {
    A * root, * cp;
    int h, n0, n, N;    //Высота, текущая, максимальнвя мощность
    int current;
    A ** ptrs;
 
    A * Build(int, int, int &);     //Формирование дерева по отрезку массива ссылок с возвратом высоты
    void BuildSeq();                //Образование последовательности по кратностям
    void OP(AVL *&, int mode = 0, int pos = 0);  //Двуместная операция
public:                                 //   (0 - AND, 1 - SUB, 2 - XOR, 4 - OR, 5 - MERGE)
    int * Part(int, int);       //Извлечение части последовательности
    int Step (A *&, Stack &, int mode = 0); //Один шаг внутреннего обхода дерева
    void Display(int); //Вывод дерева на экран, начиная с указанного ряда
 
    int IN(int e) {return (FIND(e) >= 0); };
    int INSERT(int);    //Вставка нового узла (с присоединением к концу п-ти)
    int REMOVE(int);        //Удаление узла из дерева
    void AND(AVL *& T) { OP(T); }
    void SUB(AVL *& T) { OP(T, 1); }
    void XOR(AVL *& T) { OP(T, 2); }
    void OR(AVL *& T) { OP(T, 3); }
    void MERGE(AVL *& T) { OP(T, 4); }
    AVL * SPLIT(int);
    int FIND(int);
    int SEQ(int p) { if (p < n) {
               current = p;
               return ptrs[p]->key;
             }
             else return -1; };
    void MUL(int);
    void CONCAT(AVL *& T) { OP(T, 5); }
    void EXCL(AVL *& T);
    void ERASE(int, int);
    void CHANGE(AVL *& T, int p) { ERASE(p, p+T->n); OP(T, 5, p + 1); }
    void SUBST(AVL *& T, int p) { OP(T, 5, p + 1); }
    AVL * COPY();               // = COPY
    int operator == (AVL &);   // = EQ
    void PUSH(int e){ INSERT(e); }
    int POP(){ if(n) { int e = ptrs[n-1]->key; REMOVE(e); current = n-1; return e; }
           else return -1;
        }
    int GET(){ if(n) { int e = ptrs[0]->key; REMOVE(e); current = 0; return e; }
           else return -1;
        }
    int CURRENT() {return ptrs[current]->key; }
    int NEXT() { if (n) { if(current++ >= n) current = 0;
                    return ptrs[current]->key; }
                 else return -1;
               }
    int PREV() { if(n) { if(--current < 0) current = n-1; return ptrs[current]->key; }
                 else return -1;
               }
    AVL(){ root = cp = 0; h = n0 = n = 0; current = -1; N = NN;
           ptrs = new A* [N]; };        //Конструктор пустого дерева
    AVL(int);       //Конструктор произвольного дерева заданной мощности
    AVL(int *&);    //Конструктор дерева из заданной последовательности
    ~AVL();
    };
 
class Els {     //Элемент стека
       A * p;
       int a;
       Els * pr;
friend class Stack;
public:
       Els(){};
       Els(A * pp, int e, Els * ptr)
        {p = pp; a = e; pr = ptr;};
       ~Els(){};
       };
 
class Stack {
       Els * stptr; // Указатель стека
public:
       Stack(){ stptr = 0; };
       Stack(A * pp, int e){ stptr = new Els(pp, e, 0); };
       void Push(A *, int);
       int Pop(A *&, int &);
};
 
int Stack :: Pop(A * & pp, int & aa)    //Поднять из стека, вернуть "стек не пуст"
{
   if (stptr) {
      Els * s = stptr;
      pp = s->p;
      aa = s->a;
      stptr = s->pr;
      delete s;
      return 1;
   }
   else return 0;
}
 
void Stack :: Push(A * pp, int aa)  //Опустить в стек
{
   Els * s = new Els; //ELs(pp, aa); //, stptr);
   s->p = pp;
   s->a = aa;
   s->pr = stptr;
   stptr = s;
}
 
A :: A(int e)   //Конструктор нового узла с весом "e"
{
   key = e;
   link[0] = 0;
   link[1] = 0;
   b = 0;
   k = 1;
}
 
A :: A(A *& u) //Конструктор "копирования"
{
   key = u->key;
   link[0] = link[1] = 0;
   b = 0;
   k = u->k;
   bkwd = 0;
}
 
void A :: Erase()
{
   if (link[0]) link[0]->Erase();
   if (link[1]) link[1]->Erase();
   delete this;
}
 
AVL :: ~AVL()
{
   if (root) root->Erase();
   if (n) delete [] ptrs;
}
 
AVL :: AVL(int k) //Конструктор - генератор дерева мощности "k"
{
   N = NN;
   int c, d = NN/k, e;
   n0 = 0;
   ptrs = new A* [N];
   ptrs[0] = new A(c = random(d)+1);  //Первый элемент
   for (int i = 1; i < k; i++) {
       e = random(d);  //Случайная добавка
       if (e > 1) {
      c += e;
      ptrs[++n0] = new A(c); //Новый элемент множества
       }
       else ptrs[n0]->k++;  //Новый кратный
   }
   n0++;
   root = Build(0, n0, h);
   BuildSeq();
   current = 0;
}
 
AVL :: AVL(int * &keys) //Конструктор дерева из последовательности
{  int i, j, c,
     * seql = new int[NN];
   A * s0;
   for (n = 0; keys[n]; n++)
      seql[n] = keys[n];  //Копирование с подсчётом мощности
   if (n) {
      for (i = n;  i >= 0; i--)
     for (j = 1; j < i; j++)
        if (keys[j - 1] > keys[j]) {
           c = keys[j];
           keys[j] = keys[j - 1];
           keys[j - 1] = c;
        }
      N = n;
      ptrs = new A*[N];
      ptrs[0] = new A(keys[0]);
      for (j = i = 1; i < n; i++)   //Создание комплекта узлов...
     if (keys[i - 1] != keys[i])  // ...пропуск совпадений
        ptrs[j++] = new A(keys[i]);
      n0 = j;
      root = Build(0, n0, h);  //Формирование дерева
      for (i = 0; i < n; i++) { //Восстановление массива ссылок
     s0 = root;
     while (s0 && (s0->key != seql[i]))
        s0 = s0->link[s0->key < seql[i]];
     if (!s0)
        Error(2);
     s0->k = 0;
     ptrs[i] = s0;
      }
      for (i = n - 1; i >= 0; i--) { //Подсчёт кратностей
     ptrs[i]->k++;
     ptrs[i]->bkwd = &ptrs[i];
      }
   }
   else { root = 0;  ptrs = 0; N = n0 = 0; }
   delete []keys;
   delete []seql;
   current = 0;
}
 
AVL * AVL :: COPY() //Конструктор копирования
{  AVL * T1 = new AVL;
   A *s0 = 0;
   Stack St0;
   int p0 = Step(s0, St0);
   while (p0) {
      T1->ptrs[T1->n0++] = new A(s0);
      p0 = Step(s0, St0);
   }
   T1->root = T1->Build(0, n0, h);
   T1->BuildSeq();
   return T1;
}
 
int AVL :: operator == (AVL & T) //Сравнение множеств
{
   A * s0 = 0, *s1 = 0;
   Stack St0, St1;
   int p = 1, p0 = Step(s0, St0), p1 = T.Step(s1, St1);
   while (p && p0 && p1) {
      p *= s0->key == s1->key;
      p0 = Step(s0, St0);
      p1 = T.Step(s1, St1);
   }
   return p;
}
 
A * AVL :: Build(int a, int b, int &h2) //Сборка АВЛ-дерева из массива узлов
{
   h2 = 0;
   if (b <= a) return 0;
   int h0 = 0, h1 = 0, c = (a + b) /2;
   A * s = ptrs[c];
   s->bkwd = &ptrs[c];
   s->link[0] = Build(a, c, h0);
   s->link[1] = Build(c+1, b, h1);
   s->b = h1 - h0;
   h2 = 1 + (h0 > h1? h0 : h1);
   return s;
}
 
int * AVL :: Part(int p1, int p2) //Извлечение подпоследовательности
{  if (p2 > n) p2 = n;
   if (p1 >= p2) p1 = p2 - 1;
   int i, j = 0, * seq = new int[p2 - p1 + 1];
   for (i = p1; i < p2; i++)
      seq[j++] = ptrs[i]->key;
   seq[j] = 0;
   return seq;
}
 
void AVL :: BuildSeq() //Восстановление последовательности по кратностям
{
   int i, j;
   for (i = n = 0; i < n0; i++) n += ptrs[i]->k;  //Подсчёт полной мощности
   i = n0; j = n;
   while ((i > 0) && (i != j)) {
      --i; --j;
      ptrs[j] = ptrs[i];
      ptrs[j]->bkwd = &ptrs[j];     //Установка обратных ссылок
      for (int l = 1; l < ptrs[i]->k; l++)  { //Восстановление дубликатов
         ptrs[--j] = ptrs[i];
         ptrs[j]->bkwd = &ptrs[j];
      }
   }
}
 
void AVL :: OP(AVL *& T, int mode, int pos)    //Двуместная операция
{       //(0 - AND, 1 - SUB, 2 - XOR, 3 - OR, 4 - MERGE, 5 - CONCAT)
    // pos != 0 -> вместо сцепления - вставка с позиции 'pos - 1'
   int p = 0, p0, p1, q = 0;
   A ** pt = new A * [NN],       //Массив для узлов результата
     ** pq = new A * [n + T->n]; //Массив для лишних узлов
   A * s0 = 0, * s1 = 0;
   Stack St0, St1;
   p0 = Step(s0, St0);
   p1 = T->Step(s1, St1);
   while (p0 && p1) { //Отбор узлов для нового дерева, сброс ссылок на них
     if (s0->key == s1->key) {
     if (!mode || (mode > 2)) pt[p++] = s0;
     s0->k = (mode > 3)? s0->k + s1->k : 1; //MERGE -> счёт кратности
     pq[q++] = s1;    //Дубликат -> в список удаляемых
     *s1->bkwd = s0;  //Перестановка ссылки на сохранённый узел
     p0 = Step(s0, St0);
     p1 = T->Step(s1, St1);
      }
      else if (s0->key < s1->key) {
     if (mode) { pt[p++] = s0;
         if (mode < 4) s0->k = 1;
         }
     else pq[q++] = s0;  //Ненужный узел - в список удаляемых
     p0 = Step(s0, St0);
      }
      else {
     if (mode > 1) { pt[p++] = s1;
        if (mode < 4) s1->k = 1;
        }
     else pq[q++] = s1; //Ненужный узел - в список удаляемых
     p1 = T->Step(s1, St1);
      }
   };
   //Подбор "хвостов"
   while (p0) {
    if (mode) { //Не AND
       pt[p++] = s0;
       if (mode < 4) s0->k = 1; //Результат - множество: кратность = 1
       }
    else pq[q++] = s0;  //Ненужный узел - в список удаляемых
    p0 = Step(s0, St0);
   }
   while (p1) {
    if (mode > 1) { //Не AND и не SUB
       pt[p++] = s1;
       if (mode < 4) s1->k = 1; //Результат - множество: кратность = 1
    }
    else pq[q++] = s1; //Ненужный узел - в список удаляемых
    p1 = T->Step(s1, St1);
   }
 
   for (p0 = 0; p0 < q; p0++) delete pq[p0]; //Уничтожение лишних узлов
   if (mode == 5) { //CONCAT: сцепление массивов ссылок, р-т -> в pq[]
      if (pos > n + 1) pos = 0;
      int n1 = pos? pos - 1 : n; //Если вставка, копировать только до 'pos'
      for (q = 0; q < n1; q++)
         pq[q] = ptrs[q];
      current = q;
      for (p0 = 0; p0 < T->n; p0++)
         pq[q++] = T->ptrs[p0];
      if (pos) for (p0 = pos - 1; p0 < n; p0++) //Вставка: копировать остаток
         pq[q++] = ptrs[p0];
      n = q;
   }
   else {
     n = p; delete []pq; //Не CONCAT: уничтожение pq[]
   }
   T->root = 0; //Все узлы T использованы или уже удалены
   delete T;
   delete []ptrs;
   ptrs = pt;  //Переключение массива ссылок на результат; сброс link[]
   for (q = 0; q < p; q++) ptrs[q]->link[0] = ptrs[q]->link[1] = 0;
   root = Build(0, p, h); //Сборка нового дерева
   n0 = p;  //Установка мощности для множества
   if (mode == 4) BuildSeq(); //MERGE: обработка кратностей
   if (mode == 5) { //CONCAT: подмена массива ссылок
      delete []ptrs; //Уничтожение упорядоченного массива
      ptrs = pq;     //... подмена
      for (q = n - 1; q >= 0; q--) //Установка обратных ссылок
     ptrs[q]->bkwd = &ptrs[q];
   }
   else current = 0;
}
 
AVL * AVL :: SPLIT(int a) //Расцепление
{  A ** pt = new A * [n], //остающиеся узлы
     ** pq = new A * [n], //отделякмые узлы
      * s0 = 0; //текущий узел для внутреннего обхода
   Stack St0;   //стек для внутреннего обхода
   int i = 0,  j = 0, p0 = Step(s0, St0);
   while (p0) {     //обход в разделением узлов
      s0->k = 1;    //сброс кратностей
      if (s0->key < a) {
         pt[i] = s0;    //перенос узла в последовательность
     s0->bkwd = &pt[i++];  // установка обратной ссылки
 
      }
      else {
     pq[j] = s0;
     s0->bkwd = &pq[j++];
      }
      p0 = Step(s0, St0);
   } 
   delete []ptrs;   //подмена текущей последовательности
   ptrs = pt;
   n = n0 = i;      //фиксация мощности
   root = Build(0, i, h);   //воссоздание текущего дерева
 
   AVL * T2 = new AVL;  //Новое пустое дерево
   T2->n = T2->n0 = j;  //фиксация мощности
   T2->ptrs = pq;   //передача последовательности
   T2->root = T2->Build(0, j, T2->h);  //воссоздание второго дерева
   return T2;
}
 
void AVL :: EXCL(AVL *& T) //Исключить последовательность T, если она есть
{  
   int p = FIND(T->ptrs[0]->key),
       r = 1, i = p, j = 0;
   if (p >= 0) { //Проверка на вхождение последовательности T
      for (int l = 0; l < ptrs[p]->k; l++) {
     while (r && (j < T->n)) r *= (ptrs[i++]->key == T->ptrs[j++]->key);
     if (r) {
        ERASE(p, p + T->n); //T найдена, удаляем
        return;
     }
     p++;
     while (ptrs[p]->key != T->ptrs[0]->key) p++;
     r = 1;  i = p;  j = 0;
      }
   }
}
 
void AVL :: ERASE(int p1, int p2) //Укоротить (исключить часть от p1 до p2)
{
   if (p2 > n) p2 = n;
   if (p1 >= p2) return;
   int p0, q = 0, r;
   A ** pt = new A * [NN],  //Массив ссылок на узлы результата
     ** pq = new A * [n];   //Массив ссылок на удаляемые узлы
   A * s0 = 0;
   Stack St0;
   for (r = 0; r < n; r++)  //Отбор удаляемых узлов
      if ((p1 <= r) && (r < p2)) ptrs[r]->k--; //Уменьшение кратности
   r = 0;
   p0 = Step(s0, St0);
   while (p0) {  //Отбор оставляемых узлов
      if (s0->k) pt[r++] = s0; //Отбираются узлы с ненулевой кратностью
      else pq[q++] = s0;       //Кратность = 0 -> в удаляемые
      p0 = Step(s0, St0);
   }
   for (p0 = 0; p0 < q; p0++) delete pq[p0]; //Уничтожение лишних узлов
   delete []pq;
   pq = ptrs;  //Сохранение исходной последовательности
   ptrs = pt;  //Переключение массива ссылок на результат; сброс link[]
   for (q = 0; q < r; q++) ptrs[q]->link[0] = ptrs[q]->link[1] = 0;
   root = Build(0, r, h); //Сборка нового дерева
   delete []ptrs; //Уничтожение упорядоченного массива ссылок
   ptrs = pq;
   r = p1;
   for (q = p2; q < n; q++)
      ptrs[r++] = ptrs[q]; //Исключение части последовательности
   n = r;
   for (q = n - 1; q >= 0; q--) //Установка обратных ссылок
     ptrs[q]->bkwd = &ptrs[q];
   current = p1;
}
 
void AVL :: MUL (int m) //Размножить p раз
{  int p0;
   A * s0 = 0;
   Stack St0;
   if (n && (m*n > N)) { //Проверка корректности данных
      Error(1);
      m = N/n; }
   p0 = Step(s0, St0);
   while (p0) { //Корректировка кратностей
      s0->k *= m;
      p0 = Step(s0, St0);
   }
   for (p0 = 1; p0 < m; p0++) //Размножение ссылок
     for (int i = 0; i < n; i++) ptrs[p0*n+i] = ptrs[i];
   current = n;
   n *= m;
   }
 
void Error (int p)
{  char y;
   switch (p) {
   case 1: printf("\nMUL: Tree overflow"); break;
   case 2: printf("\nAVL(seql): Value not found! Exit?(Y)"); break;
   default: printf("\n Undetermined error");
   }
   y = getche();
   if (toupper(y) == 'Y') exit(1);
}
void AVL :: Display(int firstrow)
{
   if (firstrow == FIRSTROW)  //Вызов для главного дерева -> очистить экран
     clrscr();
   gotoxy(1, firstrow);
 
   cprintf("AVL-Tree(h=%2d n0=%2d n=%2d) ------->", h, n0, n);
   if (root) {
      root->Display(firstrow, FIRSTCOL, 1, ptrs);
      gotoxy(1, firstrow + MAXDEPTH + 2);
      for (int i=0; i<n; i++) {
     textcolor((i == current)? LIGHTRED : WHITE);
     cprintf("%4d", ptrs[i]->key);
      }
      textcolor(WHITE);
   }
   else cprintf("<Empty!>");
}
 
void A::Display(int rov, int col, int depth, A ** ptr) //Выдача узла (дерева в целом) на экран
{
   if(depth > MAXDEPTH) {cout << "..."; return; }
   gotoxy(col, rov);
   cout << key; // Вес в узле
   gotoxy(col, rov+1);
   cout << bb[b+1]; // Баланс
   gotoxy(col, rov+2);
   cout << k;
   gotoxy(col, rov+3);
   cout << (int)(bkwd-ptr);
   if (link[0]) link[0]->Display(rov+1, col-(OFFSET>>depth), depth+1, ptr);
   if (link[1]) link[1]->Display(rov+1, col+(OFFSET>>depth), depth+1, ptr);
}
 
int AVL :: FIND(int e)
{
    A *p = root;
    int cont = 1;
    if (root) {
       while (cont && (e != p->key)) {
          p = p->link[ e > p->key ];
          cont = (p != 0);
       }
       if (cont) { current = (int)(p->bkwd - ptrs);
      return current;
       }
    }
    return -1;
}
 
int AVL :: INSERT(int e)    //Метод: Вставка нового узла
{ A *t, *s, *p, *q, *r;
   int a, cont, d;
   //===== Инициализация =====
   t = 0;  current = n;
   if (root == 0) { // Дерево пусто
      ptrs[0] = root = new A(e); //Создать корень
      n0 = n = h = 1;       //...мощность и высота = 1
      root->bkwd = ptrs;
      return 2;         //...выход: "вставлено"
   }
   else {
      s = p = root;
      cont = 1;
      //===== Поиск места вставки =====
      while((e != p->key) && cont) {
     a = e > p->key? 1:0;
     q = p->link[a];
     if(q) { //Есть сын
        if(q->b) { t = p; d = a;
           s = q; } //запоминание узла с ненулевым балансом
        p = q; //Шаг вниз
        }
     else {
        ptrs[n] = p->link[a] = q = new A(e);  //Вставка
        q->bkwd = &ptrs[n++]; //...Обратная ссылка
        n0++; cont = 0; }
      }
      if (cont) {   // Элемент уже имеется, вставка дубликата
     ptrs[n] = p;
     n++; p->k++;
     return 1;
      }
      else { //Вставлен новый узел
     //===== Замена нулевых балансов на +1/-1
        r = p = s->link[e > s->key];
        while (p != q) {
           if (e < p->key) {
          if (p->b == 0) p->b = -1;
          p = p->link[0];
           }
          else { if (p->b == 0) p->b = +1;
          p = p->link[1];
           }
        }
     //===== Балансировка =====
        if (e < s->key) a = -1; //Левый или правый случай?
        else a = +1;
        if (s->b == 0) {    //s - это корень. Дерево подросло...
           h++;
        s->b = a;
     }
        else if (s->b == -a) s->b = 0;  //...сбалансировалось
        else {      // (s->b == a):... разбалансировалось
           if (r->b == a) { //Случай I: Однократный поворот
          p = r;
          s->link[(1+a)/2] = r->link[(1-a)/2];
          r->link[(1-a)/2] = s;
          s->b = r->b = 0;
           }
           else {       //Случай II: Двукратный поворот
          p = r->link[(1-a)/2];
          r->link[(1-a)/2] = p->link[(1+a)/2];
          p->link[(1+a)/2] = r;
          s->link[(1+a)/2] = p->link[(1-a)/2];
          p->link[(1-a)/2] = s;
          if (p->b) {
            if (p->b == a) { s->b = -a; r->b = 0; }
            else { s->b = 0; r->b = a; }
          p->b = 0;
          }
          else  s->b = r->b = 0;
        }
           if (t) t->link[d] = p; // Корректировка
           else root = p;         // внешней ссылки
        }
      }
      return 2; // Выход: "Вставлено"
   }
}
 
int AVL :: REMOVE(int e)    //Удаление узла с весом "e"
{  A *p, *q, *r;
   int i, a, cont, B[] = {-1, +1};
   Stack * St = new Stack; //Создание и очистка стека
 
   //===== Инициализация =====
   p = 0;
   a = 0;
   cont = ((q = root) != 0);
   //===== Поиск удаляемого элемента =====
   while(cont && (e != q->key)) {
      St->Push(p, a);   //Опускание в стек указателя на узел и направления спуска
      p = q;
      a = e > q->key;
      q = q->link[a];
      if(q == 0) cont = 0;  //Ссылка пуста -> закончить поиск, элемента нет
   }
   if (cont) {     // Элемент найден, удаляем
      n--;
      if (q->k > 1) { //Удаление дубликата
     q->k--;
     i = current = q->bkwd - ptrs;
     while (i < n) {
        i++;
        if (ptrs[i] == q) current = i;
     }
     // Уплотнение массива ссылок
     if(current < n) {
        for (i = current; i < n; i++) ptrs[i] = ptrs[i+1];
        for (i = n; i >= 0; i--) ptrs[i]->bkwd = &ptrs[i];
     }
     else current = 0;
      }
      else {  //Удаление оригинала
     n0--;
     if (r = q->link[1]) { // Правое поддерево не пусто? + Уст. r
         if (r->link[0]) { // Случай 3: ищем пустую левую ссылку...
        St->Push(p, a); //Опускаем в стек узел на пути к месту удаления
        p = q;
        a = 1;
        do {
           St->Push(p, a);
           p = r;
           r = r->link[a = 0];
        } while(r->link[0]);
        q->key = r->key; // Нашли, подменяем удаляемое значение...
        current = q->bkwd - ptrs;
        q->bkwd = r->bkwd;
        *q->bkwd = q;
        ptrs[current] = r;
        r->bkwd = &ptrs[current];
        p->link[0] = r->link[1];
        q = r;
         }
         else {
        r->link[0] = q->link[0]; // Случай 2: замена правым сыном
        if(p) p->link[a] = r;
        else root = r;
        St->Push(p, a);
        p = r;
        p->b = q->b;
        a = 1;
         }
     }
     else {
        if (p) p->link[a] = q->link[0];  // Случай 1: правое поддерево пусто
        else root = q->link[0];
     }
     current = q->bkwd - ptrs;
     // Уплотнение массива ссылок
     if(current < n) {
        for (i = current; i < n; i++) ptrs[i] = ptrs[i+1];
        for (i = n; i >= 0; i--) ptrs[i]->bkwd = &ptrs[i];
     }
     else current = 0;
     delete q;    //Уничтожение узла
 
     //===== Балансировка =====
     while (cont) { //Цикл, пока не дойдём до корня дерева
        cont = 0;
        if (!p) h--; // Дошли до корня. Уменьшаем высоту дерева
        else if (p->b) { //b != 0
           cont = 1;
           if (p->b == B[a]) { // Поддерево сбалансировалось. Идем к корню...
           p->b = 0;
           St->Pop(p, a);   //Поднятие из стека указателя на отца и направления
           }
           else { // p->b == -B[a]: Требуется перебалансировка
          q = r = p->link[1-a];
          if (r->b == -p->b) { // Случай 2: двукратный поворот
             r = r->link[a];
             p->link[1-a] = r->link[a];
             q->link[a] = r->link[1-a];
             r->link[a] = p;
             r->link[1-a] = q;
             if (r->b) {
            if (r->b == B[a]) { p->b = 0; q->b = -B[a]; }
            else { p->b = B[a]; q->b = 0; }
            r->b = 0;
             }
             else  q->b = p->b = 0;
          }
          else { // Случаи 1 и 3: однократный поворот
             p->link[1-a] = r->link[a];
             r->link[a] = p;
             if (r->b) { // Случай 1: поддерево стало ниже...
            r->b = p->b = 0;
             }
             else {     // Случай 3: высота поддерева не изменилась!
            r->b = B[a];
            cont = 0;     //...Балансировка закончена. Выход
             }
          }
          St->Pop(p, a);     //Шаг вверх по дереву
          if (p) p->link[a] = r;     // Завершение поворотов
          else root = r;
           }
        }
        else {
           p->b = -B[a]; // (p->b == 0): Алгоритм завершен.
        }
     } //while(cont)...
      }
      return 3; //Выход: "Удаление выполнено"
   }
   else return 4; // Элемента в дереве нет
}
 
int AVL :: Step(A *& ptr, Stack & St, int mode) //Шаг по дереву в порядке внутреннего обхода
{ int a, b;
  if (ptr == 0) { //Первое обращение
    if (root == 0) return 0; //Дерево пусто, выход
    cp = ptr = root;    //Поиск крайнего левого элемента
    while (cp->link[0]) {St.Push(cp, 0); cp = ptr = cp->link[0];}   //Идём влево
    current = cp->k;
    return 1;
  }
  else { //Текущий уже выдан
    if(mode && (--current)) return 1;
    if(cp->link[1]) { //Шаг вправо
      St.Push (cp, 1);
      cp = ptr = cp->link[1];
      while (cp->link[0]) {
      St.Push(cp, 0);
      cp = ptr = cp->link[0];
    }
      current = cp->k;
      return 1;
      }
    else {
      a = 1;
      while(St.Pop(cp, a)&&a);
      if (a) {
    current = n-1;
    return 0;
      }
      else {
    ptr = cp;
    current = cp->k;
    return 1;
      }
    }
  }
}
 
void main()
{  int k = 0, l = 0;
   A * ptr; char op = '0';
   Stack St0;
   AVL * home = new AVL(N1), * second;
   char msg[][18] = {"Начнём, пожалуй...",
            "Уже есть!",
            "Вставлено!",
            "Удалено!",
            "Отсутствует!"},
       antw[][13] = {"HE совпадают", "совпадают"};
 
   textcolor(WHITE); textbackground(BLACK);
   do {
      home->Display(FIRSTROW);
      cout << "\n\nTEST: 1 - IN+INSERT/REMOVE, 2 - FIND, 3 - PUSH/POP/GET/PUT, 4 - PREV/NEXT,\n"
     "5 - Step, 6 - AND/SUB/XOR/OR/MERGE/CONCAT, 7 - MUL,\n"
     "8 - EXCL/ERASE/SUBST/CHANGE/SPLIT, 9 - COPY/EQ;  0 - exit\n Op=";
      op = getche();
      switch (op) {
      case '1':
//Демонстрация вставки и удаления (до ввода значения 0)
   do {
      home->Display(FIRSTROW);
      gotoxy(1, MAXDEPTH+5);
      cout << msg[l];
      cout << "\nElement ['+dd':INSERT/'-dd':REMOVE/'0':exit] ";
      cin >> k;
      if (k > 0) l = home->INSERT(k);
      else if (k < 0) l = home->REMOVE(-k);
   } while (k);
      break;
      case '2':
// Проверка FIND
   do {
      home->Display(FIRSTROW);
      gotoxy(1, MAXDEPTH+6);
      cout << "\n Демонстрация FIND\n";
      clreol();
      printf("FIND: Result = %d; New element ['0':exit] ", k);
      cin >> k;
      if (k > 0) k = home->FIND(k);
   } while (k);
      break;
 
      case '3':
// Проверка PUSH и POP
   do {
      home->Display(FIRSTROW);
      gotoxy(1, MAXDEPTH+6);
      cout << "\n Демонстрация PUT, GET, PUSH и POP\n";
      clreol();
      printf("Result = %d; New element ['+dd'PUT=PUSH, '-'POP, '*'GET, '0':exit] ", k);
      op = getche(); k = 0;
      switch (op) {
        case '-': k = home->POP(); break;
        case '*': k = home->GET(); break;
        case '0': op = 1; break;
        case '+': op = getche();
        default:
          if (isdigit(op)) {
          do {
        k = k*10 + (op - '0');
          } while (isdigit(op = getche()));
          if (k) home->PUSH(k); op = 1;
        }
      }
   } while (k);
      break;
 
      case '4':
// Проверка PREV и NEXT
   do {
      home->Display(FIRSTROW);
      gotoxy(1, MAXDEPTH+6);
      cout << "\n Демонстрация PREV и NEXT\n";
      clreol();
      printf("Result = %d; New element ['-':PREV, '+' NEXT, '0':exit] ", home->CURRENT());
      k = getche();
      switch (k) {
         case '-': home->PREV(); break;
         case '+': home->NEXT(); break;
         default: ;
      }
   } while (k-'0');
      break;
 
      case '5':
//Извлечение из дерева неубывающей последовательности весов
   home->Display(FIRSTROW);
   cout << "\n Демонстрация Step\n";
   ptr = 0;
   while (home->Step(ptr, St0, 1)) {
     cout << ptr->El() << " ";
     getch();
   }
   cout << "\n    The tree is closed. Press any key to continue...";
   getch();
      break;
 
      case '6':
//Двуместные операции над множествами
   do {
      second = new AVL(N2);
      home->Display(FIRSTROW);
      second->Display(SECONDROW);
      gotoxy(1, SECONDROW+MAXDEPTH+3);
      cout << "\n 1-AND, 2-SUB, 3-XOR, 4-OR, 5-MERGE, 6-CONCAT;  0-exit: ";
      clreol();
      k = getche();
      switch (k) {
case '1':   home->AND(second); break;
case '2':   home->SUB(second); break;
case '3':   home->XOR(second); break;
case '4':   home->OR(second); break;
case '5':   home->MERGE(second); break;
case '6':   home->CONCAT(second); break;
default:    ;
      };
//   delete second; - НЕ НУЖНО, удалено в процессе обработки!
   } while (k-'0');
       break;
   case '7':
// Проверка MUL
      second = home;
   do {
      second->Display(FIRSTROW);
      delete second;
      second = new AVL(N2);
      second->Display(SECONDROW);
      gotoxy(1, SECONDROW+MAXDEPTH+2);
      cout << "\n Демонстрация MUL: ";
      clreol();
      printf("Count ['0':exit]=");
      k = getche();
      second->MUL((int)(k - '0'));
   } while (k-'0');
       home = second;
       break;
   case '8':
// Проверка EXCL, ERASE, SUBST, CHANGE
//    second = home;
       do {   int p1 = random(N2),
          p2 = p1 + 1 + random(N2),
          p3 = random(NN),
          *keys;
      home->Display(FIRSTROW);
//    if (second) delete second;
      cout << "\n 1-EXCL, 2-ERASE, 3-SUBST, 4-CHANGE, 5-SPLIT;  0-exit: ";
      clreol();
      k = getche();
      switch (k) {
    case '1':
         keys = home->Part(p1, p2);
         second = new AVL(keys);
         second->Display(SECONDROW);
         gotoxy(1, SECONDROW+MAXDEPTH+2);
         cout << "\n Демонстрация EXCL... ";
         clreol(); getche();
         home->EXCL(second);
         break;
    case '2':
         cout << "\n Демонстрация ERASE("<< p1 << ", " << p2 << ")...";
         clreol(); getche();
         home->ERASE(p1, p2);
         break;
    case '3':
         second = new AVL(N2);
         second->Display(SECONDROW);
         gotoxy(1, SECONDROW+MAXDEPTH+2);
         cout << "\n Демонстрация SUBST(T2, "<< p1 << ")...";
         clreol(); getche();
         home->SUBST(second, p1);
         break;
    case '4':
         second = new AVL(N2);
         second->Display(SECONDROW);
         gotoxy(1, SECONDROW+MAXDEPTH+2);
         cout << "\n Демонстрация CHANGE(T2, "<< p1 << ")...";
         clreol(); getche();
         home->CHANGE(second, p1);
         break;
    case '5':
         gotoxy(1, SECONDROW+MAXDEPTH+2);
         cout << "\n Демонстрация SPLIT("<< p3 << ")...";
         clreol(); getch();
         second = home->SPLIT(p3);
         home->Display(FIRSTROW);
         second->Display(SECONDROW);
         gotoxy(1, SECONDROW+MAXDEPTH+2);
         cout << "\n Готово...";
         clreol(); getch();
         break;
    default: ;
         }
      } while (k-'0');
      break;
       case '9':
//Проверка COPY/EQ
      second = home->COPY();
      int p = 1;
   do {
      home->Display(FIRSTROW);
      second->Display(SECONDROW);
      gotoxy(1, SECONDROW+MAXDEPTH+2);
      cout << "\n Демонстрация COPY/EQ: ";
      clreol();
      printf("\nМножества %s; Сделать копию? ['1' - да; '0':выход]=", antw[p]);
      k = getche();
      delete second;
      if (k - '1') second = new AVL(N2);
      else second = home->COPY();
      p = (*home == *second);
   } while (k-'0');
      delete second;
          break;
       default: ;
       }
    } while (op != '0');
   cout << "\n    The end. Press any key to exit...";
   getch();
}

//=== Красно-чёрные деревья =========================== Версия 5 =====
//=== Демонстрационная программа ===================== (C)Сlgn: 25.04.07
//Построение дерева из упорядоченного массива и выполнение вставок/удалений
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <conio.h>
#include <iostream.h>
 
const int NN=200;
 
class Stack;
typedef int T;                  // Тип хранимых данных
inline int compLT(T a, T b) { return(a < b); }
inline int compEQ(T a, T b) { return(a == b); }
 
enum Direction {left, right};
 
typedef int nodeColor;
 
// Узел красно-чёрного дерева
class Node {
    static Node *root;      // статический указатель на корень
     Node * L[2];       // левый сын, правый сын
     Node *parent;      // отец
     nodeColor color;            // цвет узла (BLACK, RED)
     T data;     // данные в узле
         int k;
     Node **bkwd;
    void Destroy();
    friend class Tree;
    public:
    void Display(int, int, int l = 1);     // Метод для выдачи узла на экран
     Node(T, Node *);    // Конструкторы
     Node();
    void rotate(Direction);      // Вращение
    void insertFixup();          // Восстановление после кставки
    void deleteFixup();          // Восстановление после удаления
    friend Node * SubTree(int, int, T *, Node *);// Создание поддерева
   };
 
Node * Node :: root=0;  //Объявление и инициализация статического поля
 
Node sentinel; //Лист - заглушка (-> конструктор заглушки)
 
Node * NIL  = &sentinel;           // Ссылка на заглушку
 
// Дерево в целом
class Tree {
    Node * root, *cp;// корень
    int n,n0;
        int current;
        Node **ptrs;
    int firstrov;   // позиция на экране
    Node *insertNode(T data);
    void deleteNode(Node *z);
    Node *findNode(T data);
    int Step (Node *&, Stack &);//Один шаг внутреннего обхода дерева
    void OP(Tree *&,int mode=0, int pos=0);
 public:
    void BuildTree(T *);
    Tree (int f) {root = NIL; firstrov = f;}
    ~Tree();
    void Display();
    int IN(T data){return findNode(data)!=NULL; };
    void INSERT(T data){insertNode(data);};
    void REMOVE(T data){deleteNode(findNode(data));};
    void AND(Tree &);
    void XOR(Tree &);
    void PUSH(T k) {INSERT(k);};
    void SUB(Tree &);
    void OR(Tree &);
    void MERGE(Tree & Q){OR(Q);};
    Tree& COPY(Tree &);
 
      };
 
//Tree  t1(1), t2(12);                 // Деревья для работы
 
Node :: Node(T d, Node * p) //Конструктор нового узла
{
     data = d;
     parent = p;
     L[left] = NIL;
     L[right] = NIL;
     color = RED;
}
 
Node :: Node(void)      //Конструктор заглушки
{
     data = 0;
     parent = 0;
     L[left] = this;
     L[right] = this;
     color = BLACK;
}
 
void Node :: Destroy()  // Удаление дерева
{
    if(this != NIL){ L[0]->Destroy();
             L[1]->Destroy();
             delete this;
               }
}
 
Tree :: ~Tree()     // Деструктор для дерева
{
    if(root != NIL) root->Destroy();
}
 
class Els {     //Элемент стека
       Node * p;
       int a;
       Els * pr;
friend class Stack;
public:
       Els(){};
       Els(Node * pp, int e, Els * ptr)
        {p = pp; a = e; pr = ptr;};
       ~Els(){};
       };
 
 
class Stack {
       Els * stptr; // Указатель стека
public:
       Stack(){ stptr = 0; };
       Stack(Node * pp, int e){ stptr = new Els(pp, e, 0); };
       void Push(Node *, int);
       int Pop(Node *&, int &);
};
 
int Stack :: Pop(Node * & pp, int & aa)     //Поднять из стека, вернуть "стек не пуст"
{
   if (stptr) {
      Els * s = stptr;
      pp = s->p;
      aa = s->a;
      stptr = s->pr;
      delete s;
      return 1;
   }
   else return 0;
}
 
void Stack :: Push(Node * pp, int aa)  //Опустить в стек
{
   Els * s = new Els; //ELs(pp, aa); //, stptr);
   s->p = pp;
   s->a = aa;
   s->pr = stptr;
   stptr = s;
}
 
 
int Tree :: Step(Node *& ptr, Stack & St) //Шаг по дереву в порядке внутреннего обхода
{ int a, b;
  if (ptr == 0) { //Первое обращение
    if (root == 0) return 0; //Дерево пусто, выход
    cp = ptr = root;    //Поиск крайнего левого элемента
    while (cp->L[0]) {St.Push(cp, 0); cp = ptr = cp->L[0];} //Идём влево
//  current = cp->k;
    return 1;
  }
  else { //Текущий уже выдан
//    if(mode && (--current)) return 1;
    if(cp->L[1]) { //Шаг вправо
      St.Push (cp, 1);
      cp = ptr = cp->L[1];
      while (cp->L[0]) {
      St.Push(cp, 0);
      cp = ptr = cp->L[0];
    }
//      current = cp->k;
      return 1;
      }
    else {
      a = 1;
      while(St.Pop(cp, a)&&a);
      if (a) {
//  current = n-1;
    return 0;
      }
      else {
    ptr = cp;
//  current = cp->k;
    return 1;
      }
    }
  }
}
 
 
const int FIRSTCOL=40, OFFSET=40; // Данные для выдачи на экран
 
void Tree :: Display (/*char a*/)       // Вывод дерева в целом
{               int col = FIRSTCOL, rov = firstrov;
        gotoxy(col-OFFSET+1, rov);
           //   cprintf("Ждём (%d); осталось %2d ---- КОРЕНЬ --->", a, ct);
        if (root != NIL) root->Display(rov, col);
        else cprintf("<Пусто!>");
        textcolor(BLACK);
}
void Node::Display(int rov, int col, int level) // Вывод одного узла
{       gotoxy(col, rov);
        if (color == RED) textcolor (LIGHTRED);
        else textcolor(color);
        cprintf("%d", data);
        if (L[left] != NIL) L[left]->Display(rov+1, col-(OFFSET>>level), level+1);
        if (L[right] != NIL) L[right]->Display(rov+1, col+(OFFSET>>level), level+1);
}
 
void Node :: rotate(Direction D) { //Поворот в направлении D (комментарии для случая "влево")
 
     Node *x = this, *y = x->L[1-D];  //=right
 
     /* установка указателя x->right */
     x->L[1-D] = y->L[D];
     if (y->L[D] != NIL) y->L[D]->parent = x;
 
     /* установка указателя y->parent */
     if (y != NIL) y->parent = x->parent;
     if (x->parent) {
          if (x == x->parent->L[D])
                x->parent->L[D] = y;
          else
                x->parent->L[1-D] = y;
//           x->parent->L[1 - (x == x->parent->L[D])] = y;
     }
     else {
       root = y;
     }
 
     /* связывание x и y */
     y->L[D] = x;
     if (x != NIL) x->parent = y;
}
 
void Node :: insertFixup() {    // Балансировка после вставки
 
     Node *x = this;
     Direction D;
     /* проверка красно-чёрных свойств */
     while (x != root && x->parent->color == RED) {
          /* обнаружено нарушение... */
          D = (Direction)(x->parent == x->parent->parent->L[left]);
 
          Node *y = x->parent->parent->L[D];  //right
                if (y->color == RED) {
 
                     /* дядя - RED */
                     x->parent->color = BLACK;
                     y->color = BLACK;
                     x->parent->parent->color = RED;
                     x = x->parent->parent;
                } else {
 
                     /* дядя - BLACK */
                     if (x == x->parent->L[D]) { //right
                          /* делаем x левым сыном */
                          x = x->parent;
                          x->rotate((Direction)(1-D));
                     }
 
                     /* перекраска и поворот */
                     x->parent->color = BLACK;
                     x->parent->parent->color = RED;
                //   rotateRight(x->parent->parent);
                     x->parent->parent->rotate(D);
                }
     }
     root->color = BLACK;
}
 
Node * Tree :: insertNode(T data) { // Создание узла и вставка в дерево
 
     Node *current, *parent, *x;
     Node::root = this->root;
     /* поиск места вставки... */
     current = root;
     parent = 0;
     while (current != NIL) {
          if (compEQ(data, current->data)) return (current);
          parent = current;
          current = compLT(data, current->data) ?
                current->L[left] : current->L[right];
     }
 
     /* создание нового узла */
     if ((x = new Node(data, parent)) == 0) {
       printf ("Недостаточно памяти: (insertNode)\n");
       exit(1);
     }
 
     /* вставка в дерево */
    if(parent) {
      if(compLT(data, parent->data))
         parent->L[left] = x;
      else
         parent->L[right] = x;
     }
    else Node::root = root = x;
 
    x->insertFixup();
    root = Node::root;
    return x;
}
 
void Node :: deleteFixup() {    // Балансировка после удаления
 
     Node *x = this;
     while (x != root && x->color == BLACK) {
        Direction D =  (Direction)(x == x->parent->L[left]);
        Node *w = x->parent->L[D];      //right
        if (w->color == RED) {
           w->color = BLACK;
           x->parent->color = RED;
           x->parent->rotate((Direction)(1-D)); //left
           w = x->parent->L[D];     //right
        }
        if (w->L[left]->color == BLACK && w->L[right]->color == BLACK) {
           w->color = RED;
           x = x->parent;
        }
        else {
           if (w->L[D]->color == BLACK) {   //right
             w->L[1-D]->color = BLACK;  //left
             w->color = RED;
             w->rotate(D);          //right
             w = x->parent->L[D];       //right
           }
           w->color = x->parent->color;
           x->parent->color = BLACK;
           w->L[D]->color = BLACK;      //right
           x->parent->rotate((Direction)(1-D));     //left
           x = root;
        }
    }
    x->color = BLACK;
}
 
void Tree :: deleteNode(Node *z) {  // Удаление узла z из дерева
 
     Node *x, *y;
     Node::root = this->root;
 
     if (!z || z == NIL) return;
 
 
     if (z->L[left] == NIL || z->L[right] == NIL) {
    /* узел z имеет сына - NIL-узел, можно удалить/исключить z */
       y = z;
     } else {
    /* поиск замещающего узла с NIL-сыном */
       y = z->L[right];
       while (y->L[left] != NIL) y = y->L[left];
     }
 
    /* x - единственный сын узла y */
     if (y->L[left] != NIL)
       x = y->L[left];
     else
       x = y->L[right];
 
    /* удаление y из цепочки от отца */
     x->parent = y->parent;
     if (y->parent)
       if (y == y->parent->L[left])
         y->parent->L[left] = x;
       else
         y->parent->L[right] = x;
     else
       root = x;
 
     if (y != z) z->data = y->data;
 
 
     if (y->color == BLACK)
       x->deleteFixup ();
 
     delete y;
     root = Node::root;
}
Node * Tree :: findNode(T data) {   // Поиск узла по данным
 
    Node *current = root;
    while(current != NIL)
    if(compEQ(data, current->data))
        return (current);
    else
        current = compLT (data, current->data) ?
        current->L[left] : current->L[right];
    return(0);
}
 
Node * SubTree(int a, int b, T * source, Node * p)
{
    if (b < a) return NIL;
    else if (b == a) return new Node(source[a], p);
    else {
      int c = a + (int)((b - a) / 2);
      Node *t = new Node(source[c], p);
      t->data = source[c];
      t->L[0] = SubTree(a, c-1, source, t);
      t->L[1] = SubTree(c+1, b, source, t);
//    if((t->L[0] != NIL) || (t->L[1] != NIL))
        t->color = BLACK;
      t->parent = p;
      return t;
    }
}
 
int strlen1(T * ss)
{ int c = 0;
  while(ss[c++]);
  return c;
}
 
void Tree :: BuildTree(T * source)
{
    root = SubTree(0, strlen1(source)-1, source, 0);
}
void Tree :: OP(Tree *& T, int mode, int pos)    //Двуместная операция
{       //(0 - AND, 1 - SUB, 2 - XOR, 3 - OR, 4 - MERGE, 5 - CONCAT)
    // pos != 0 -> вместо сцепления - вставка с позиции 'pos - 1'
   int p = 0, p0, p1, q = 0;
   Node ** pt = new Node * [NN],       //Массив для узлов результата
     ** pq = new Node * [n + T->n]; //Массив для лишних узлов
   Node * s0 = 0, * s1 = 0;
   Stack St0, St1;
   p0 = Step(s0, St0);
   p1 = T->Step(s1, St1);
   while (p0 && p1) { //Отбор узлов для нового дерева, сброс ссылок на них
     if (s0->data == s1->data) {
     if (!mode || (mode > 2)) pt[p++] = s0;
     s0->k = (mode > 3)? s0->k + s1->k : 1; //MERGE -> счёт кратности
     pq[q++] = s1;    //Дубликат -> в список удаляемых
     *s1->bkwd = s0;  //Перестановка ссылки на сохранённый узел
     p0 = Step(s0, St0);
     p1 = T->Step(s1, St1);
      }
      else if (s0->data < s1->data) {
     if (mode) { pt[p++] = s0;
         if (mode < 4) s0->k = 1;
         }
     else pq[q++] = s0;  //Ненужный узел - в список удаляемых
     p0 = Step(s0, St0);
      }
      else {
     if (mode > 1) { pt[p++] = s1;
        if (mode < 4) s1->k = 1;
        }
     else pq[q++] = s1; //Ненужный узел - в список удаляемых
     p1 = T->Step(s1, St1);
      }
   };
   //Подбор "хвостов"
   while (p0) {
    if (mode) { //Не AND
       pt[p++] = s0;
       if (mode < 4) s0->k = 1; //Результат - множество: кратность = 1
       }
    else pq[q++] = s0;  //Ненужный узел - в список удаляемых
    p0 = Step(s0, St0);
   }
   while (p1) {
    if (mode > 1) { //Не AND и не SUB
       pt[p++] = s1;
       if (mode < 4) s1->k = 1; //Результат - множество: кратность = 1
    }
    else pq[q++] = s1; //Ненужный узел - в список удаляемых
    p1 = T->Step(s1, St1);
   }
 
   for (p0 = 0; p0 < q; p0++) delete pq[p0]; //Уничтожение лишних узлов
   if (mode == 5) { //CONCAT: сцепление массивов ссылок, р-т -> в pq[]
      if (pos > n + 1) pos = 0;
      int n1 = pos? pos - 1 : n; //Если вставка, копировать только до 'pos'
      for (q = 0; q < n1; q++)
         pq[q] = ptrs[q];
      current = q;
      for (p0 = 0; p0 < T->n; p0++)
         pq[q++] = T->ptrs[p0];
      if (pos) for (p0 = pos - 1; p0 < n; p0++) //Вставка: копировать остаток
         pq[q++] = ptrs[p0];
      n = q;
   }
   else {
     n = p; delete []pq; //Не CONCAT: уничтожение pq[]
   }
   T->root = 0; //Все узлы T использованы или уже удалены
   delete T;
   delete []ptrs;
   ptrs = pt;  //Переключение массива ссылок на результат; сброс link[]
   for (q = 0; q < p; q++) ptrs[q]->L[0] = ptrs[q]->L[1] = 0;
   root = SubTree(0, p,ptrs, h); //Сборка нового дерева
   n0 = p;  //Установка мощности для множества
   if (mode == 4) BuildSeq(); //MERGE: обработка кратностей
   if (mode == 5) { //CONCAT: подмена массива ссылок
      delete []ptrs; //Уничтожение упорядоченного массива
      ptrs = pq;     //... подмена
      for (q = n - 1; q >= 0; q--) //Установка обратных ссылок
     ptrs[q]->bkwd = &ptrs[q];
   }
   else current = 0;
}
 
 
void main(void)
{ int k = 0;// l = 0, N = 0;
Node *t;
Tree *t1=new Tree(1);
 
 // char nametr[][3] = {"S1", "S2", "S"};
 
  T source[] = {1,2,3,5,6,7,12,15,23,35,40,0};    //int source1[] = {1, 2, 3, 4, 0};
 // int source2[] = {3, 4, 5, 6, 7, 0};
 // Tree S1; //ДЕРЕВЬЯ ДЛЯ УПРАЖНЕНИЙ
 
 char msg[][52] = {"Работа с RBTree-деревом:демонстрационная программа",
            "Элемент уже есть!",
            "Вставлено!",
            "Удалено!",
            "Отсутствует!"};
 //  Tree *t1=&S1;
 
  // textcolor(15);
  /* for (k = 0; K[k]; k++) home.Insert(K[k]);
   for (k = 0; K1[k]; k++) S1.Insert(K1[k]);
   for (k = 0; K2[k]; k++) S2.Insert(K2[k]); */
   do {
     clrscr();
 
     puts("\n\n");
     puts("RBTree Демонстрация\n\n");
     puts("1-Вывести текущее дерево на экран \n");
     puts("2-Выполнить операции...->         \n");
     puts("0-Выход                          \n\n");
     printf("Выберите пункт меню: ");
 
     cin >> k;
     switch (k)
     {
       case 1: {
             clrscr();
             t1->BuildTree(source);
             textbackground(WHITE);
             clrscr();
             t1->Display();
             getch();
             break;
             }
       case 2: {
             int k1;
             do
             {
               clrscr();
               puts("Выберите операцию: \n\n");
               puts("1-INSERT       \n");
               puts("2-REMOVE        \n");
               puts("3-AND          \n");
               puts("4-XOR          \n");
               puts("5-MERGE           \n");
               puts("6-SUB              \n");
               puts("7-OR               \n");
               puts("8-COPY             \n");
               puts("9-IN              \n");
               puts("10-PUSH           \n");
 
               puts("0-Вернуться в главное меню\n\n\n");
               printf("Выберите пункт меню: ");
               cin >> k1;
 
               if (k1)
             switch (k1)
             {
               int min;
               case 1: {
                    clrscr();
                    cout << "Вставка элемента в текущее дерево\n";
                    cout << "Введите ключ нового элемента ";
                    int ky;
                    cin >> ky;
                    t1->Display();
                    cout << "\nДля просмотра результата вставки нажмите любую клавишу";
                    getch();
                    clrscr();
                    t1->INSERT(ky);
                    cout << "Результат вставки: " << msg[ky] << "\n";
                    t1->Display();
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                    break;
                   }
               case 2: {
                    clrscr();
                    cout << "Удаление элемента из текущего дерева\n";
                    cout << "Введите ключ удаляемого элемента ";
                    int ky;
                    cin >> ky;
                    t1->Display();
                    cout << "\nДля просмотра результата удаления нажмите любую клавишу";
                    getch();
                    clrscr();
                    t1->REMOVE(ky);
                    cout << "Результат удаления: " << msg[ky] << "\n";
                    t1->Display();
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                    break;
                   }
              /* case 3: {
                    clrscr();
                    cout << "Выполняем операцию and деревьев S1 и S2, результат записан в дереве S\n";
                    cout << "Для просмотра деревьев S1 и S2 нажмите любую клавишу\n";
                    getch();
                    S1.Display();
                    getch();
                    S2.Display();
                    S1.and(&S1, &S2, &S);
                    cout << "\nРезультат - содержимое дерева S. Для просмотра результата нажмите любую клавишу";
                    getch();
                    S.Display();
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                    break;
                   }
               case 4: {
                    clrscr();
                    cout << "Выполняем операцию xor деревьев S1 и S2, результат записан в дереве S";
                    cout << "Для просмотра деревьев S1 и S2 нажмите любую клавишу\n";
                    getch();
                    S1.Display();
                    getch();
                    S2.Display();
                    curtree->xor(&S1, &S2, &S);
                    cout << "\nРезультат - содержимое дерева S. Для просмотра результата нажмите любую клавишу";
                    getch();
                    S.Display();
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                   break;
                   }
               case 5: {
                    clrscr();
                    cout << "Выполняем операцию merge деревьев S1 и S2, результат записан в дереве S";
                    cout << "Для просмотра деревьев S1 и S2 нажмите любую клавишу\n";
                    getch();
                    S1.Display();
                    getch();
                    S2.Display();
                    curtree->merge(&S1, &S2, &S);
                    cout << "\nРезультат - содержимое дерева S. Для просмотра результата нажмите любую клавишу";
                    getch();
                    S.Display();
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                   break;
                   }
               case 6: {
                    clrscr();
                    ctree(curtree);
                    curtree->Display();
                    cout << "\n";
                    if ((min=curtree->min()) != -1)
                      cout << "Минимальное значение = "<< min;
                    else
                      cout << "Дерево пусто!\n";
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                    break;
                   }
               case 7: {
                    clrscr();
                    ctree(curtree);
                    cout << "Выполнение операции размножения текущего дерева\n";
                    cout << "Введите множитель ";
                    int ky;
                    cin >> ky;
                    curtree->Display();
                    cout << "\nДля просмотра результата размножения нажмите любую клавишу";
                    getch();
                    clrscr();
                    curtree->mul(ky); //увеличиваем счетчики count в каждом листе
                    curtree->Display();
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                   break;
                   }
               case 8: {
                    clrscr();
 
                    cout << "Выполнение операции замены значений дерева S1 значениями из S2\n";
                    cout << "Введите номер в последовательности, с которого производить замену ";
                    int ky;
                    cin >> ky;
                    clrscr();
                    cout << "Для просмотра деревьев S1 и S2 нажмите любую клавишу\n";
                    getch();
                    S1.Display();
                    getch();
                    S2.Display();
                    if (S1.change(&S2, &S, ky))
                      cout << "\nНеверный номер в последовательности, последовательность меньше!\n";
                    else
                    {
                    cout << "\nРезультат - содержимое дерева S. Для просмотра результата нажмите любую клавишу";
                    getch();
                    S.Display();
                    }
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                   break;
                   }  */
                case 9: {
                    clrscr();
                    int curt;
                    t1->Display();
                    curt=t1->IN(curt);
                    //t1->INSERT(curt);
                    //cout << "Текущий элемент = "<< curt;
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                   break;
                   }
               case 10: {
                    clrscr();
                    cout << "Выполнение операции push текущего дерева\n";
                    cout << "Введите ключ опускаемого элемента ";
                    int ky;
                    cin >> ky;
                    t1->Display();
                    cout << "\nДля просмотра результата операции нажмите любую клавишу";
                    getch();
                    clrscr();
                    t1->PUSH(ky); //увеличиваем счетчики count в каждом листе
                    t1->Display();
                    cout << "\nДля возврата в меню нажмите любую клавишу";
                    getch();
                   break;
                   }
             }
             } while (k1);
             break;
           }
        /* case 4: {
               int k1, ct;
 
               ctree(curtree);
               cout << "Изменить дерево (текущие значения будут утрачены!) (1-Да/0-Нет) ";
               cin >> k1;
               if (k1 != 1) break;
               curtree->~Tree();
               cout << "Введите жедаемое кол-во элементов дерева ";
               cin >> k1;
               randomize();
               for (int u=0; u<k1; u++) curtree->Insert(random(100));
               break;
 
             } */
     }
   } while (k);
   clrscr();
   return;
}
 
 
 
 
 
 
/*void main(int argc, char **argv)
{
    int a, b, maxnum, ct;
    Node *t;
    Tree *t1 = new Tree(1), *t2 = new Tree(15);
 
    T source[] = {1,2,3,5,7,8,12,24,31,42,55,56,77,88,98,102,0};    //Стартовое дерево
    t1->BuildTree(source);
    textbackground(WHITE);
    clrscr();
    t1->Display('*', 0);
    getch();
//    delete t1;
//    t1 = new Tree(1);
 
    /* Вызов:
     *
     *   rbt maxnum
     *
     *   Пример: rbt 2000
     *     ->  выполнить 2000 вставок/удалений
     *
     */
       /*   if (argc < 2) printf("\nУкажите количество операций!");
    else {
      maxnum = atoi(argv[1]);
      randomize();
      a = random(26) + 'A';
      for (ct = maxnum; ct; ct--) {
    b = random(52) + 'A';
    if (b > 'Z') b +=  'a' - 'A' - 26;
    if (t1->IN(a)) {
         t2->INSERT(a);
         t1->REMOVE(a);
     }
    else t1->INSERT(a);
    clrscr();
    t1->Display(b, ct);
    t2->Display(b, ct);
    getch();
    a = b;
     }
    }
} */