удаление элемента из Red-Black tree - C++ - Ответ 3077303

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <conio.h>
#include <iostream.h>
int QQ = 10;
int QQ1 =8;
int Nk = 1000; //Limit for data
const int NN=200;
const int N3=10;
const int FIRSTROW = 1, SECONDROW = 13,
       MAXDEPTH = 5; //Константы управления выводом на экран
 
class Stack;
//typedef int T;                  // Тип хранимых данных
inline int compLT(int a, int b) { return(a < b); }
inline int compEQ(int a, int 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)
     int data;     // данные в узле
     int k;
     Node **bkwd;
    void Destroy();
    friend class Tree;
    public:
    void Display(int, int, int l = 1);     // Метод для выдачи узла на экран
     Node(int, Node *);  // Конструкторы
     Node();
    void rotate(Direction);      // Вращение
    void insertFixup();          // Восстановление после кставки
    void deleteFixup();          // Восстановление после удаления
    friend Node * SubTree(int &, Node **, int, int, int *, 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(int data);
    void deleteNode(Node *z);
    Node *findNode(int data);
    int Step (Node *&, Stack &);//Один шаг внутреннего обхода дерева
    void OP(Tree *&,int mode=0, int pos=0);
    Node * Build(int a, int b, int &h2);
    void BuildSeq();
 public:
    void BuildTree(int *);
    Tree (int f) {root = NIL; firstrov = f;}
    Tree (int f, int N);
    ~Tree();
    void Display(int);
    int IN(int data){return findNode(data)!=NULL; };
    void INSERT(int data){insertNode(data);};
    void REMOVE(int data){deleteNode(findNode(data));};
    void AND(Tree *& T) { OP(T); }
    void SUB(Tree *& T) { OP(T, 1); }
    void XOR(Tree *& T) { OP(T, 2); }
    void OR(Tree *& T)  { OP(T, 3); }
    void MERGE(Tree *& T) { OP(T, 4); }
    Tree& COPY(Tree &);
    void PUSH(int k) {INSERT(k);};
 
      };
 
Tree :: Tree (int f, int N)
{ int i, c = 0,d = Nk/N,* s = new int[N+1];
  ptrs  = new Node* [NN];
  n0 =N;
  n =0;
  firstrov = f;
  for(i = 0; i < N; i++)
  { c += random(d)+1;
    s[i] = c;
  }
  s[N] = 0;
 
  BuildTree(s);
  delete []s;
}
//Tree  t1(1), t2(12);                 // Деревья для работы
 
Node :: Node(int d, Node * p)   //Конструктор нового узла
{
     data = d;
     k = 1;
     bkwd = NULL;
     parent = p;
     L[left] = NIL;
     L[right] = NIL;
     color = RED;
}
 
Node :: Node(void)      //Конструктор заглушки
{
     data = 0;
     parent = 0;
     k = 1;
     bkwd = NULL;
     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 (int firstrow)     // Вывод дерева в целом
{
 
         if (firstrow == FIRSTROW)  //Вызов для главного дерева -> очистить экран
         clrscr();
        gotoxy(1, firstrow);
        cprintf("Red-Black demonstration");
           //   int col = FIRSTCOL, rov = firstrov;
           //   gotoxy(col-OFFSET+1, rov);
           //   cprintf("Ждём (%d); осталось %2d ---- КОРЕНЬ --->", a, ct);
        if (root != NIL)
        {
            root->Display(firstrow,FIRSTCOL,1);
            gotoxy(1,firstrow + MAXDEPTH + 2);
            for(int i=0; i<n; i++)printf("%1d ", ptrs[i]->data);
        }
        else cprintf("<Empty>");
        textcolor(BLACK);
}
 
void Node::Display(int rov, int col, int level) // Вывод одного узла
{
         if(level > MAXDEPTH) {cout << "..."; return; }
        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(int data) {   // Создание узла и вставка в дерево
 
     Node *current, *parent, *x;
     Node::root = this->root;
 
     /* поиск места вставки... */
     current = root;
     parent = 0;
     while (current != NIL) {
          if (compEQ(data, current->data)){
          ptrs[n++] = current;
          current->k++;
          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);
     }
     ptrs[n] = x;
     ptrs[n]->bkwd = &ptrs[n];
     n++;
     n0++;
     /* вставка в дерево */
    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;
     int i;
 
     Node::root = this->root;
     n--;
     n0--;
 
     if (!z || z == NIL) return;
     ptrs[n]=z;
 
     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;
 
     current = x->bkwd - ptrs;
     x->bkwd = y->bkwd;
     *x->bkwd = x;
     ptrs[current] = y;
     y->bkwd = &ptrs[current];
 
     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 ();
      current = x->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 y;
     root = Node::root;
}
 
Node * Tree :: findNode(int 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 &n, Node ** ptrs, int a, int b, int * source, Node * p)
{
    if (b < a) return NIL;
    else if (b == a) {
      ptrs[n] = new Node(source[a], p);
      ptrs[n]->bkwd = &ptrs[n];
      return ptrs[n++];
    }
    else {
      int c = a + (int)((b - a) / 2);
      Node * t = ptrs[n] = new Node(source[a], p);
      t->data = source[c];
      t->bkwd = &ptrs[n++];
      t->L[0] = SubTree(n, ptrs, a, c-1, source, t);
      t->L[1] = SubTree(n, ptrs, c+1, b, source, t);
//    if((t->L[0] != NIL) || (t->L[1] != NIL))
        t->color = BLACK;
      t->parent = p;
      return t;
    }
}
 
int strlen1(int * ss)
{ int c = 0;
  while(ss[c++]);
  return c-1;
}
 
void Tree :: BuildTree(int * source)
{
    n0 = strlen1(source); n = 0;
    root = SubTree(n, ptrs, 0, n0-1, source, 0);
    root->color=BLACK;
}
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, h = 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 = 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;
}
 
Node * Tree :: Build(int a, int b, int &h2) //Сборка RB-дерева из массива узлов
{
   h2 = 0;
   if (b <= a) return 0;
   int h0 = 0, h1 = 0, c = (a + b) /2;
   Node * s = ptrs[c];
   s->bkwd = &ptrs[c];
   s->L[0] = Build(a, c, h0);
   s->L[1] = Build(c+1, b, h1);
   s->color = h0+h1>0? BLACK : RED;
   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;
   if (p1 < 0) p1 = 0;
   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 Tree :: 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 main(void)
{
    int ky, k = 0;// l = 0, N = 0;
    Node *t;
    Tree *t1=new Tree(FIRSTROW,QQ1), *t2;
  // int source[] = {1,2,3,5,6,7,12,15,23,35,40,0};
   //   int source1[]= {4,6,77,45,33,0};
      /*    char msg[][58] = {"Работа с RBTree-деревом:демонстрационная программа",
            "Элемент уже есть!",
            "Вставлено!",
            "Удалено!",
            "Отсутствует!"};  */
   //   t1->BuildTree(source);
    textcolor(BLACK);
    textbackground(WHITE);
    do {
        clrscr();
        t1->Display(FIRSTROW);
        gotoxy(1, MAXDEPTH+3);
        cout << "\n\n 1 - IN+INSERT; 2 - REMOVE; 3 - PUSH; 4 - AND/SUB/XOR/OR/MERGE;"
              " 0 - Exit\n Op=";
        cin >> k;
        switch (k)
        {
        case 1:
        {
            gotoxy(1, MAXDEPTH+7);
            cout << "\New Element:";
            cin >> ky;
            t1->INSERT(ky);
            break;
            }
        case 2:
        {
            gotoxy(1, MAXDEPTH+7);
            cout << "\Deleted element:";
            cin >> ky;
            t1->REMOVE(ky);
            break;
 
        }
        case 3:
        {
            gotoxy(1, MAXDEPTH+7);
            cout << "\New Element:";
            int ky;
            cin >> ky;
            t1->PUSH(ky);
            break;
        }
        case 4:
        {
        do
        {
            Tree *t2=new Tree(SECONDROW, QQ);
            t1->Display(FIRSTROW);
            t2->Display(SECONDROW);
            gotoxy(1, SECONDROW+MAXDEPTH+3);
            cout << "\n 1-AND, 2-SUB, 3-XOR, 4-OR, 5-MERGE;  0-exit: ";
            clreol();
            cin >> k;
            switch (k) {
                case 1: t1->AND(t2); break;
                case 2: t1->SUB(t2); break;
                case 3: t1->XOR(t2); break;
                case 4: t1->OR(t2); break;
                case 5: t1->MERGE(t2); break;
        }
        } while (k);
        break;
 
 
        }
 
        }
    }while (k);
 
        cout << "\n The end. Press any key to exit...";
        getch();
}