type
  PAVLnode = ^AVLnode;
  AVLnode  = record
    up    : PAVLnode;
    left  : PAVLnode;
    right : PAVLnode;
    key   : typ_danych;
    bf    : integer;
    // opcjonalnie
    Data: typ_danych;
  end;

struct AVLnode
{
  AVLnode * up;
  AVLnode * left;
  AVLnode * right;
  typ_danych key;
  int bf;
  // opcjonalnie
  typ_danych data
};

Type AVLnode
  up As AVLnode Ptr
  left As AVLnode Ptr
  right As AVLnode Ptr
  key As typ_danych
  bf As Integer
  ' opcjonalnie
  data As typ_danych
End Type

// Drzewo AVL
// Data: 22.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program AVL;

// Definicja typu węzłów
// drzewa AVL
//----------------------
type
  PAVLnode = ^AVLnode;
  AVLnode  = record
    up    : PAVLnode;
    left  : PAVLnode;
    right : PAVLnode;
    key   : integer;
    bf    : integer;
  end;

// Zmienne globalne
//-----------------

// łańcuchy do znaków ramek
var
  cr, cl, cp : string;

// Procedura wypisuje drzewo
//--------------------------
procedure print_bt(sp, sn : string;
                  v : PAVLnode);
var
  s : string;
  i : integer;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cr, v^.right);

    s := Copy(sp, 1, length(sp)-2);
    for i := 1 to length(s) do
      write(char(ord(s[i])));
    for i := 1 to length(sn) do
      write(char(ord(sn[i])));
    writeln(v^.key, ':', v^.bf);

    s := sp;
    if sn = cl then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cl, v^.left);
  end;
end;

// Procedura DFS:postorder
// usuwająca drzewo
//------------------------
procedure dfs_release(v : PAVLnode);
begin
  if v <> nil then
  begin
    // usuwamy lewe poddrzewo
    dfs_release(v^.left);
    // usuwamy prawe poddrzewo
    dfs_release(v^.right);
    // usuwamy sam węzeł
    dispose(v);
  end
end;

// Rotacja RR
//-----------
procedure rot_rr(var root : PAVLnode;
                 A : PAVLnode);
var
  B, p : PAVLnode;
begin
  B := A^.right;
  p := A^.up;

  A^.right := B^.left;
  if A^.right <> nil then
    A^.right^.up := A;

  B^.left := A;
  B^.up := p;
  A^.up := B;

  if p <> nil then
  begin
    if p^.left = A then
      p^.left := B
    else
      p^.right := B;
  end
  else
    root := B;

  if B^.bf = -1 then
  begin
    A^.bf := 0;
    B^.bf := 0;
  end
  else
  begin
    A^.bf := -1;
    B^.bf := 1;
  end
end;

// Rotacja LL
//-----------
procedure rot_ll(var root : PAVLnode;
                 A : PAVLnode);
var
  B, p : PAVLnode;
begin
  B := A^.left;
  p := A^.up;

  A^.left := B^.right;
  if A^.left <> nil then
    A^.left^.up := A;

  B^.right := A;
  B^.up := p;
  A^.up := B;

  if p <> nil then
  begin
    if p^.left = A then
      p^.left := B
    else
      p^.right := B;
  end
  else
    root := B;

  if B^.bf = 1 then
  begin
    A^.bf := 0;
    B^.bf := 0;
  end
  else
  begin
    A^.bf := 1;
    B^.bf := -1;
  end
end;

// Rotacja RL
//-----------
procedure rot_rl(var root : PAVLnode;
                 A : PAVLnode);
var
  B, C, p : PAVLnode;
begin
  B := A^.right;
  C := B^.left;
  p := A^.up;

  B^.left := C^.right;
  if B^.left <> nil then
    B^.left^.up := B;

  A^.right := C^.left;
  if A^.right <> nil then
    A^.right^.up := A;

  C^.left := A;
  C^.right := B;
  A^.up := C;
  B^.up := C;
  C^.up := p;

  if p <> nil then
  begin
    if p^.left = A then
      p^.left := C
    else
      p^.right := C;
  end
  else
    root := C;

  if C^.bf = -1 then
    A^.bf :=  1
  else
    A^.bf := 0;

  if C^.bf =  1 then
    B^.bf := -1
  else
    B^.bf := 0;

  C^.bf := 0;
end;

// Rotacja LR
//-----------
procedure rot_lr(var root : PAVLnode;
                 A : PAVLnode);
var
  B, C, p : PAVLnode;
begin
  B := A^.left;
  C := B^.right;
  p := A^.up;

  B^.right := C^.left;
  if B^.right <> nil then
    B^.right^.up := B;

  A^.left := C^.right;
  if A^.left <> nil then
    A^.left^.up := A;

  C^.right := A;
  C^.left := B;
  A^.up := C;
  B^.up := C;
  C^.up := p;

  if p <> nil then
  begin
    if p^.left = A then
      p^.left := C
    else
      p^.right := C;
  end
  else
    root := C;

  if C^.bf =  1 then
    A^.bf := -1
  else
    A^.bf := 0;

  if C^.bf = -1 then
    B^.bf :=  1
  else
    B^.bf := 0;

  C^.bf := 0;
end;

// Wstawia nowy węzeł do drzewa AVL
// root - referencja korzenia
// k    - klucz nowego węzła
//---------------------------------
procedure avl_insert(var root : PAVLnode;
                        k : integer);
var
  w, p, r : PAVLnode;
  t     : boolean;
begin
  // tworzymy dynamicznie nowy węzeł
  new(w);
  // inicjujemy pola
  w^.left  := nil;
  w^.right := nil;
  w^.up    := nil;
  w^.key   := k;
  w^.bf    := 0;

  //----------------------------------------
  // FAZA 1 - wstawienie węzła do drzewa AVL
  //----------------------------------------

  // rozpoczynamy od korzenia
  p := root;

  // jeśli drzewo jest puste, to węzeł w
  if p = nil then
    root := w // umieszczamy w korzeniu
  else
  begin // inaczej szukamy miejsce dla w
    while true do
      // porównujemy klucze
      if k < p^.key then
      begin
        // jeśli p nie posiada
        // lewego syna, to
        if p^.left = nil then
        begin
          // lewym synem p
          // staje się węzeł w
          p^.left := w;
          break; // wychodzimy z pętli
        end;
        // inaczej przechodzimy
        // do lewego syna 
        p := p^.left;
      end
      else
      begin
        // jeśli p nie posiada
        // prawego syna, to
        if p^.right = nil then
        begin
          // prawym synem 
          // staje się węzeł w
          p^.right := w;
          break; // wychodzimy z pętli
        end;
        // inaczej przechodzimy
        // do prawego syna 
        p := p^.right;
      end;
    w^.up := p; // ojcem w jest p

    //---------------------------------
    // FAZA 2 - równoważenie drzewa AVL
    //---------------------------------

    if p^.bf <> 0 then
      p^.bf := 0 // UWAGA NR 1
    else
    begin
      if p^.left = w then // UWAGA NR 2
        p^.bf := 1
      else
        p^.bf := -1;
      // będziemy szli w górę drzewa
      // w kierunku korzenia
      // r i p wskazują ojca 
      // i syna na tej ścieżce
      r := p^.up;
      t := false;
      while r <> nil do
      begin
        if r^.bf <> 0 then
        begin
          // ustalamy wynik pętli
          t := true;
          break; // przerywamy pętlę
        end;
        // inaczej modyfikujemy r.bf
        if r^.left = p then
          r^.bf :=  1
        else
          r^.bf := -1;
        // przechodzimy w górę
        // na wyższy poziom
        p := r;
        r := r^.up;
      end;

      // jeśli r.bf = +/- 1, 
      // to musimy
      // równoważyć drzewo
      if t then
      begin
        if r^.bf = 1 then
        begin
          // gałęzie się równoważą
          if r^.right = p then
            r^.bf := 0
          else
            if p^.bf = -1 then
              rot_lr(root, r)
            else
              rot_ll(root, r);
        end
        else
        begin // r.bf = -1
          // gałęzie się równoważą
          if r^.left = p then
            r^.bf := 0
          else
            if p^.bf = 1 then
              rot_rl(root, r)
            else
              rot_rr(root, r);
        end;
      end;
    end;
  end;
end;

// Funkcja znajduje
// poprzednik węzła p
//-------------------
function avl_pred(p : PAVLnode)
                   : PAVLnode;
var
  r : PAVLnode;
begin
  if p <> nil then
  begin
    if p^.left <> nil then
    begin
      p := p^.left;
      while p^.right <> nil do
        p := p^.right;
    end
    else
    repeat
      r := p;
      p := p^.up;
    until (p = nil) or (p^.right = r);
  end;
  avl_pred := p;
end;

// Funkcja szuka w drzewie AVL
// węzła o zadanym kluczu. Jeśli
// go znajdzie, zwraca jego wskazanie.
// Jeżeli nie, to zwraca wskazanie puste.
// Parametrami są:
// p - wskazanie korzenia drzewa AVL
// k - klucz poszukiwanego węzła
//---------------------------------------
function avl_find(p : PAVLnode;
                 k : integer)
                   : PAVLnode;
begin
  while (p <> nil) and
        (p^.key <> k) do
    if k < p^.key then
      p := p^.left
    else
      p := p^.right;
  avl_find := p;
end;

// Funkcja usuwa rekurencyjnie węzeł x
// root - referencja do zmiennej
//        z adresem korzenia
// x - wskazanie usuwanego węzła
//------------------------------------
function avl_remove(var root : PAVLnode;
                          x : PAVLnode)
                            : PAVLnode;
var
  t, y, z : PAVLnode;
  nest  : boolean;

begin
  if (x^.left <> nil) and
     (x^.right <> nil) then
  begin
    y := avl_remove(root, avl_pred(x));
    nest := false;
  end
  else
  begin
    if x^.left <> nil then
    begin
      y := x^.left;
      x^.left := nil;
    end
    else
    begin
      y := x^.right;
      x^.right := nil;
    end;
    x^.bf := 0;
    nest := true;
  end;

  if y <> nil then
  begin
    y^.up := x^.up;
    y^.left := x^.left;
    if y^.left <> nil then
      y^.left^.up  := y;

    y^.right := x^.right;
    if y^.right <> nil then
      y^.right^.up := y;

    y^.bf := x^.bf;
  end;

  if x^.up <> nil then
  begin
    if x^.up^.left = x then
      x^.up^.left := y
    else
      x^.up^.right := y;
  end
  else
    root := y;

  if nest then
  begin
    z := y;
    y := x^.up;
    while y <> nil do
    begin
      if y^.bf = 0 then
      begin // Przypadek nr 1
        if y^.left = z then
          y^.bf := -1
        else
          y^.bf := 1;
        break;
      end
      else
      begin
        if((y^.bf = 1) and (y^.left = z)) or
          ((y^.bf = -1) and (y^.right = z)) then
        begin // Przypadek nr 2
          y^.bf := 0;
          z := y;
          y := y^.up;
        end
        else
        begin
          if y^.left = z then
            t := y^.right
          else
            t := y^.left;
          if t^.bf = 0 then
          begin // Przypadek 3A
            if y^.bf = 1 then
              rot_ll(root, y)
            else
              rot_rr(root, y);
            break;
          end
          else
            if y^.bf = t^.bf then
            begin // Przypadek 3B
              if y^.bf = 1 then
                rot_ll(root, y)
              else
                rot_rr(root, y);
              z := t;
              y := t^.up;
            end
            else
            begin // Przypadek 3C
              if y^.bf = 1 then
                rot_lr(root, y)
              else
                rot_rl(root, y);
              z := y^.up;
              y := z^.up;
            end
        end
      end
    end
  end;
  avl_remove := x;
end;

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

var
  // tablica kluczy węzłów
  Tk : array [0..31] of integer;
  i, x, i1, i2  : integer;
  // korzeń drzewa AVL
  root : PAVLnode;

begin
  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie
  // edytory pozwalają wstawiać
  // znaki konsoli do tworzenia
  // ramek.

  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  randomize;
  // Tworzymy puste drzewo AVL
  root := nil;
  // Tablicę wypełniamy wartościami kluczy
  for i := 0 to 31 do
    Tk[i] := i+1;
  // Mieszamy tablicę
  for i := 1 to 300 do
  begin
    // Losujemy 2 indeksy
    i1 := random(32);
    i2 := random(32);
    // Wymieniamy Tk[i1] <--> Tk[i2]
    x := Tk[i1];
    Tk[i1] := Tk[i2];
    Tk[i2] := x;
  end;
  // Na podstawie tablicy
  // tworzymy drzewo AVL
  for i := 0 to 31 do
  begin
    write(Tk[i], ' ');
    avl_insert(root, Tk [i]);
  end;
  writeln; writeln;
  // Wyświetlamy zawartość drzewa AVL
  print_bt('', '', root);
  writeln; writeln;
  // Ponownie mieszamy tablicę
  for i := 1 to 300 do
  begin
    i1 := random(32);
    i2 := random(32);
    x := Tk[i1];
    Tk[i1] := Tk[i2];
    Tk[i2] := x;
  end;
  // Usuwamy 15 węzłów
  for i := 0 to 14 do
  begin
    write(Tk[i], ' ');
    avl_remove(root, avl_find(root, Tk[i]));
  end;
  writeln; writeln;
  // Wyświetlamy zawartość drzewa AVL
  print_bt('', '', root);
  // Usuwamy drzewo AVL z pamięci
  dfs_release(root);
end.

// Drzewo AVL
// Data: 22.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definicja typu węzłów drzewa AVL
//---------------------------------
struct AVLnode
{
  AVLnode * up, *left, *right;
  int key, bf;
};

// Zmienne globalne
//-----------------

// łańcuchy do znaków ramek
string cr, cl, cp;

// Procedura wypisuje drzewo
//--------------------------
void print_bt(string sp, 
             string sn, 
             AVLnode * v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr)
      s[s.length()-2] = ' ';
    print_bt (s+cp, cr, v->right);
    s = s.substr(0, sp.length()-2);
    cout << s << sn << v->key
         << ":" << v->bf << endl;
    s = sp;
    if(sn == cl)
      s[s.length()-2] = ' ';
    print_bt(s+cp, cl, v->left);
  }
}

// Procedura DFS:postorder
// usuwająca drzewo
//------------------------
void dfs_release(AVLnode * v)
{
  if(v)
  {
    // usuwamy lewe poddrzewo
    dfs_release(v->left);
    // usuwamy prawe poddrzewo
    dfs_release(v->right);
    // usuwamy sam węzeł
    delete v;
  }
}

// Rotacja RR
//-----------
void rot_rr(AVLnode * & root, 
        AVLnode * A)
{
  AVLnode * B = A->right, 
          * p = A->up;

  A->right = B->left;
  if(A->right)
    A->right->up = A;

  B->left = A;
  B->up = p;
  A->up = B;

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

  if(B->bf == -1)
    A->bf = B->bf = 0;
  else
  {
    A->bf = -1;
    B->bf = 1;
  }
}

// Rotacja LL
//-----------
void rot_ll(AVLnode * & root, 
        AVLnode * A)
{
  AVLnode * B = A->left, 
          * p = A->up;

  A->left = B->right;
  if(A->left)
    A->left->up = A;

  B->right = A;
  B->up = p;
  A->up = B;

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

  if(B->bf == 1)
    A->bf = B->bf = 0;
  else
  {
    A->bf = 1;
    B->bf = -1;
  }
}

// Rotacja RL
//-----------
void rot_rl(AVLnode * & root, 
        AVLnode * A)
{
  AVLnode * B = A->right, 
          * C = B->left, 
          * p = A->up;

  B->left = C->right;
  if(B->left)
    B->left->up = B;

  A->right = C->left;
  if(A->right)
    A->right->up = A;

  C->left = A;
  C->right = B;
  A->up = B->up = C;
  C->up = p;

  if(p)
  {
    if(p->left == A)
      p->left = C;
    else
      p->right = C;
  }
  else root = C;

  if(C->bf == -1)
    A->bf = 1;
  else
    A->bf = 0;

  if(C->bf == 1)
    B->bf = -1;
  else
    B->bf = 0;

  C->bf = 0;
}

// Rotacja LR
//-----------
void rot_lr(AVLnode * & root, 
        AVLnode * A)
{
  AVLnode * B = A->left, 
          * C = B->right, 
          * p = A->up;

  B->right = C->left;
  if(B->right)
    B->right->up = B;

  A->left = C->right;
  if(A->left)
    A->left->up = A;

  C->right = A;
  C->left = B;
  A->up = B->up = C;
  C->up = p;

  if(p)
  {
    if(p->left == A)
      p->left = C;
    else
      p->right = C;
  }
  else root = C;

  if(C->bf == 1)
    A->bf = -1;
  else
    A->bf = 0;

  if(C->bf == -1)
    B->bf = 1;
  else
    B->bf = 0;

  C->bf = 0;
}

// Wstawia nowy węzeł do drzewa AVL
// root - referencja korzenia
// k    - klucz nowego węzła
//---------------------------------
void avl_insert(AVLnode * & root, 
               int k)
{
  AVLnode * w, * p, * r;
  bool t;

  // tworzymy dynamicznie nowy węzeł
  w = new AVLnode;
  w->left = w->right = w->up = NULL;
  w->key = k;
  w->bf = 0;

  //----------------------------------------
  // FAZA 1 - wstawienie węzła do drzewa AVL
  //----------------------------------------

  // rozpoczynamy od korzenia
  p = root;

  // jeśli drzewo jest puste, 
  // to węzeł w umieszczamy w korzeniu
  if(!p) root = w;
  else
  {
    // inaczej szukamy miejsce dla w
    while(true)
      // porównujemy klucze
      if(k < p->key)
      {
        // jeśli p nie posiada
        // lewego syna, to
        if(!p->left)
        {
          // lewym synem p
          // staje się węzeł w
          p->left = w;
          break; // wychodzimy z pętli
        }
        // inaczej przechodzimy
        // do lewego syna 
        p = p->left;
      }
      else
      {
        // jeśli p nie posiada
        // prawego syna, to
        if(!p->right)
        {
          // prawym synem 
          // staje się węzeł w
          p->right = w;
          break; // wychodzimy z pętli
        }
        // inaczej przechodzimy
        // do prawego syna 
        p = p->right;
      }
    w->up = p; // ojcem w jest p

    //---------------------------------
    // FAZA 2 - równoważenie drzewa AVL
    //---------------------------------

    if(p->bf)
      p->bf = 0; // UWAGA NR 1
    else
    {
      if(p->left == w) // UWAGA NR 2
        p->bf = 1;
      else
        p->bf = -1;

      // będziemy szli w górę drzewa
      // w kierunku korzenia
      // r i p wskazują ojca 
      // i syna na tej ścieżce
      r = p->up;
      t = false;
      while(r)
      {
        if(r->bf)
        {
          // ustalamy wynik pętli
          t = true;
          break; // przerywamy pętlę
        };
        // inaczej modyfikujemy r.bf
        if(r->left == p)
          r->bf = 1;
        else
          r->bf = -1;
        // przechodzimy w górę
        // na wyższy poziom
        p = r;
        r = r->up;
      }
      // jeśli r.bf = +/- 1, 
      // to musimy równoważyć drzewo
      if(t)
      {
        if(r->bf == 1)
        {
          // gałęzie się równoważą
          if(r->right == p)
            r->bf = 0;
          else if(p->bf == -1)
            rot_lr(root, r);
          else
            rot_ll(root, r);
        }
        else
        { // r.bf = -1
          // gałęzie się równoważą
          if(r->left == p)
            r->bf = 0;
          else if(p->bf == 1)
            rot_rl(root, r);
          else
            RR (root, r);
        }
      }
    }
  }
}

// Funkcja znajduje
// poprzednik węzła p
//-------------------
AVLnode * avl_pred(AVLnode * p)
{
  AVLnode * r;

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

// Funkcja szuka w drzewie AVL
// węzła o zadanym kluczu.
// Jeśli go znajdzie, zwraca
// jego wskazanie. Jeżeli nie, 
// to zwraca wskazanie puste.
// Parametrami są:
// p - wskazanie korzenia drzewa AVL
// k - klucz poszukiwanego węzła
//----------------------------------
AVLnode * avl_find(AVLnode * p, 
                  int k)
{
  while(p && p->key != k)
    p = (k < p->key) ? p->left:
                       p->right;
  return p;
}

// Funkcja usuwa rekurencyjnie
// węzeł x
// root - referencja do zmiennej
//        z adresem korzenia
// x    - wskazanie usuwanego węzła
//---------------------------------
AVLnode * avl_remove(AVLnode * & root, 
                    AVLnode * x)
{
  AVLnode  * t, * y, * z;
  bool nest;

  if(x->left && x->right)
  {
    y = avl_remove(root, avl_pred(x));
    nest = false;
  }
  else
  {
    if(x->left)
    {
      y = x->left;
      x->left = NULL;
    }
    else
    {
      y = x->right;
      x->right = NULL;
    }
    x->bf = 0;
    nest = true;
  }

  if(y)
  {
    y->up = x->up;
    y->left = x->left;
    if(y->left)
      y->left->up = y;

    y->right = x->right;
    if(y->right)
      y->right->up = y;

    y->bf = x->bf;
  }

  if(x->up)
  {
    if(x->up->left == x)
      x->up->left = y;
    else
      x->up->right = y;
  }
  else root = y;

  if(nest)
  {
    z = y;
    y = x->up;
    while(y)
    {
      if(!y->bf)
      { // Przypadek nr 1
        if(y->left == z)
          y->bf = -1;
        else
          y->bf = 1;
        break;
      }
      else
      {
        if(((y->bf ==  1) && (y->left  == z))||
           ((y->bf == -1) && (y->right == z)))
        { // Przypadek nr 2
          y->bf = 0;
          z = y;
          y = y->up;
        }
        else
        {
          if(y->left == z)
            t = y->right;
          else t = y->left;

          if(!t->bf)
          { // Przypadek 3A
            if(y->bf == 1)
              rot_ll(root, y);
            else
              rot_rr(root, y);
            break;
          }
          else if(y->bf == t->bf)
          { // Przypadek 3B
            if(y->bf == 1)
              rot_ll(root, y);
            else
              rot_rr(root, y);
            z = t;
            y = t->up;
          }
          else
          { // Przypadek 3C
            if(y->bf == 1)
              rot_lr(root, y);
            else
              rot_rl(root, y);
            z = y->up;
            y = z->up;
          }
        }
      }
    }
  }
  return x;
}

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

int main()
{
  // tablica kluczy węzłów
  int Tk[32];
  int i, i1, i2;
  AVLnode * root = NULL;

  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie
  // edytory pozwalają wstawiać
  // znaki konsoli do tworzenia
  // ramek.

  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

  srand(time(NULL));

  // Tablicę wypełniamy wartościami kluczy
  for(i = 0; i < 32; i++)
    Tk[i] = i+1;
  // Mieszamy tablicę
  for(i = 0; i < 300; i++)
  {
    // Losujemy 2 indeksy
    i1 = rand()%32;
    i2 = rand()%32;
    // Wymieniamy Tk[i1] <--> Tk[i2]
    swap(Tk[i1], Tk[i2]);
  }
  // Na podstawie tablicy
  // tworzymy drzewo AVL
  for(i = 0; i < 32; i++)
  {
    cout << Tk[i] << " ";
    avl_insert(root, Tk[i]);
  }
  cout << endl << endl;
  // Wyświetlamy zawartość drzewa AVL
  print_bt("", "", root);
  cout << endl << endl;
  // Ponownie mieszamy tablicę
  for(i = 0; i < 300; i++)
  {
    i1 = rand()%32;
    i2 = rand()%32;
    swap(Tk[i1], Tk[i2]);
  }
  // Usuwamy 15 węzłów
  for(i = 0; i < 15; i++)
  {
    cout << Tk[i] << " ";
    avl_remove(root, avl_find(root, Tk[i]));
  }
  cout << endl << endl;
  // Wyświetlamy zawartość drzewa AVL
  print_bt("", "", root);
  // Usuwamy drzewo AVL z pamięci
  dfs_release(root);
  return 0;}

' Drzewo AVL
' Data: 22.05.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Definicja typu węzłów drzewa AVL
'---------------------------------
Type AVLnode
  up As AVLnode Ptr
  Left As AVLnode Ptr
  Right As AVLnode Ptr
  key As Integer
  bf As Integer
End Type

' Zmienne globalne
'-----------------

' łańcuchy do ramek
Dim Shared As String * 2 cr, _
                         cl, _
                         cp

' Procedura wypisuje drzewo
'--------------------------
Sub print_bt(sp As String, _
             sn As String, _
              v As AVLnode Ptr)

  Dim As String s

  If v Then
    s = sp
    If sn = cr Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cp, cr, v->Right)

    s = Mid(s, 1, Len(sp)-2)
    Print Using "&&&:&";s;sn;v->key;v->bf

    s = sp
    If sn = cl Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cp, cl, v->Left)
  End If
End Sub

' Procedura DFS:postorder
' usuwająca drzewo
'------------------------
Sub dfs_release(v As AVLnode Ptr)
  If v Then
    ' usuwamy lewe poddrzewo
    dfs_release(v->left)
    ' usuwamy prawe poddrzewo
    dfs_release (v->right)
    ' usuwamy sam węzeł
    delete v
  End If
End Sub

' Rotacja RR
'-----------
Sub rot_rr(ByRef root As AVLnode Ptr, _
       ByVal A As AVLnode Ptr)
  Dim As AVLnode Ptr B = A->right, _
                      p = A->up
  A->right = B->Left
  If A->Right Then _
    A->right->up = A

  B->left = A
  B->up = p
  A->up = B

  If p Then
    if p->left = A Then
    	p->left = B
    Else
    	p->right = B
    End If
  Else
    root = B
  End If

  If B->bf = -1 Then
    A->bf = 0
    B->bf = 0
  Else
    A->bf = -1
    B->bf = 1
  End If
End Sub

' Rotacja LL
'-----------
Sub rot_ll(ByRef root As avlNode Ptr, _
       ByVal A As AVLnode Ptr)
  Dim As AVLnode Ptr B = A->left, _
                     p = A->up
  A->left = B->Right
  If A->left Then _
    A->left->up = A

  B->right = A
  B->up = p
  A->up = B

  If p Then
    If p->left = A Then
    	p->left = B
    Else
    	p->right = B
    End If
  Else
    root = B
  End If

  if B->bf = 1 Then
    A->bf = 0
    B->bf = 0
  Else
    A->bf =  1
    B->bf = -1
  End If
End Sub

' Rotacja RL
'-----------
Sub rot_rl(ByRef root As AVLnode Ptr, _
       ByVal A As AVLnode Ptr)
  Dim As AVLnode Ptr B = A->right, _
                     C = B->left, _
                     p = A->up
  B->left = C->Right
  if B->left Then _
    B->left->up = B

  A->right = C->Left
  If A->Right Then _
    A->right->up = A

  C->left = A
  C->right = B
  A->up = C
  B->up = C
  C->up = p

  If p Then
    if p->left = A Then
      p->left = C
    Else
      p->right = C
    End If
  Else
    root = C
  End If

  If C->bf = -1 Then
    A->bf = 1
  Else
    A->bf = 0
  End If
  
  If C->bf =  1 Then
    B->bf = -1
  Else
    B->bf = 0
  End If
  
  C->bf = 0
End Sub

' Rotacja LR
'-----------
sub rot_lr(ByRef root As AVLnode Ptr, _
       ByVal A As AVLnode Ptr)
  Dim As AVLnode Ptr B = A->left, _
                     C = B->right, _
                     p = A->up
  B->right = C->Left
  If B->right Then _
    B->right->up = B

  A->left = C->Right
  if A->left Then _
    A->left->up = A

  C->right = A
  C->left = B
  A->up = C
  B->up = C
  C->up = p

  if p Then
    If p->left = A Then
      p->left = C
    Else
      p->right = C
    End If
  Else
    root = C
  End If

  If C->bf = 1 Then
    A->bf = -1
  Else
    A->bf = 0
  End If
  
  If C->bf = -1 Then
    B->bf =  1
  Else
    B->bf = 0
  End If

  C->bf = 0
End Sub

' Wstawia nowy węzeł do drzewa AVL
' root - referencja korzenia
' k    - klucz nowego węzła
'---------------------------------
Sub avl_insert(ByRef root As AVLnode Ptr, _
                       k As Integer)	
  Dim As AVLnode Ptr w, p, r
  Dim As Integer t

  ' tworzymy dynamicznie nowy węzeł
  w = new AVLnode
  w->left  = 0
  w->right = 0
  w->up    = 0
  w->key   = k
  w->bf    = 0

  '----------------------------------------
  ' FAZA 1 - wstawienie węzła do drzewa AVL
  '----------------------------------------

  ' rozpoczynamy od korzenia
  p = root

  If p = 0 Then
    ' jeśli drzewo jest puste, 
    ' to węzeł w umieszczamy w korzeniu
    root = w         
  Else
    ' inaczej szukamy miejsce dla w
    While 1
      ' porównujemy klucze
      If k < p->key Then
        ' jeśli p nie posiada
        ' lewego syna, to
        If p->Left = 0 Then
          ' lewym synem p
          ' staje się węzeł w
          p->left = w
          Exit While ' wychodzimy z pętli
        End If
        ' inaczej przechodzimy
        ' do lewego syna 
        p = p->Left
      Else
        ' jeśli p nie posiada
        ' prawego syna, to
        If p->Right = 0 Then
          ' prawym synem 
          ' staje się węzeł w
          p->right = w
          Exit While ' wychodzimy z pętli
        End If
        ' inaczej przechodzimy
        ' do prawego syna 
        p = p->Right
      End If
    Wend
    w->up = p ' ojcem w jest p

    '---------------------------------
    ' FAZA 2 - równoważenie drzewa AVL
    '---------------------------------

    If p->bf Then
    	p->bf = 0 ' UWAGA NR 1
    Else
      ' UWAGA NR 2
      If p->left = w Then
        p->bf = 1
      Else
        p->bf = -1
      End If

      ' będziemy szli w górę drzewa
      ' w kierunku korzenia
      ' r i p wskazują ojca 
      ' i syna na tej ścieżce
      r = p->up

      t = 0
      While r
        If r->bf Then
          ' ustalamy wynik pętli
          t = 1
          Exit While ' przerywamy pętlę
        End If
        ' inaczej modyfikujemy r.bf
        If r->left = p Then
          r->bf = 1
        Else
          r->bf = -1
        End If

        ' przechodzimy w górę
        ' na wyższy poziom
        p = r
        r = r->up
      Wend
      ' jeśli r.bf = +/- 1, 
      ' to musimy równoważyć drzewo
      If t = 1 Then
        If r->bf = 1 Then
          If r->right = p Then
          	' gałęzie się równoważą
            r->bf = 0
          ElseIf p->bf = -1 Then
            rot_lr(root, r)
          Else
            rot_ll(root, r)
          End If
        Else ' r.bf = -1
          If r->left = p Then
            ' gałęzie się równoważą
            r->bf = 0
          ElseIf p->bf = 1 Then
            rot_rl(root, r)
          Else
            rot_rr(root, r)
          End If
        End If
      End If
    End If
  End If
End Sub

' Funkcja znajduje poprzednik węzła p
'------------------------------------
Function avl_pred(ByVal p As AVLnode Ptr) _
                         As AVLnode Ptr
  Dim As AVLnode Ptr r

  If p Then
    If p->Left Then
      p = p->Left
      While p->Right
      	p = p->Right
      Wend
    Else
      Do
        r = p
        p = p->up
      Loop Until p = 0 OrElse _
                 p->Right = r
    End If
  End If
  Return p
 
End Function

' Funkcja szuka w drzewie AVL
' węzła o zadanym kluczu.
' Jeśli go znajdzie, zwraca
' jego wskazanie. Jeżeli nie, 
' to zwraca wskazanie puste.
' Parametrami są:
' p - wskazanie korzenia drzewa AVL
' k - klucz poszukiwanego węzła
'----------------------------------
Function avl_find(p As AVLnode Ptr, _
                 k As Integer) _
                   As AVLnode Ptr
  while(p <> 0) AndAlso _
       (p->key <> k)
    If k < p->key Then
      p = p->Left
    Else
      p = p->Right
    End If
  Wend
  Return p
 
End Function

' Funkcja usuwa rekurencyjnie węzeł x
' root - referencja do zmiennej
'        z adresem korzenia
' x    - wskazanie usuwanego węzła
'------------------------------------
Function avl_remove(ByRef root As AVLnode Ptr, _
                            x As AVLnode Ptr) _
                              As AVLnode Ptr

  Dim As AVLnode Ptr t, y, z
  Dim As Integer nest

  if(x->Left <> 0) And _
    (x->Right <> 0) Then
    y = avl_remove(root, avl_pred(x))
    nest = 0
  Else
    If x->Left Then
      y = x->left
      x->left = 0
    Else
      y = x->right
      x->right = 0
    End If
    x->bf = 0
    nest  = 1
  End If

  If y Then
    y->up = x->up
    y->left = x->left
    If y->Left Then _
      y->left->up  = y
      
    y->right = x->right
    If y->Right Then _
      y->right->up = y
    
    y->bf = x->bf
  End If

  If x->up Then
    If x->up->left = x Then
      x->up->left = y
    Else
      x->up->right = y
    End If
  Else
    root = y
  End If

  If nest = 1 Then
    z = y
    y = x->up
    While y
      If y->bf = 0 Then ' Przypadek nr 1
        If y->left = z Then
          y->bf = -1
        Else
          y->bf = 1
        End If
        Exit While
      Else
        ' Przypadek nr 2
        if((y->bf = 1) AndAlso (y->left = z)) OrElse _
          ((y->bf = -1) AndAlso (y->right = z)) Then
          y->bf = 0
          z = y: y = y->up
        Else
          If y->left = z Then
            t = y->right
          Else
            t = y->Left
          End If
          If t->bf = 0 then ' Przypadek 3A
            If y->bf = 1 Then
              rot_ll(root, y)
            Else
              rot_rr(root, y)
            End If
            Exit While
          ElseIf y->bf = t->bf Then ' Przypadek 3B
            If y->bf = 1 Then
              rot_ll(root, y)
            Else
              rot_rr(root, y)
            End If
            z = t
            y = t->up
          Else ' Przypadek 3C
            If y->bf = 1 Then
              rot_lr(root, y)
            Else
              rot_rl(root, y)
            End If
            z = y->up
            y = z->up
          End If
        End If
      End If
    Wend
  End If
  Return x
End Function

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

' tablica kluczy węzłów
Dim As Integer Tk(31)
Dim As Integer i, i1, i2
Dim As AVLnode Ptr root = 0

' ustawiamy łańcuchy znakowe, 
' ponieważ nie wszystkie edytory
' pozwalają wstawiać znaki konsoli
' do tworzenia ramek.

' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr(218)+Chr(196)
cl = Chr(192)+Chr(196)
cp = Chr(179)+" "

Randomize
' Tablicę wypełniamy wartościami kluczy
For i = 0 To 31
  Tk(i) = i+1
Next
' Mieszamy tablicę
For i = 1 To 300
  ' Losujemy 2 indeksy
  i1 = Int(Rnd()*32)
  i2 = Int(Rnd()*32)
  ' Wymieniamy Tk[i1] <--> Tk[i2]
  Swap Tk(i1), Tk(i2)
Next
' Na podstawie tablicy tworzymy drzewo AVL
For i = 0 To 31
  Print Tk(i);
  avl_insert(root, Tk(i))
Next
Print: Print
' Wyświetlamy zawartość drzewa AVL
print_bt("", "", root)
Print: Print
' Ponownie mieszamy tablicę
For i = 1 To 300
  i1 = Int(Rnd()*32)
  i2 = Int(Rnd()*32)
  Swap Tk(i1), Tk(i2)
Next
' Usuwamy 15 węzłów
For i = 0 To 14
  Print Tk(i);
  avl_remove(root, avl_find(root, Tk(i)))
Next
Print: Print
' Wyświetlamy zawartość drzewa AVL
print_bt("", "", root)
' Usuwamy drzewo BST z pamięci
dfs_release(root)
End