type
  PBTnode = ^BTnode;
  BTnode =  record
    up    : PRBTnode;
    left  : PRBTnode;
    right : PRBTnode;
    key   : typ_danych;
    …
  end;

struct BTnode
{
  BTnode *up, *left, *right;
  typ_danych key;
  …
};

Type BTnode
  up As BTnode Ptr
  left As BTnode Ptr
  right As BTnode Ptr
  key As typ_danych
  …
End Type

// Zbiory zaimplementowane
// w drzewach czerwono-czarnych
// Data: 9.07.2014
// (C)2014 mgr Jerzy Wałaszek
//-----------------------------

program sets;

// Definicja węzła drzewa
// czerwono-czarnego
type
  PRBTnode = ^RBTnode;
  RBTnode  = record
    up    : PRBTnode;
    left  : PRBTnode;
    right : PRBTnode;
    key   : integer;
    color : char;
  end;

// Zmienne globalne

var
  // Węzeł strażnika
  S : RBTnode = (up:@S;
                 left:@S;
                 right:@S;
                 key:0;
                 color:'B');

// Procedury obsługi drzew
// czerwono-czarnych

// Wykonuje rotację
// w lewo względem A
//------------------
procedure rot_L(var root : PRBTnode;
                       A : PRBTnode);
var
  B, p : PRBTnode;
begin
  B := A^.right;
  if B <> @S then
  begin
    p := A^.up;
    A^.right := B^.left;
    if A^.right <> @S then
      A^.right^.up := A;
    B^.left := A;
    B^.up := p;
    A^.up := B;
    if p <> @S then
    begin
      if p^.left = A then
        p^.left := B
      else
        p^.right := B;
    end
    else root := B;
  end;
end;

// Wykonuje rotację
// w prawo względem A
//-------------------
procedure rot_R(var root : PRBTnode;
                       A : PRBTnode);
var
  B, p : PRBTnode;
begin
  B := A^.left;
  if B <> @S then
  begin
    p := A^.up;
    A^.left := B^.right;
    if A^.left <> @S then
      A^.left^.up := A;
    B^.right := A;
    B^.up := p;
    A^.up := B;
    if p <> @S then
    begin
      if p^.left = A then
        p^.left := B
      else
        p^.right := B;
    end
    else root := B;
  end;
end;

// Wstawia do drzewa węzeł
// o kluczu k
//------------------------
procedure insert_rbt(var root : PRBTnode;
                            k : integer);
var
  X, Y : PRBTnode;
begin
  // Tworzymy nowy węzeł
  new(X);
  // Inicjujemy pola
  X^.left  := @S;
  X^.right := @S;
  X^.up    := root;
  X^.key   := k;
  // X staje się korzeniem
  if X^.up = @S then
    root := X
  else
    // Szukamy liścia do zastąpienia przez X
    while true do
    begin
      if k < X^.up^.key then
      begin
        if X^.up^.left = @S then
        begin
          // X zastępuje lewy liść
          X^.up^.left := X;
          break;
        end;
        X^.up := X^.up^.left;
      end
      else
      begin
        if X^.up^.right = @S then
        begin
          // X zastępuje prawy liść
          X^.up^.right := X;
          break;
        end;
        X^.up := X^.up^.right;
      end;
    end;
  // Węzeł kolorujemy na czerwono
  X^.color := 'R';
  while (X <> root) and
        (X^.up^.color = 'R') do
  begin
    if X^.up = X^.up^.up^.left then
    begin
      // Y -> wujek X
      Y := X^.up^.up^.right;
      // Przypadek 1
      if Y^.color = 'R' then
      begin
        X^.up^.color := 'B';
        Y^.color := 'B';
        X^.up^.up^.color := 'R';
        X := X^.up^.up;
        continue;
      end;
      // Przypadek 2
      if X = X^.up^.right then
      begin
        X := X^.up;
        rot_L(root, X);
      end;
      // Przypadek 3
      X^.up^.color := 'B';
      X^.up^.up^.color := 'R';
      rot_R(root, X^.up^.up);
      break;
    end
    else
    begin // Przypadki lustrzane
      Y := X^.up^.up^.left;
      // Przypadek 1
      if Y^.color = 'R' then
      begin
        X^.up^.color := 'B';
        Y^.color := 'B';
        X^.up^.up^.color := 'R';
        X := X^.up^.up;
        continue;
      end;
      // Przypadek 2
      if X = X^.up^.left then
      begin
        X := X^.up;
        rot_R(root, X);
      end;
      // Przypadek 3
      X^.up^.color := 'B';
      X^.up^.up^.color := 'R';
      rot_L(root, X^.up^.up);
      break;
    end;
  end;
  root^.color := 'B';
end;

// Wyszukuje najmniejszy węzeł
// w poddrzewie o korzeniu p
//----------------------------
function  min_rbt(p : PRBTnode)
                    : PRBTnode;
begin
  if p <> @S then
    while p^.left <> @S do
      p := p^.left;
  min_rbt := p;
end;

// Zwraca następnik p
//-------------------
function succ_rbt(p : PRBTnode)
                    : PRBTnode;
var
  r : PRBTnode;
begin
  succ_rbt := @S;
  if p <> @S then
  begin
    if p^.right <> @S then
      succ_rbt := min_rbt(p^.right)
    else
    begin
      r := p^.up;
      while (r <> @S) and
            (p = r^.right) do
      begin
        p := r;
        r := r^.up;
      end;
      succ_rbt := r;
    end;
  end;
end;

// Usuwa z drzewa węzeł X
//-----------------------
procedure remove_rbt(var root : PRBTnode;
                            X : PRBTnode);
var
  W, Y, Z : PRBTnode;
begin
  if (X^.left = @S) or
     (X^.right = @S) then
    Y := X
  else
    Y := succ_rbt(X);
  if Y^.left <> @S then
    Z := Y^.left
  else
    Z := Y^.right;
  Z^.up := Y^.up;
  if Y^.up = @S then
    root := Z
  else
    if Y = Y^.up^.left then
      Y^.up^.left  := Z
  else
    Y^.up^.right := Z;
  if Y <> X then
    X^.key := Y^.key;
  // Naprawa struktury drzewa
  // czerwono-czarnego
  if Y^.color = 'B' then
    while (Z <> root) and
          (Z^.color = 'B') do
      if Z = Z^.up^.left then
      begin
        W := Z^.up^.right;
        if W^.color = 'R' then
        begin // Przypadek 1
          W^.color := 'B';
          Z^.up^.color := 'R';
          rot_L(root, Z^.up);
          W := Z^.up^.right;
        end;
        if (W^.left^.color = 'B') and
           (W^.right^.color = 'B') then
        begin // Przypadek 2
          W^.color := 'R';
          Z := Z^.up;
          continue;
        end;
        if W^.right^.color = 'B' then
        begin // Przypadek 3
          W^.left^.color := 'B';
          W^.color := 'R';
          rot_R(root, W);
          W := Z^.up^.right;
        end;
        // Przypadek 4
        W^.color := Z^.up^.color;
        Z^.up^.color := 'B';
        W^.right^.color := 'B';
        rot_L(root, Z^.up);
        // To spowoduje zakończenie pętli
        Z := root;
      end
      else
      begin // Przypadki lustrzane
        W := Z^.up^.left;
        if W^.color = 'R' then
        begin // Przypadek 1
          W^.color := 'B';
          Z^.up^.color := 'R';
          rot_R(root, Z^.up);
          W := Z^.up^.left;
        end;
        if (W^.left^.color = 'B') and
           (W^.right^.color = 'B') then
        begin // Przypadek 2
          W^.color := 'R';
          Z := Z^.up;
          continue;
        end;
        if W^.left^.color = 'B' then
        begin // Przypadek 3
          W^.right^.color := 'B';
          W^.color := 'R';
          rot_L(root, W);
          W := Z^.up^.left;
        end;
        // Przypadek 4
        W^.color := Z^.up^.color;
        Z^.up^.color := 'B';
        W^.left^.color := 'B';
        rot_R(root, Z^.up);
        // To spowoduje zakończenie pętli
        Z := root;
      end;
  Z^.color := 'B';
  dispose(Y);
end;

// Procedury obsługi zbioru

// Szuka w drzewie węzła
// o danej wartości klucza x.
// Jeśli węzeł zostanie
// znaleziony, to zwraca jego adres.
// Inaczej zwraca wskazanie puste.
//----------------------------------
function s_isin(A : PRBTnode;
                x : integer)
                  : PRBTnode;
begin
  while A <> @S do
  begin
    // Węzeł znaleziony
    if A^.key = x then Exit(A);
    if x < A^.key then
      A := A^.left
    else
      A := A^.right;
  end;
  // Węzeł nieznaleziony
  s_isin := nil;
end;

// Dodaje do drzewa nowy węzeł,
// jeśli w drzewie takiego węzła
// jeszcze nie ma
//------------------------------
procedure s_add(var A : PRBTnode;
                    x : integer);
begin
  if s_isin(A, x) = nil then
    insert_rbt(A, x);
end;

// Wyszukuje w drzewie węzeł
// o kluczu x i usuwa go
//--------------------------
procedure s_remove(var A : PRBTnode;
                       x : integer);
var
  p : PRBTnode;
begin
  // Szukamy węzła o kluczu x
  p := s_isin(A, x);
  if p <> nil then
    remove_rbt(A, p);
end;

// Usuwa wszystkie węzły z drzewa
//-------------------------------
procedure s_clear(var A : PRBTnode);
begin
  if A <> @S then
  begin
    // Rekurencyjnie usuwamy
    // lewe poddrzewo
    s_clear(A^.left);
    // Rekurencyjnie usuwamy
    // prawe poddrzewo
    s_clear(A^.right);
    // Usuwamy węzeł
    dispose(A);
    A := @S;
  end;
end;

// Procedura kopiuje elementy
// z drzewa A do C
//---------------------------
procedure s_copy(A : PRBTnode;
             var C : PRBTnode);
begin
  if A <> @S then
  begin
    // Dodajemy do C klucz
    // bieżącego węzła
    s_add(C, A^.key);
    // Rekurencyjnie dodajemy
    // do C lewe poddrzewo
    s_copy(A^.left, C);
    // Rekurencyjnie dodajemy
    // do C prawe poddrzewo
    s_copy(A^.right, C);
  end;
end;

// Procedura tworzy sumę
// zbiorów A i B w C
//----------------------
procedure s_union(A, B : PRBTnode;
                 var C : PRBTnode);
begin
  // Czyścimy C
  s_clear(C);
  // W C umieszczamy A
  s_copy(A, C);
  // Dodajemy B do C
  s_copy(B, C);
end;

// Procedura kopiuje do C
// te elementy A, które
// również są w B
//-----------------------
procedure s_icopy(A, B : PRBTnode;
                 var C : PRBTnode);
begin
  if A <> @S then
  begin
    if s_isin(B, A^.key) <> nil then
      s_add(C, A^.key);
    s_icopy(A^.left, B, C);
    s_icopy(A^.right, B, C);
  end;
end;

// Procedura tworzy w C
// iloczyn zbiorów A i B
//----------------------
procedure s_intersection(A, B : PRBTnode;
                        var C : PRBTnode);
begin
  // Czyścimy C
  s_clear(C);
  // Tworzymy iloczyn zbiorów
  s_icopy(A, B, C);
end;

// Procedura kopiuje do C
// te elementy A, których
// nie ma w B
//-----------------------
procedure s_dcopy(A, B : PRBTnode;
                 var C : PRBTnode);
begin
  if A <> @S then
  begin
    if s_isin(B, A^.key) = nil then
      s_add(C, A^.key);
    s_dcopy(A^.left, B, C);
    s_dcopy(A^.right, B, C);
  end;
end;

// Procedura tworzy w C
// różnicę zbiorów A i B
//----------------------
procedure s_difference(A, B : PRBTnode;
                      var C : PRBTnode);
begin
  // Czyścimy C
  s_clear(C);
  // Tworzymy różnicę zbiorów
  s_dcopy(A, B, C);
end;

// Funkcja zwraca true,
// jeśli zbiór A jest
// podzbiorem B
//---------------------
function s_subset(A, B : PRBTnode)
                       : boolean;
begin
  if A = @S then Exit(true);
  if s_isin(B, A^.key) = nil then
    Exit(false);
  s_subset := s_subset(A^.left, B) and
              s_subset(A^.right, B);
end;

// Procedura zlicza rekurencyjnie
// węzły w drzewie
//-------------------------------
procedure s_cnt(A : PRBTnode;
          var cnt : integer);
begin
  if A <> @S then
  begin
    // Zliczamy węzeł bieżący
    inc(cnt);
    // Rekurencyjnie liczymy węzły
    // w lewym poddrzewie
    s_cnt(A^.left, cnt);
    // Rekurencyjnie liczymy węzły
    // w prawym poddrzewie
    s_cnt(A^.right, cnt);
  end;
end;

// Funkcja oblicza liczbę
// węzłów w drzewie
//-----------------------
function s_size(A : PRBTnode)
                  : integer;
var
  // Licznik węzłów
  cnt : integer;
begin
  // Zerujemy licznik
  cnt := 0;
  // Zliczamy węzły
  s_cnt(A, cnt);
  // Zwracamy wynik
  s_size := cnt;
end;

// Funkcja zwraca true,
// jeśli zbiór jest pusty
//-----------------------
function s_empty(A : PRBTnode)
                   : boolean;
begin
  s_empty := A = @S;
end;

// Procedura rekurencyjnie
// wyświetla zawartość drzewa
//---------------------------
procedure s_print(A : PRBTnode);
begin
  if A <> @S then
  begin
    s_print(A^.left);
    write(A^.key, ' ');
    s_print(A^.right);
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  A, B, C, D : PRBTnode;
  i, x       : integer;

begin
  randomize;
  // Tworzymy puste zbiory
  A := @S;
  B := @S;
  C := @S;
  D := @S;
  // Do zbioru A dodajemy 10 losowych elementów
  for i := 1 to 10 do
    s_add(A, -20+random(41));
  // Do zbioru B dodajemy 15 losowych elementów
  for i := 1 to 15 do
    s_add(B, -20+random(41));
  // Wyświetlamy je
  writeln('A:');
  s_print(A); writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  writeln('B:');
  s_print (B); writeln;
  writeln('SIZE OF B IS ', s_size(B));
  // Suma zbiorów
  writeln;
  writeln('UNION OF A AND B:');
  s_union(A, B, C);
  s_print(C); writeln;
  writeln('SIZE OF UNION IS ', s_size(C));
  // Iloczyn zbiorów
  writeln;
  writeln('INTERSECTION OF A AND B:');
  s_intersection(A, B, C);
  s_print(C); writeln;
  writeln('SIZE OF INTERSECTION IS ', s_size(C));
  // Różnica zbiorów
  writeln;
  writeln('DIFFERENCE OF A AND B:');
  s_difference(A, B, C);
  s_print(C); writeln;
  writeln('SIZE OF DIFFERENCE IS ', s_size(C));
  // Podzbiór
  // Kopiujemy A do C
  s_union(A, A, C);
  // Usuwamy 7 elementów
  for i := 1 to 7 do
    s_remove(C, -20+random(41));
  writeln;
  writeln('IS:');
  s_print(C);
  writeln(' SUBSET OF A?');
  writeln(s_subset(C, A));
  s_difference(B, A, C);
  // Usuwamy 12 elementów
  for i := 1 to 12 do
    s_remove(C, -20+random(41));
  writeln;
  writeln('IS:');
  s_print(C);
  writeln(' SUBSET OF A?');
  writeln(s_subset(C, A));
  // Usuwanie
  writeln;
  write('FROM A WE REMOVE');
  for i := 1 to 5 do
  begin
    x := -20+random(41);
    write(x:4);
    s_remove(A, x);
  end;
  writeln;
  writeln('A:'); s_print(A); writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  // Sprawdzamy obecność wybranych
  // elementów w B
  for i := 1 to 10 do
  begin
    x := -20+random(41);
    write('IS ELEMENT', x:4, ' IN SET B? ');
    if s_isin(B, x) <> nil then
      writeln('YES')
    else
      writeln('NO');
  end;
  writeln;
  // Sprawdzenie testu na zbiór pusty
  writeln('IS SET A EMPTY?');
  writeln(s_empty(A));
  writeln;
  writeln('IS INTERSECTION OF A AND DIFFERENCE' +
          ' OF B AND A EMPTY?');
  s_difference(B, A, C);
  s_intersection(A, C, D);
  writeln(s_empty(D));
  writeln;
  // Usuwamy zbiory
  s_clear(A);
  s_clear(B);
  s_clear(C);
  s_clear(D);
end.

// Zbiory zaimplementowane
// w drzewach czerwono-czarnych
// Data: 9.07.2014
// (C)2014 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definicja węzła drzewa
// czerwono-czarnego
struct RBTnode
{
  RBTnode * up;
  RBTnode * left;
  RBTnode * right;
  int key;
  char color;
};

// Zmienne globalne
RBTnode S = {&S, &S, &S, 0, 'B'};

// Procedury obsługi drzew czerwono-czarnych

// Wykonuje rotację w lewo
// względem A
//------------------------
void rot_L(RBTnode * & root,
           RBTnode * A)
{
  RBTnode * B, * p;

  B = A->right;
  if(B != &S)
  {
    p = A->up;
    A->right = B->left;
    if(A->right != &S)
      A->right->up = A;
    B->left = A;
    B->up = p;
    A->up = B;
    if(p != &S)
    {
      if(p->left == A)
        p->left = B;
      else
        p->right = B;
    }
    else root = B;
  }
}

// Wykonuje rotację w prawo
// względem A
//-------------------------
void rot_R(RBTnode * & root,
           RBTnode * A)
{
  RBTnode * B, * p;

  B = A->left;
  if(B != &S)
  {
    p = A->up;
    A->left = B->right;
    if(A->left != &S)
      A->left->up = A;
    B->right = A;
    B->up = p;
    A->up = B;
    if(p != &S)
    {
      if(p->left == A)
        p->left = B;
      else
        p->right = B;
    }
    else root = B;
  }
}

// Wstawia do drzewa węzeł
// o kluczu k
//------------------------
void insert_rbt(RBTnode * & root,
                int k)
{
  RBTnode * X, * Y;

  // Tworzymy nowy węzeł
  X = new RBTnode;
  // Inicjujemy pola
  X->left  = &S;
  X->right = &S;
  X->up    = root;
  X->key   = k;
  // X staje się korzeniem
  if(X->up == &S)
    root = X;
  else
    // Szukamy liścia do zastąpienia
    // przez X
    while(true)
    {
      if(k < X->up->key)
      {
        if(X->up->left == &S)
        {
          // X zastępuje lewy liść
          X->up->left = X;
          break;
        }
        X->up = X->up->left;
      }
      else
      {
        if(X->up->right == &S)
        {
          // X zastępuje prawy liść
          X->up->right = X;
          break;
        }
        X->up = X->up->right;
      }
    }
  // Węzeł kolorujemy na czerwono
  X->color = 'R';
  while((X != root) &&
        (X->up->color == 'R'))
  {
    if(X->up == X->up->up->left)
    {
      // Y -> wujek X
      Y = X->up->up->right;
      // Przypadek 1
      if(Y->color == 'R')
      {
        X->up->color = 'B';
        Y->color = 'B';
        X->up->up->color = 'R';
        X = X->up->up;
        continue;
      }
      // Przypadek 2
      if(X == X->up->right)
      {
        X = X->up;
        rot_L(root, X);
      }
      // Przypadek 3
      X->up->color = 'B';
      X->up->up->color = 'R';
      rot_R(root, X->up->up);
      break;
    }
    else
    { // Przypadki lustrzane
      Y = X->up->up->left;
      // Przypadek 1
      if(Y->color == 'R')
      {
        X->up->color = 'B';
        Y->color = 'B';
        X->up->up->color = 'R';
        X = X->up->up;
        continue;
      }
      // Przypadek 2
      if(X == X->up->left)
      {
        X = X->up;
        rot_R(root, X);
      }
      // Przypadek 3
      X->up->color = 'B';
      X->up->up->color = 'R';
      rot_L(root, X->up->up);
      break;
    }
  }
  root->color = 'B';
}

// Wyszukuje najmniejszy węzeł
// w poddrzewie o korzeniu p
//----------------------------
RBTnode * min_rbt(RBTnode * p)
{
  if(p != &S)
    while(p->left != &S)
      p = p->left;
  return p;
}

// Zwraca następnik p
//-------------------
RBTnode * succ_rbt(RBTnode * p)
{
  RBTnode * r;

  if(p != &S)
  {
    if(p->right != &S)
      return min_rbt(p->right);
    else
    {
      r = p->up;
      while((r != &S) &&
            (p == r->right))
      {
        p = r;
        r = r->up;
      }
      return r;
    }
  }
  return &S;
}

// Usuwa z drzewa węzeł X
//-----------------------
void remove_rbt(RBTnode * & root,
                RBTnode * X)
{
  RBTnode * W, * Y, * Z;

  if((X->left == &S) ||
     (X->right == &S))
    Y = X;
  else
    Y = succ_rbt(X);
  if(Y->left != &S)
    Z = Y->left;
  else
    Z = Y->right;
  Z->up = Y->up;
  if(Y->up == &S)
    root = Z;
  else
    if(Y == Y->up->left)
      Y->up->left  = Z;
    else
      Y->up->right = Z;
  if(Y != X)
    X->key = Y->key;
  // Naprawa struktury drzewa
  // czerwono-czarnego
  if(Y->color == 'B')
  {
    while((Z != root) &&
          (Z->color == 'B'))
      if(Z == Z->up->left)
      {
        W = Z->up->right;
        if(W->color == 'R')
        { // Przypadek 1
          W->color = 'B';
          Z->up->color = 'R';
          rot_L(root, Z->up);
          W = Z->up->right;
        }
        if((W->left->color == 'B') &&
           (W->right->color == 'B'))
        { // Przypadek 2
          W->color = 'R';
          Z = Z->up;
          continue;
        }
        if(W->right->color == 'B')
        { // Przypadek 3
          W->left->color = 'B';
          W->color = 'R';
          rot_R(root, W);
          W = Z->up->right;
        }
        // Przypadek 4
        W->color = Z->up->color;
        Z->up->color = 'B';
        W->right->color = 'B';
        rot_L(root, Z->up);
        // To spowoduje zakończenie pętli
        Z = root;
      }
      else
      { // Przypadki lustrzane
        W = Z->up->left;
        if(W->color == 'R')
        { // Przypadek 1
          W->color = 'B';
          Z->up->color = 'R';
          rot_R(root, Z->up);
          W = Z->up->left;
        }
        if((W->left->color == 'B') &&
           (W->right->color == 'B'))
        { // Przypadek 2
          W->color = 'R';
          Z = Z->up;
          continue;
        }
        if(W->left->color == 'B')
        { // Przypadek 3
          W->right->color = 'B';
          W->color = 'R';
          rot_L(root, W);
          W = Z->up->left;
        }
        // Przypadek 4
        W->color = Z->up->color;
        Z->up->color = 'B';
        W->left->color = 'B';
        rot_R(root, Z->up);
        // To spowoduje zakończenie pętli
        Z = root;
      }
  }
  Z->color = 'B';
  delete Y;
}

// Procedury obsługi zbioru

// Szuka w drzewie węzła
// o danej wartości klucza x.
// Jeśli węzeł zostanie znaleziony,
// to zwraca jego adres.
// Inaczej zwraca wskazanie puste.
//---------------------------------
RBTnode * s_isin(RBTnode * A,
                 int x)
{
  while(A != &S)
  {
    // Węzeł znaleziony
    if(A->key == x) return A;
    if(x < A->key)
      A = A->left;
    else
      A = A->right;
  }
  // Węzeł nieznaleziony
  return NULL;
}

// Dodaje do drzewa nowy węzeł,
// jeśli w drzewie takiego węzła
// jeszcze nie ma
//------------------------------
void s_add(RBTnode * & A,
           int x)
{
  if(!s_isin(A, x))
    insert_rbt(A, x);
}

// Wyszukuje w drzewie węzeł o kluczu x i usuwa go
//------------------------------------------------
void s_remove(RBTnode * & A,
              int x)
{
  // Szukamy węzła o kluczu x
  RBTnode * p = s_isin(A, x);
  if(p) remove_rbt(A, p);
}

// Usuwa wszystkie węzły z drzewa
//-------------------------------
void s_clear(RBTnode * & A)
{
  if(A != &S)
  {
    // Rekurencyjnie usuwamy
    // lewe poddrzewo
    s_clear(A->left);
    // Rekurencyjnie usuwamy
    // prawe poddrzewo
    s_clear(A->right);
    // Usuwamy węzeł
    delete A;
    A = &S;
  }
}

// Procedura kopiuje elementy
// z drzewa A do C
//---------------------------
void s_copy(RBTnode * A,
            RBTnode * & C)
{
  if(A != &S)
  {
    // Dodajemy do C klucz
    // bieżącego węzła
    s_add(C, A->key);
    // Rekurencyjnie dodajemy do C
    // lewe poddrzewo
    s_copy(A->left, C);
    // Rekurencyjnie dodajemy do C
    // prawe poddrzewo
    s_copy(A->right, C);
  }
}

// Procedura tworzy sumę
// zbiorów A i B w C
//----------------------
void s_union(RBTnode * A,
             RBTnode * B,
             RBTnode * & C)
{
  // Czyścimy C
  s_clear (C);
  // W C umieszczamy A
  s_copy(A, C);
  // Dodajemy B do C
  s_copy(B, C);
}

// Procedura kopiuje do C
// te elementy A, które
// również są w B
//-----------------------
void s_icopy(RBTnode * A,
             RBTnode * B,
             RBTnode * & C)
{
  if(A != &S)
  {
    if(s_isin(B, A->key))
      s_add(C, A->key);
    s_icopy(A->left, B, C);
    s_icopy(A->right, B, C);
  }
}

// Procedura tworzy w C iloczyn
// zbiorów A i B
//-----------------------------
void s_intersection(RBTnode * A,
                    RBTnode * B,
                    RBTnode * & C)
{
  // Czyścimy C
  s_clear(C);
  // Tworzymy iloczyn zbiorów
  s_icopy(A, B, C);
}

// Procedura kopiuje do C te elementy A,
// których nie ma w B
//--------------------------------------
void s_dcopy(RBTnode * A,
             RBTnode * B,
             RBTnode * & C)
{
  if(A != &S)
  {
    if(!s_isin(B, A->key))
      s_add(C, A->key);
    s_dcopy(A->left, B, C);
    s_dcopy(A->right, B, C);
  }
}

// Procedura tworzy w C różnicę
// zbiorów A i B
//-----------------------------
void s_difference(RBTnode * A,
                  RBTnode * B,
                  RBTnode * & C)
{
  // Czyścimy C
  s_clear(C);
  // Tworzymy różnicę zbiorów
  s_dcopy(A, B, C);
}

// Funkcja zwraca true, jeśli zbiór A
// jest podzbiorem B
//-----------------------------------
bool s_subset(RBTnode * A,
              RBTnode * B)
{
  if(A == &S) return true;
  if(!s_isin(B, A->key)) return false;
  return s_subset(A->left, B) &&
         s_subset(A->right, B);
}

// Procedura zlicza rekurencyjnie
// węzły w drzewie
//-------------------------------
void s_cnt(RBTnode * A,
           int & cnt)
{
  if(A != &S)
  {
    // Zliczamy węzeł bieżący
    cnt++;
    // Rekurencyjnie liczymy węzły
    // w lewym poddrzewie
    s_cnt(A->left, cnt);
    // Rekurencyjnie liczymy węzły
    // w prawym poddrzewie
    s_cnt(A->right, cnt);
  }
}

// Funkcja oblicza liczbę
// węzłów w drzewie
//-----------------------
int s_size(RBTnode * A)
{
  // Zerujemy licznik
  int cnt = 0;
  // Zliczamy węzły
  s_cnt(A, cnt);
  // Zwracamy wynik
  return cnt;
}

// Funkcja zwraca true,
// jeśli zbiór jest pusty
//-----------------------
bool s_empty(RBTnode * A)
{
  return A == &S;
}

// Procedura rekurencyjnie wyświetla
// zawartość drzewa
//----------------------------------
void s_print(RBTnode * A)
{
  if(A != &S)
  {
    s_print(A->left);
    cout << A->key << " ";
    s_print(A->right);
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  RBTnode *A, *B, *C, *D;
  int i, x;

  srand(time(NULL));

  // Tworzymy puste zbiory
  A = B = C = D = &S;
  // Do zbioru A dodajemy 10
  // losowych elementów
  for(i = 0; i < 10; i++)
    s_add(A, -20+(rand() % 41));
  // Do zbioru B dodajemy 15
  // losowych elementów
  for(i = 0; i < 15; i++)
    s_add(B, -20+(rand() % 41));
  // Wyświetlamy je
  cout << "A:" << endl;
  s_print(A);
  cout << endl << "SIZE OF A IS "
       << s_size(A) << endl
       << endl << "B:" << endl;
  s_print (B);
  cout << endl << "SIZE OF B IS "
       << s_size(B) << endl << endl
  // Suma zbiorów
       << "UNION OF A AND B:" << endl;
  s_union(A, B, C);
  s_print(C);
  cout << endl << "SIZE OF UNION IS "
       << s_size(C) << endl << endl
  // Iloczyn zbiorów
       << "INTERSECTION OF A AND B:" << endl;
  s_intersection(A, B, C);
  s_print(C);
  cout << endl << "SIZE OF INTERSECTION IS "
       << s_size(C) << endl << endl
  // Różnica zbiorów
       << "DIFFERENCE OF A AND B:" << endl;
  s_difference(A, B, C);
  s_print(C);
  cout << endl << "SIZE OF DIFFERENCE IS "
       << s_size(C) << endl << endl;
  // Podzbiór
  // Kopiujemy A do C
  s_union(A, A, C);
  // Usuwamy 7 elementów
  for(i = 0; i < 7; i++)
    s_remove(C, -20+(rand() % 41));
  cout << "IS:" << endl;
  s_print(C);
  cout << " SUBSET OF A?" << endl
       << (s_subset(C, A) ? "YES": "NO")
       << endl << endl;
  s_difference(B, A, C);
  // Usuwamy 12 elementów
  for(i = 0; i < 12; i++)
    s_remove(C, -20+(rand() % 41));
  cout << "IS:" << endl;
  s_print(C);
  cout << " SUBSET OF A?" << endl
       << (s_subset(C, A) ? "YES": "NO")
       << endl << endl
  // Usuwanie
       << "FROM A WE REMOVE";
  for(i = 0; i < 5; i++)
  {
    x = -20+(rand() % 41);
    cout << setw(4) << x;
    s_remove(A, x);
  }
  cout << endl << "A:" << endl;
  s_print(A);
  cout << endl << "SIZE OF A IS "
       << s_size(A) << endl << endl;
  // Sprawdzamy obecność wybranych
  // elementów w B
  for(i = 0; i < 10; i++)
  {
    x = -20+(rand() % 41);
    cout << "IS ELEMENT" << setw(4)
         << x << " IN SET B? "
         << (s_isin(B, x) ? "YES": "NO")
         << endl;
  }
  // Sprawdzenie testu na zbiór pusty
  cout << endl << "IS SET A EMPTY?" << endl
       << (s_empty(A) ? "YES": "NO")
       << endl << endl
       << "IS INTERSECTION OF A AND DIFFERENCE"
          " OF B AND A EMPTY?" << endl;
  s_difference(B, A, C);
  s_intersection(A, C, D);
  cout << (s_empty(D) ? "YES": "NO")
       << endl << endl;
  // Usuwamy tablice dynamiczne w zbiorach
  s_clear(A);
  s_clear(B);
  s_clear(C);
  s_clear(D);
  return 0;
}

' Zbiory zaimplementowane
' w drzewach czerwono-czarnych
' Data: 9.07.2014
' (C)2014 mgr Jerzy Wałaszek
'-----------------------------

' Definicja węzła drzewa czerwono-czarnego
Type RBTnode
  up    As RBTnode Ptr
  left  As RBTnode Ptr
  right As RBTnode Ptr
  key   As Integer
  color As String * 1
End Type

' Zmienne globalne

Dim Shared As RBTnode S _
    => (@S, @S, @S, 0, "B")

' Procedury obsługi drzew czerwono-czarnych

' Wykonuje rotację w lewo względem A
'-----------------------------------
Sub rot_L(ByRef root As RBTnode Ptr, _
          ByVal A As RBTnode Ptr)

  Dim As RBTnode Ptr B, p

  B = A->Right
  If B <> @S Then
    p = A->up
    A->right = B->Left
    If A->right <> @S then _
      A->right->up = A
    B->left = A
    B->up = p
    A->up = B
    If p <> @S Then
      If p->left = A then
        p->left = B
      Else
        p->right = B
      End If
    Else
      root = B
    End If
  End If
End Sub

' Wykonuje rotację w prawo względem A
'------------------------------------
Sub rot_R(ByRef root As RBTnode Ptr, _
          ByVal A As RBTnode Ptr)

  Dim As RBTnode Ptr B, p

  B = A->Left
  If B <> @S Then
    p = A->up
    A->left = B->Right
    If A->left <> @S Then _
      A->left->up = A
    B->right = A
    B->up = p
    A->up = B
    If p <> @S Then
      If p->left = A Then
        p->left = B
      Else
        p->right = B
      End If
    Else
      root = B
    End If
  End If
End Sub

' Wstawia do drzewa węzeł o kluczu k
'-----------------------------------
Sub insert_rbt(ByRef root As RBTnode Ptr, _
               ByVal k As Integer)

  Dim As RBTnode Ptr X, Y

  X = new RBTnode  ' Tworzymy nowy węzeł
  X->left  = @S    ' Inicjujemy pola
  X->right = @S
  X->up    = root
  X->key   = k
  If X->up = @S Then
  	  root = X ' X staje się korzeniem
  Else
    ' Szukamy liścia do zastąpienia przez X
    Do
      If k < X->up->key Then
        If X->up->left = @S Then
          ' X zastępuje lewy liść
          X->up->left = X
          Exit Do
        End If
        X->up = X->up->Left
      Else
        If X->up->right = @S Then
          ' X zastępuje prawy liść
          X->up->right = X
          Exit Do
        End If
        X->up = X->up->Right
      End If
    Loop
  End If
  ' Węzeł kolorujemy na czerwono
  X->color = "R"
   While (X <> root) AndAlso _
         (X->up->color = "R")
    If X->up = X->up->up->Left Then
      Y = X->up->up->Right ' Y -> wujek X
      If Y->color = "R" Then ' Przypadek 1
        X->up->color = "B"
        Y->color = "B"
        X->up->up->color = "R"
        X = X->up->up
        Continue While
      End If
      If X = X->up->Right Then ' Przypadek 2
        X = X->up
        rot_L(root, X)
      End If
      X->up->color = "B" ' Przypadek 3
      X->up->up->color = "R"
      rot_R(root, X->up->up)
      Exit While
    Else ' Przypadki lustrzane
      Y = X->up->up->Left
      If Y->color = "R" Then ' Przypadek 1
        X->up->color = "B"
        Y->color = "B"
        X->up->up->color = "R"
        X = X->up->up
        Continue While
      End If
      if X = X->up->Left Then ' Przypadek 2
        X = X->up
        rot_R(root, X)
      End If
      X->up->color = "B" ' Przypadek 3
      X->up->up->color = "R"
      rot_L(root, X->up->up)
      Exit While
    End If
  Wend
  root->color = "B"
End Sub

' Wyszukuje najmniejszy węzeł w poddrzewie
' o korzeniu p
'-----------------------------------------
Function min_rbt(ByVal p As RBTnode Ptr) _
                         As RBTnode Ptr
  If p <> @S Then
    While p->left <> @S
      p = p->Left
    Wend
  End If
  Return p
End Function

' Zwraca następnik p
'-------------------
Function succ_rbt(ByVal p As RBTnode Ptr) _
                          As RBTnode Ptr
  Dim As RBTnode Ptr r

  If p <> @S Then
    If p->right <> @S Then
      Return min_rbt(p->right)
    Else
      r = p->up
      while (r <> @S) AndAlso (p = r->right)
        p = r
        r = r->up
      Wend
      Return r
    End If
  End If
  Return @S
End Function

' Usuwa z drzewa węzeł X
'-----------------------
Sub remove_rbt(ByRef root As RBTnode Ptr, _
                  ByVal X As RBTnode Ptr)

  Dim As RBTnode Ptr W, Y, Z

  If (X->left = @S) OrElse _
     (X->right = @S) Then
    Y = X
  Else
    Y = succ_rbt(X)
  End If
  If Y->left <> @S Then
    Z = Y->Left
  Else
    Z = Y->Right
  End If
  Z->up = Y->up
  If Y->up = @S Then
    root = Z
  ElseIf Y = Y->up->Left Then
    Y->up->Left = Z
  Else
    Y->up->right = Z
  End If
  If Y <> X Then X->key = Y->key

  ' Naprawa struktury drzewa
  ' czerwono-czarnego
  If Y->color = "B" Then
    While (Z <> root) AndAlso _
          (Z->color = "B")
      If Z = Z->up->Left Then
        W = Z->up->Right
        ' Przypadek 1
        If W->color = "R" Then
          W->color = "B"
          Z->up->color = "R"
          rot_L(root, Z->up)
          W = Z->up->Right
        End If
        ' Przypadek 2
        If (W->left->color = "B") AndAlso _
           (W->right->color = "B") Then
          W->color = "R"
          Z = Z->up
          Continue While
        End If
        ' Przypadek 3
        If W->right->color = "B" Then
          W->left->color = "B"
          W->color = "R"
          rot_R(root, W)
          W = Z->up->Right
        End If
        ' Przypadek 4
        W->color = Z->up->Color
        Z->up->color = "B"
        W->right->color = "B"
        rot_L(root, Z->up)
        ' To spowoduje zakończenie pętli
        Z = root
      Else ' Przypadki lustrzane
        W = Z->up->Left
        ' Przypadek 1
        If W->color = "R" Then
          W->color = "B"
          Z->up->color = "R"
          rot_R(root, Z->up)
          W = Z->up->Left
        End If
        ' Przypadek 2
        If (W->left->color = "B") AndAlso _
           (W->right->color = "B") Then
          W->color = "R"
          Z = Z->up
          Continue While
        End If
        ' Przypadek 3
        If W->left->color = "B" Then
          W->right->color = "B"
          W->color = "R"
          rot_L(root, W)
          W = Z->up->Left
        End If
        ' Przypadek 4
        W->color = Z->up->Color
        Z->up->color = "B"
        W->left->color = "B"
        rot_R(root, Z->up)
        ' To spowoduje zakończenie pętli
        Z = root
      End If
    Wend
  End If
  Z->color = "B"
  Delete Y
End Sub

' Procedury obsługi zbioru

' Szuka w drzewie węzła o danej wartości
' klucza x. Jeśli węzeł zostanie znaleziony,
' to zwraca jego adres. Inaczej zwraca
' wskazanie puste.
'-------------------------------------------
Function s_isin(ByVal A As RBTnode Ptr, _
                ByVal x As Integer) _
                        As RBTnode Ptr
  While A <> @S
    ' Węzeł znaleziony
    If A->key = x Then Return A
    If x < A->key Then
      A = A->Left
    Else
      A = A->Right
    End If
  Wend
  Return 0 ' Węzeł nieznaleziony
End Function

' Dodaje do drzewa nowy węzeł,
' jesli w drzewie takiego węzła
' jeszcze nie ma
'------------------------------
Sub s_add(ByRef A As RBTnode Ptr, _
          ByVal x As Integer)
  If s_isin(A, x) = 0 Then insert_rbt(A, x)
End Sub

' Wyszukuje w drzewie węzeł o kluczu x
' i usuwa go
'-------------------------------------
Sub s_remove(ByRef A As RBTnode Ptr, _
             ByVal x As Integer)
  ' Szukamy węzła o kluczu x
  Dim As RBTnode Ptr p = s_isin (A, x)
  If p Then remove_rbt(A, p)
End Sub

' Usuwa wszystkie węzły z drzewa
'-------------------------------
Sub s_clear(ByRef A As RBTnode Ptr)
  If A <> @S Then
    ' Rekurencyjnie usuwamy lewe poddrzewo
    s_clear(A->left)
    ' Rekurencyjnie usuwamy prawe poddrzewo
    s_clear(A->right)
    Delete A ' Usuwamy węzeł
    A = @S
  End If
End Sub

' Procedura kopiuje elementy z drzewa A do C
'-------------------------------------------
Sub s_copy(Byval A As RBTnode Ptr, _
           ByRef C As RBTnode Ptr)
  If A <> @S Then
    ' Dodajemy do C klucz bieżącego węzła
    s_add(C, A->key)
    ' Rekurencyjnie dodajemy do C
    ' lewe poddrzewo
    s_copy(A->left, C)
    ' Rekurencyjnie dodajemy do C
    ' prawe poddrzewo
    s_copy(A->right, C)
  End If
End Sub

' Procedura tworzy sumę zbiorów A i B w C
'----------------------------------------
Sub s_union(ByVal A As RBTnode Ptr, _
            ByVal B As RBTnode Ptr, _
            ByRef C As RBTnode Ptr)
  s_clear(C) ' Czyścimy C
  s_copy(A, C) ' W C umieszczamy A
  s_copy(B, C) ' Dodajemy B do C
End Sub

' Procedura kopiuje do C te elementy A,
' które również są w B
'--------------------------------------
Sub s_icopy(ByVal A As RBTnode Ptr, _
            ByVal B As RBTnode Ptr, _
            ByRef C As RBTnode Ptr)
  If A <> @S Then
    If s_isin(B, A->key) Then _
      s_add(C, A->key)
    s_icopy(A->left, B, C)
    s_icopy(A->right, B, C)
  End If
End Sub

' Procedura tworzy w C iloczyn zbiorów A i B
'-------------------------------------------
Sub s_intersection(ByVal A As RBTnode Ptr, _
                   ByVal B As RBTnode Ptr, _
                   ByRef C As RBTnode Ptr)
  ' Czyścimy C
  s_clear(C)
  ' Tworzymy iloczyn zbiorów
  s_icopy(A, B, C)
End Sub

' Procedura kopiuje do C te elementy A,
' których nie ma w B
'--------------------------------------
Sub s_dcopy(ByVal A As RBTnode Ptr, _
            ByVal B As RBTnode Ptr, _
            ByRef C As RBTnode Ptr)
  If A <> @S Then
    If s_isin(B, A->key) = 0 Then _
      s_add(C, A->key)
    s_dcopy(A->left, B, C)
    s_dcopy(A->right, B, C)
  End If
End Sub

' Procedura tworzy w C różnicę zbiorów A i B
'-------------------------------------------
Sub s_difference(ByVal A As RBTnode Ptr, _
                 ByVal B As RBTnode Ptr, _
                 ByRef C As RBTnode Ptr)
  ' Czyścimy C
  s_clear(C)
  ' Tworzymy różnicę zbiorów
  s_dcopy(A, B, C)
End Sub

' Funkcja zwraca true, jeśli zbiór A
' jest podzbiorem B
' Inaczej zwraca false
'-----------------------------------
Function s_subset(ByVal A As RBTnode Ptr, _
                  ByVal B As RBTnode Ptr) _
                          As Integer
  If A = @S Then Return -1
  If s_isin(B, A->key) = 0  Then Return 0
  Return s_subset(A->left, B) AndAlso _
         s_subset(A->right, B)
End Function

' Procedura zlicza rekurencyjnie węzły
' w drzewie
'-------------------------------------
Sub s_cnt(ByVal A As RBTnode Ptr, _
          ByRef cnt As Integer)
  If A <> @S Then
    ' Zliczamy węzeł bieżący
    cnt += 1
    ' Rekurencyjnie liczymy węzły
    ' w lewym poddrzewie
    s_cnt(A->left, cnt)
    ' Rekurencyjnie liczymy węzły
    ' w prawym poddrzewie
    s_cnt(A->right, cnt)
  End If
End Sub

' Funkcja oblicza liczbę węzłów w drzewie
'----------------------------------------
Function s_size(ByVal A As RBTnode Ptr) _
                        As Integer
  ' Zerujemy licznik
  Dim As Integer cnt = 0
  s_cnt(A, cnt) ' Zliczamy węzły
  Return cnt ' Zwracamy wynik
End Function

' Funkcja zwraca true,
' jeśli zbiór jest pusty
'-----------------------
Function s_empty(ByVal A As RBTnode Ptr) _
                         As Integer
  Return A = @S
End Function

' Procedura rekurencyjnie wyświetla
' zawartość drzewa
'----------------------------------
Sub s_print(byval A As RBTnode Ptr)
  If A <> @S Then
    s_print(A->left)
    Print Using "& ";A->key;
    s_print(A->right)
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As RBTnode Ptr A, B, C, D
Dim As Integer i, x

Randomize
' Tworzymy puste zbiory
A = @S
B = @S
C = @S
D = @S
' Do zbioru A dodajemy
' 10 losowych elementów
For i = 1 To 10
  s_add(A, -20+Int(rnd()*41))
Next
' Do zbioru B dodajemy
' 15 losowych elementów
For i = 1 To 15
  s_add(B, -20+Int(Rnd()*41))
Next
' Wyświetlamy je
Print "A:"
s_print(A): Print
Print "SIZE OF A IS";s_size(A)
Print
Print "B:"
s_print(B): Print
Print "SIZE OF B IS";s_size(B)
Print
' Suma zbiorów
Print "UNION OF A AND B:"
s_union(A, B, C)
s_print(C): Print
Print "SIZE OF UNION IS";s_size(C)
Print
' Iloczyn zbiorów
Print "INTERSECTION OF A AND B:"
s_intersection(A, B, C)
s_print(C): Print
Print "SIZE OF INTERSECTION IS";s_size(C)
Print
' Różnica zbiorów
Print "DIFFERENCE OF A AND B:"
s_difference(A, B, C)
s_print(C): Print
Print "SIZE OF DIFFERENCE IS";s_size(C)
Print
' Podzbiór
' Kopiujemy A do C
s_union(A, A, C)
' Usuwamy 7 elementów
For i = 1 To 7
  s_remove(C, -20+Int(Rnd()*41))
Next
Print "IS:";
s_print(C)
Print " SUBSET OF A?"
If s_subset(C, A) Then
  Print "YES"
Else
  Print "NO"
End If
Print
s_difference(B, A, C)
' Usuwamy 12 elementów
For i = 1 To 12
  s_remove(C, -20+Int(Rnd()*41))
Next
Print "IS:"
s_print(C)
Print " SUBSET OF A?"
If s_subset(C, A) Then
  Print "YES"
Else
  Print "NO"
End If
Print
' Usuwanie
Print "FROM A WE REMOVE";
For i = 1 To 5
  x = -20+Int(Rnd()*41)
  Print Using "& ";x;
  s_remove(A, x)
Next
Print
Print "A:"
s_print(A): Print
Print "SIZE OF A IS";s_size(A)
Print
' Sprawdzamy obecność wybranych
' elementów w B
For i = 1 To 10
  x = -20+Int(Rnd()*41)
  Print Using "IS ELEMENT#### IN SET B? ";x;
  If s_isin(B, x) Then
  	 Print "YES"
  Else
  	 Print "NO"
  End If
Next
Print
' Sprawdzenie testu na zbiór pusty
Print "IS SET A EMPTY?"
If s_empty(A) Then
  Print "YES"
Else
  Print "NO"
End If
Print
Print "IS INTERSECTION OF A AND " + _
      "DIFFERENCE OF B AND A EMPTY?"
s_difference(B, A, C)
s_intersection(A, C, C)
If s_empty(C) Then
  Print "YES"
Else
  Print "NO"
End If
Print
' Usuwamy zbiory
s_clear(A)
s_clear(B)
s_clear(C)
s_clear(D)
End